学习笔记——数论——约数
1.d/n 等价于n%d==0.
2.一个整数N的约数个数的上界为.
3.1-N 每个数的约数个数综合大约为N * log N 个。
4.1-1e9中的数，约数个数最多的数仅有1536个约数
倍数法求1-N中所有数的约数集合：NlogN
void gao()
{
vectorfactor[M];
for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)v[j].push_back(i);
}
数论分块：
k/i (1<=i<=n)
L,R每块的范围，x每块k/i的取值
for(int L=1,R;L<=n;L=R+1)
{
R=min(n,k/L?k/(k/L):n);
ll x=k/L;
}
最大公约数：
1.gcd(a,b)*lcm(a,b)=a*b;
2. lcm(a*d,b*d)=lcm(a,b)*d;
3.gcd(a,b)=gcd(b,a-b)=gcd(a,a-b);更相减损术
4.gcd(2*a,2*b)=2*gcd(a,b);
5.gcd(a,b)=gcd(b,a%b);欧几里得算法
作者：夕林山寸
相关文章
Iris
2021-08-03
Valora
2021-02-16
Halima
2021-06-19
Kande
2023-05-13
Ula
2023-05-13
Jacinda
2023-05-13
Winona
2023-05-13
Fawn
2023-05-13
Echo
2023-05-13
Maha
2023-05-13
Kande
2023-05-15
Viridis
2023-05-17
Pandora
2023-07-07
Tallulah
2023-07-17
Janna
2023-07-20
Ophelia
2023-07-20
Natalia
2023-07-20
Irma
2023-07-20