姓名： 王薪宇
赛道： 普及
类型： 算法技能
【GCD与素数筛总结】
今天学的东西不是特别难，但还是记录一下学的知识 
。
1. GCD
- GCD定义
GCD即最大公约数，一般记m,n的GCD为 \gcd(m,n) 。
数学定义：若 g|m,g|n 且g最大，则称 g 为 \gcd(m,n) 。
集合定义：若 M 为数 m 的约数集合， N 为 n 的约数集合， G 为 \gcd(m,n) 的约数集合，则有 G=M \cap N 。
质因数分解定义：设 m=a_1^{k_1}·a_2^{k_2}·...·a_n^{k_n},n=a_1^{c_1}·a_2^{c_2}·...·a_n^{c_n}(k,c\ge 0),则 \gcd(m,n)=a_1^{\min(k_1,c_1)}·a_2^{min(k_2,c_2)}·...·a_n^{\min(k_n,c_n)} 。 - GCD求解
可用欧几里得算法（辗转相除法）求解
具体来说，就是如果记 r=m-kn (相当于 r = m \mod n , k 为常数),则有 \gcd(m,n)=\gcd(n,r)
证明：
如果记 \gcd(m,n)=\gcd(n,r)=g ，则 g|m,g|kn ,因此 g|(m-kn) 。由于 r=m-kn,所以我们可以得到 g|r 。由于 g|n,g|r,所以 gcd(n,r)=g=gcd(m,n),证毕。
代码：
int gcd(int x,int y) {
if(y == 0) return x;
return gcd(y,x % y);
}
时间复杂度 O(\log n) ，空间复杂度 O(1) 。
2. 质数筛
- 埃氏筛
主要思路就是“质数的倍数是合数”。记 np_i 表示 i 是否为合数，每次当 np_i=0 时，将 i 塞入答案数组，同时将 i 的倍数标记为合数。
代码：
int n;
bool np[N];
vector<int> prime;
int main() {
……
for(int i = 2;i <= n;i++) {
if(!np[i]) {
prime.push_back(i);
for(int j = 2;j*i <= n;j++) {
np[j*i] = 1;
}
}
}
……
}
时间复杂度 O(n \log\log n) ，空间复杂度 O(n) 。
- 线性筛
埃氏筛虽然已经足够快了（ \log\log n 可以当常数），但还有一些优化空间。
我们可以注意到，在埃氏筛中，有亿些合数被重复标记，很浪费时间。我们可以让每个合数被自己最小的质因数筛掉，这样可以把复杂度降到线性。
int n;
bool np[N];
vector<int> prime;
int main() {
……
for(int i = 2;i <= n;i++) {
if(!np[i]]) {
prime.push_back(i);
}
for(int j : prime) {
if(j*i>n) break;
np[j*i] = 1;
if(i%j==0) break;
// 由于 prime 里面质数是从小到大的
//所以 i 乘上其他的质数的结果一定会被
// j 的倍数筛掉，就不需要在这里先筛一次
// 所以这里直接 break掉就好了
}
}
……
}
时间复杂度 O(n) ，空间复杂度 O(n) 。
（这玩意还能求很多积性函数值，这个以后再说。）
写总结不易，望大佬点赞 
，谢谢！
参考文献：信友队课件，OI-wiki
