前言
唤我沈七就好啦。
最大公约数
最大公约数，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b）
最大公约数可以为1。两个互为质数的数,其最大公约数就是1。如3和5的最大公约数就是1。
辗转相除法
求两个数的最大公约数的步骤如下:
333用小的一个数除大的一个数,得第一个余数;
再用第一个余数除小的一个数,得第二个余数;
又用第二个余数除第一个余数,得第三个余数;
这样逐次用后一个数去除前一个余数,直到余数是0为止.
最后一个除数就是所求的最大公约数。
例如求1515和600的最大公约数,
第一次:用600除1515,商2余315;
第二次:用315除600,商1余285;
第三次:用285除315,商1余30;
第四次:用30除285,商9余15;
第五次:用15除30,商2余0.
1515和600的最大公约数是15
实现代码
while(b) { r=a%b; sum+=a/b; a=b;b=r; }
欧几里得算法
欧几里得算法实际上是 辗转相除法的递归实现版本，核心代码只有一行。
long long gcd(long long a,long long b) { return b?gcd(b,a%b):a; }
习题练习：
矩形切割
小明有一些矩形的材料，他要从这些矩形材料中切割出一些正方形。
当他面对一块矩形材料时，他总是从中间切割一刀，切出一块最大的正方 形，
剩下一块矩形，然后再切割剩下的矩形材料，直到全部切为正方形为止。
例如，对于一块两边分别为 5 和 3 的材料（记为 5×3），小明会依次切出 3×3、2×2、1×1、1×1 共 4 个正方形。 现在小明有一块矩形的材料，两边长分别是 2019 和 324。请问小明最终会 切出多少个正方形？
题解部分：
考点：辗转求余、模拟
每次有选取剩下矩形的宽来作为正方形的边长
第一次切割：
2019 / 324 = 6 **** 75
第二次切割：
324 / 75 = 4 **** 24
第三次切割：
75 / 24 = 3 **** 3
第四次切割：
24 / 3 = 8
sum = 6 + 4 + 3 + 8 = 21；
递归实现：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5+10; int sum; LL gcd(LL a,LL b) { return b?gcd(b,a%b),sum+=a/b:sum; } int main() { gcd(2019,324); cout<<sum; return 0; }
迭代模拟：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5+10; int sum; int main() { int a=2019,b=324,r; while(b) { r=a%b; sum+=a/b; a=b;b=r; } cout<<sum; return 0; }
最小公倍数
a与b的最小公倍数是两者的乘积与两者的最大公因数的商
最大公因数和最小公倍数的乘积等于原两个数的乘积。
实现代码：
int lcm(int a, int b) { return a*b/gcd(a,b); }
约数个数
任 意 一 数 字 N 都 可 以 形 成 质 因 子 相 乘 的 形 式 ： N = p 1 a ∗ p 2 b ∗ … ∗ p k x 任意一数字 N 都可以形成 质因子相乘的形式：N=p1^a ∗p2^b∗…∗pk^x
任意一数字N都可以形成质因子相乘的形式：N=p1
a
∗p2
b
∗…∗pk
x
来复习一下
质因数分解
void divide(int x) { for (int i = 2; i <= x / i; i ++ )//先枚举小于根号x的素数 if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl; cout << endl; }
给 定 n 个 正 整 数 a i ， 请 你 输 出 这 些 数 的 乘 积 的 约 数 个 数 ， 答 案 对 1 0 9 + 7 取 模 。 给定 n 个正整数 a i，请你输出这些数的乘积的约数个数，答案对 10^9+7 取模。
给定n个正整数ai，请你输出这些数的乘积的约数个数，答案对10
9
+7取模。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int mod = 1e9 + 7; int main(){ int n,x; LL ans = 1; unordered_map<int,int> hash; cin >> n; while(n--){ cin >> x; for(int i = 2;i <= x/i; ++i){ while(x % i == 0){ x /= i; hash[i] ++; } } if(x > 1) hash[x] ++; } for(auto i : hash) ans = ans*(i.second + 1) % mod; cout << ans; return 0;
约数之和
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 110, mod = 1e9 + 7; int main() { int n; cin >> n; unordered_map<int, int> primes; while (n -- ) { int x; cin >> x; for (int i = 2; i <= x / i; i ++ ) while (x % i == 0) { x /= i; primes[i] ++ ; } if (x > 1) primes[x] ++ ; } LL res = 1; for (auto p : primes) { LL a = p.first, b = p.second; LL t = 1; while (b -- ) t = (t * a + 1) % mod; res = res * t % mod; } cout << res << endl; return 0; }
完结散花
ok以上就是对 算法模版：数论之约数全家桶 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
参考文献
https://www.acwing.com/activity/content/19/
