目录
数学符号
整除与约数
最大公约数（gcd)和最小公倍数（lcm)
质数 (素数)
算术基本定理（唯一分解定理）
约数个数
约数之和
分解质因数（枚举法）
试除法求约数（枚举法）
数学符号
x | y ：整除符号，表示 x 整除 y ，也就是 x 是 y 的约数，例如 2 | 4
整除与约数
设 a , b ∈ Z 且 a = 0 ，若 ∃ k ∈ Z 满足 b = k × a ，那称为 b 被 a 整除。记作 a | b ，否
则 a ∤ b
• 若 a | b ，则 b 是 a 的倍数， a 是 b 的约数。
最大公约数（gcd)和最小公倍数（lcm)
欧几里得算法
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}#include<iostream>
using namespace std;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {int c = gcd(a, b);return a * b / c;
}
int main() {int a, b;while (cin >> a >> b) {cout<< lcm(a, b) << endl;}return 0;
}
质数 (素数)
质数 ( 素数 ) ，是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他约数的自然数。
试除法判定质数
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;
}- 首先，定义了一个
unordered_map<int, int> p用于存储不同质因数及其出现的次数。 - 读入整数
n，表示接下来要处理n个数字。 - 在
while(n --)循环中：- 读入每个数字
x。 - 通过
for循环从2到x的平方根，检查每个数i是否能整除x。如果能整除，就增加质因数i在p中的计数，并不断用x除以i，直到x不能再被i整除。 - 如果经过上述循环后
x仍然大于1，说明x本身就是一个质因数，增加其在p中的计数。
- 读入每个数字
- 计算最终的结果
ans，通过遍历p中的每个质因数及其计数，将每个质因数的计数加1后相乘，并对结果取模mod。 - 输出结果
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;
}- 在
main函数中，首先读取一个整数n，表示接下来要处理n个输入的数。 - 定义了一个
unordered_map<int, int> p来存储每个质因数及其出现的次数。 - 进入
while (n --)循环，每次循环处理一个输入的数x：- 从 2 到
x的平方根进行遍历，如果x能被i整除，就不断将p[i]的计数加 1，并将x除以i，直到x不能再被i整除。 - 如果经过上述循环后
x仍然大于 1，说明x本身就是一个质因数，将其在p中的计数加 1 。
- 从 2 到
- 然后，通过遍历
p中的每个质因数及其计数：- 对于每个质因数
a和其计数b，初始化一个变量cnt为 1 。 - 通过一个内层循环，每次将
cnt更新为(cnt * a + 1) % mod，循环b次。 - 将当前计算得到的
cnt与res相乘，并对结果取模mod，更新res的值。
- 对于每个质因数
- 最后，输出计算得到的最终结果
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向量中。
