约数
基本概念
若整数 n 除以整数 d 的余数为零，即 d 能够整除 n,则称 d 是 n 的约数，n 是 d 的倍数，记作：d|n
约数的判定——试除法
例题描述
参考代码(C++版本)
#include <iostream> #include <algorithm> #include <vector> using namespace std; vector<int> get_divisors(int n) { vector<int> res; for(int i = 1; i <= n / i;i++) if(n % i == 0) { res.push_back(i); if(i != n / i) res.push_back(n / i); } //按照从小到大的顺序输出它的所有约数。 sort(res.begin(),res.end()); return res; } int main() { int n; cin >> n; while(n--) { int x; cin >> x; auto res = get_divisors(x); for(auto t: res) cout << t << ' '; cout << endl; } return 0; }
算法模板
vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); } sort(res.begin(), res.end()); return res; }
疑难点剖析
一、优化
最暴力的做法依旧是可爱的枚举，从1枚举到x，但是和求质数算法一样，当3是约数的时候，就不必去枚举12,15等等
二、结果统计
if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); }
利用的性质是：两数相乘，积 = 乘数 x 另一个乘数。 x % i == 0说明 i 是 x 的一个乘数，则另一乘数就是 x/i，将其加入集合
统计约数的个数
例题描述
参考代码(C++版本)
#include <iostream> #include <algorithm> #include <unordered_map> using namespace std; typedef long long LL; const int mod = 1e9 + 7; int main() { //输入 int n; cin >> n; //用STL容器开一个哈希表存分解出来的数的底数和指数 unordered_map<int,int> primes; while(n--) { int x; cin >> x; //分解质因数的算法模板来分解这个输入的x for(int i = 2; i <= x / i;i++) while(x % i == 0) { x /= i; primes[i] ++;//使i这个质因数的指数加1 } if(x > 1) primes[x] ++; //对传入的x直接就是质因子的情况进行处理 } //输出 LL res = 1; for(auto prime : primes) res = res * (prime.second + 1) % mod; cout << res << endl; return 0; }
算法模板
求约数个数算法实现流程：
统计约数的和
例题描述
参考代码(C++版本)
#include <iostream> #include <algorithm> #include <unordered_map> using namespace std; typedef long long LL; const int mod = 1e9 + 7; int main() { //输入 int n; cin >> n; //开一个哈希表存分解出来的数的底数和指数 unordered_map<int,int> primes; while(n--) { int x; cin >> x; //分解这个输入的x for(int i = 2; i <= x / i;i++) while(x % i == 0) { x /= i; primes[i] ++;//i这个质因数的指数加1 } if(x > 1) primes[x] ++; } //结合公式输出 LL res = 1; for(auto prime : primes) { //p是质数，也就是公式中的底数，a是质数出现的个数，也就是公式中的指数 int p = prime.first , a = prime.second; LL t = 1; while(a--) t = (t * p + 1) % mod; res = res * t % mod; } cout << res << endl; return 0; }
算法模板
求约数和算法实现流程：
公式推导
看完求约数个数的算法实现流程和求约数和的算法实现流程小伙伴们心中应该能很清晰的感受到，大致是相似的，只是最后输出时运用的公式不一样。
数论这章了，很像高中的数学题了，知道那个性质，明白那个公式，大抵就能够做出来的
在查阅资料之后，发现李煜东老师的《算法竞赛——进阶指南》中的对两个公式的推导十分清晰，故笔者就不画蛇添足、班门弄斧了
求约数个数的公式的意思，就是将得到的质因数再分解。例如25中，20是约数，21是约数，22是约数，23是约数，24是约数，25是约数，所以就有5+1个约数，即公式中的c1+1。对于其他分解出来的质因数也是同理分解。
求约数和的公式意思，将分解出来的质因数，同时也是这个正整数乘积96的约数，它们之间的和是多少。
25 和 31 组成的约数应该有：20、 21 、 22、23 、 24 、25 、 30 、 31。
那么这些它们组成的约数和应试是
20 x （ 30 + 31 ） + 21 x （ 30 + 31）+…+ 2^5 x ( 30 + 31 ）
经过整理，就可以得到形容李老师书中的公式：
( 20+ 21 + 22+ 23 + 24 +25 ) x( 30 + 31)
即:（1+ 21 + 22+ 23 + 24 +25 ）x (1 + 31)
演示完毕啦
欧几里得算法
基本概念
公约数：
若自然数 d 同时是自然数 a 和 b的公约数。则称 d 是 a 和 b 的公约数。在所有 a 和 b 的公约数中最大的一个，称为 a 和 b 的最大公约数，记作 gcd(a,b)
公倍数：
若自然数 m 同时是自然数 a 和 b的公约数。则称 m 是 a 和 b 的公倍数。在所有 a 和 b 的公约数中最小的一个，称为 a 和 b的最小公倍数，记作 lcm(a,b)
例题描述
参考代码(C++版本)
#include <iostream> using namespace std; //欧几里得算法，亦称为辗转相除法 int gcd(int a,int b) { return b ? gcd(b, a%b):a; } int main() { int n; scanf("%d",&n); while(n--) { int a, b; scanf("%d%d",&a,&b); printf("%d\n",gcd(a,b)); } return 0; }
算法模板
通俗来说，就把b定为除数，只要它还能够进行除法运算，就把它抛到函数中，与a进行除法运算，所有欧几里得算法也叫辗转相除法。
总结
一、质数、约数、公约数、公倍数这些我们曾经学过的数学知识要清楚喔。后续质数的筛选、分解，约数的统计都是在这些基础知识上开展的。
二、对于数论的题，小伙伴假如把我之前写的图论的文章和这篇对比，应该可以很清楚的感受到，算法模板这块的内容不再是清爽的算法的执行流程了，取而代之的是一两行公式的代码或者公式的推导理解。
