目录
数学符号
整除与约数
最大公约数(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
向量中。