(Hugecolor{Red}{10.18}) (Large{color{Blake}{主题：约数}})
主要内容：
.整除
-
(a=b imes c)，则称(a)被(b)整除，或(b)整除(a)，记作(amid b)。
-
(a=qb+r,(0le r< left| b ight|))，记(r=amod b)。
-
整除的性质：
- 若(a|b)且(a|c)，则(forall x,y)，有(a|xb+yc)。
- 若(a|b)且(b|c)，则(a|c)。
- 设(m e0)，则(a|b)，当且仅当(ma|mb)。
- 若(a|b)且(b|a)，则(a=pm b)。
.约数
- 算数基本定理的推论
对于正整数N......
- N的正约数集合：
[{{p_1^{b_1}p_2^{b_1}...p_m^{b_m}}}
]
- N的正约数个数：
[prodlimits_{i=1}^m(c_i+1)
]
- N的所有正约数的和：
[prodlimits_{i=1}^mleft(sumlimits_{j=0}^{c_i}(p_i^j)
ight)
]
- 求N的正约数集合——试除法：
- 扫描(d=1simsqrt{N})尝试是否(d|N)，若能，则(d)与(N/d)都是N的约数。复杂度：(O(sqrt{N}))。
- 试除法的推论
- 一个整数N的约数上限个数为(2 sqrt{N})。
- 求(1sim{N})每个数的正约数集合——倍数法
- (forall d,1 sim N)中以(d)为约数的数就是(d,2d,3d,...,leftlfloor{N/d} imes d ight floor)。
- 时间复杂度：(O(NlogN))。
Code：
vector<int>factor[500010]
for(int i=1;i<=n;i++)
for(inr j=1;i*j<=n;j++)
factor[i*j].push_back(i);
for(int i=1;i<=n;i++)
{
for(int j=0;j<factor[i].size;k++)
printf("%d",factor[i][j]);
puts(" ");
}
- 倍数法的推论：
- (1sim N)每个数的约数个数的总和大约为(NlogN)。
例题：P1463 [POI2002][HAOI2007]反素数
.最大公约数与最小公倍数
性质：
- 若(a|m)，(b|m)，则(operatorname{lcm}(a,b)|m)。
- 若(d|a)，(b|m)，则(d|gcd(a,b))。
- (operatorname{lcm}(ma,mb)=m imesoperatorname{lcm}(a,b)).
- (mathcal{color{Red}{important}})
[a imes b=gcd(a,b) imes operatorname{lcm}(a,b)
]
可用此条性质求出(gcd(a,b))后用(a imes b/gcd(a,b))求(operatorname{lcm}(a,b))。
.最大公约数的求法
方法一：用唯一分解定理
先分解质因数，然后求最大公约数。
令：
[a=p_1^a1 imes p_2^a2 imes... imes p_m^am
]
[b=p_1^b1 imes p_2^b2 imes... imes p_m^bm
]
则
[gcd(a,b)=p_1^{min(a1,b1)} imes p_2^{min(a2,b2)} imes... imes p_m^{min(am,bm)}
]
方法二：九章算术·更相减损术
(forall a,bin N,age b,)有(gcd(a,b)=gcd(b,a-b)=gcd(a,a-b))
(forall a,bin N,)有(gcd(2a,2b)=2 imes gcd(a,b))
方法三：欧几里得算法
(mathcal{color{Red}{important}})
[forall a,bin N,b
e 0,gcd(a,b)=gcd(b,amod b)
]
Code:
int gcd(int a,int b)
{
return (b==0)?a:gcd(b,a%b);
}
方法四：二进制算法
若(a=b,gcd(a,b)=a;)否则，分情况讨论
- (a)和(b)均为偶数，(gcd(a,b)=2 imes gcd(a/2,b/2);)
- (a)为偶数，(b)为奇数(gcd(a,b)=gcd(a/2,b);)
- (b)为偶数，(a)为奇数(gcd(a,b)=gcd(a,b/2);)
内心戏：
没啥捷径。记好结论多推推公式才有正解。
高精冲冲冲！
这玩意儿太难写了。一百多行。以后再也不写了