数论基础知识（上）

bool isPrime(int n) { if (n < 2) { return false; } for (int i = 2; i * i <= n; i ++) { if (n % i == 0) { return false; } } return true; }

算术基本定理（唯一分解定理）

推论——约数个数和约数之和

约数个数

#include <iostream> #include <unordered_map> using namespace std; const int mod = 1e9 + 7; int main() { unordered_map<int, int> p; int n; cin >> n; while(n --) { int x; cin >> x; for(int i = 2; i <= x / i; i ++) while(x % i == 0) p[i] ++, x /= i; if(x > 1) p[x] ++; } int ans = 1; for(auto i : p) ans = (long long)ans * (i.second + 1) % mod; cout << ans <<endl; return 0; }

1. 首先，定义了一个 unordered_map<int, int> p 用于存储不同质因数及其出现的次数。
2. 读入整数 n ，表示接下来要处理 n 个数字。
3. 在 while(n --) 循环中：
   • 读入每个数字 x 。
   • 通过 for 循环从 2 到 x 的平方根，检查每个数 i 是否能整除 x 。如果能整除，就增加质因数 i 在 p 中的计数，并不断用 x 除以 i ，直到 x 不能再被 i 整除。
   • 如果经过上述循环后 x 仍然大于 1 ，说明 x 本身就是一个质因数，增加其在 p 中的计数。
4. 计算最终的结果 ans ，通过遍历 p 中的每个质因数及其计数，将每个质因数的计数加 1 后相乘，并对结果取模 mod 。
5. 输出结果 ans 并结束程序。

约数之和

#include <iostream> #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> p; while(n --) { int x; cin >> x; for(int i = 2; i <= x / i; i ++) while( x % i == 0) p[i] ++, x /= i; if(x > 1) p[x] ++; } int res = 1; for(auto i : p) { LL a = i.first, b = i.second, cnt = 1; while(b --) cnt = (long long)(cnt * a + 1) % mod; res = (long long)res * cnt % mod; } cout << res << endl; return 0; }

1. 在 main 函数中，首先读取一个整数 n ，表示接下来要处理 n 个输入的数。
2. 定义了一个 unordered_map<int, int> p 来存储每个质因数及其出现的次数。
3. 进入 while (n --) 循环，每次循环处理一个输入的数 x ：
   • 从 2 到 x 的平方根进行遍历，如果 x 能被 i 整除，就不断将 p[i] 的计数加 1，并将 x 除以 i ，直到 x 不能再被 i 整除。
   • 如果经过上述循环后 x 仍然大于 1，说明 x 本身就是一个质因数，将其在 p 中的计数加 1 。
4. 然后，通过遍历 p 中的每个质因数及其计数：
   • 对于每个质因数 a 和其计数 b ，初始化一个变量 cnt 为 1 。
   • 通过一个内层循环，每次将 cnt 更新为 (cnt * a + 1) % mod ，循环 b 次。
   • 将当前计算得到的 cnt 与 res 相乘，并对结果取模 mod ，更新 res 的值。
5. 最后，输出计算得到的最终结果 res 并结束程序。

分解质因数（枚举法）

for (int i = 2; i * i <= n; i ++) { if (n % i == 0) { int cnt = 0; while (n % i == 0) { n /= i, cnt ++; } factor.push_back({i, cnt}); } } if (n > 1) { factor.push_back({n, 1}); }

• for (int i = 2; i * i <= n; i ++) ：从 2 开始，到 n 的平方根为止进行循环。选择到平方根是因为，如果 n 有大于平方根的质因数，那么必然存在一个小于平方根的质因数与之对应，所以只需要检查到平方根就可以找出所有质因数。
• if (n % i == 0) ：如果 n 能被当前的 i 整除，说明 i 可能是 n 的一个质因数。
  • int cnt = 0; ：初始化一个计数器 cnt 为 0，用于记录当前质因数 i 的出现次数。
  • while (n % i == 0) ：通过这个内层循环，不断用 n 除以 i ，并增加计数器 cnt ，直到 n 不能再被 i 整除，从而确定质因数 i 在 n 的分解式中的指数。
  • factor.push_back({i, cnt}); ：将质因数 i 及其指数 cnt 作为一个对存储到 factor 容器中。
• if (n > 1) ：如果经过上述循环，n 仍然大于 1，说明此时 n 本身就是一个质因数，且指数为 1 。所以将 {n, 1} 存入 factor 容器。

试除法求约数（枚举法）

vector<int> factor; for (int i = 1; i * i <= n; i ++) { if (n % i == 0) { factor.push_back(i); if (n / i != i) { factor.push_back(n / i); } } }

找出整数 n 的所有因数，并将它们存储在 vector<int> factor 中。

• 外层的 for 循环从 1 开始到 n 的平方根。选择到平方根是因为对于一个数 n ，如果存在因数 i 小于等于 sqrt(n) ，那么必然存在另一个因数 n / i 大于等于 sqrt(n) ，所以只需要检查到平方根就能找出所有因数。
• 对于每个 i ，如果 n 能被 i 整除，说明 i 是 n 的一个因数，将 i 放入 factor 向量中。
• 然后检查 n / i 是否不等于 i 。如果不等，说明这是另一个不同于 i 的因数，也将其放入 factor 向量中。