本博客源自我的洛谷博客
https://www.luogu.com.cn/article/1jy3ro0r
（现在改成专栏了），写作时间 2021-08-15 23:18
$a$ 是 $b$ 的约数 $\iff a\,|\,b$
$x$ 是 $a_1,a_2,…,a_i,…,a_n$ 的公约数 $\iff$
$x$ 是 $a_1,a_2,…,a_i,…,a_n$ 中所有数的约数
特别的：$x$ 是 $a$，$b$ 的公约数 $\iff x\,|\,a\;\And x\,|\,b$
一组整数的最大公约数，是指所有公约数里面最大的一个，记为 $\gcd(…)$ 。
两个数的最大公约数
欧几里得算法
指路
，复杂度 $O(\log n)$
欧几里得优化 -> Stein算法
已知 $a,b$，求 $\gcd(a,b)$
先把 $a,b$ 都变成奇数，记录 $a,b$ 中含有多少公共的 2，最后乘回来。
类似欧几里得算法进行辗转相减/相除，此过程中得到的 $a,b$ 可以放心的除以 2。
代码实现
- 欧几里得 - 最朴素的递归
1
2
3
| int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
|
- 欧几里得 - 不用递归
1
2
3
4
| int gcd(int a,int b){
if(b) while((a%=b)&&(b%=a));
return a+b;
}
|
- Stein算法 - 非位运算版
1
2
3
4
5
6
7
8
| int gcd(int a,int b){ int c=0;
if(a==0||b==0) return a+b;
while(a%2==0&&b%2==0){a/=2;b/=2;c++;}
while(a%2==0)a/=2; while(b%2==0)b/=2;
if(a<b) swap(a,b);
while(a%=b){while(a%2==0)a/=2;if(a<b)swap(a,b);} //此处括号中a%=b 可以换为 a=(a-b)/2，但亲测int下换了会变慢一点点
return b<<c;
}
|
- Stein算法 - 位运算版
int 下，改成位运算并不能使代码变快，反而使代码更长，可读性更差，不建议使用。
但倘若想求高精$\gcd$，且写了 $2^k$ 压一位的高精模板的话，也许比非位运算版能快一些。
1
2
3
4
5
6
7
8
| int gcd(int a,int b){int c=0;
if(a==0)return b;if(b==0)return a;
while((!(a&1))&&(!(b&1))){a>>=1;b>>=1;c++;}
while((!(a&1)))a>>=1; while((!(b&1)))b>>=1;
if(a<b) swap(a,b);
while(a=((a-b)>>1)){while((!(a&1)))a>>=1;if(a<b)swap(a,b);}//用高精的话换了快
return b<<c;
}
|