WIKI
GCD
辗转相除法
整除 符号 |
例如 3|6
对于 a,b
我们用(a,b)表示 a,b 的最大公因数
我们让 a≥b
那么
a=bp+r
(a,b)=(bp+r,b)=(r,b)r<b
(a,b)=(b,r)
可以继续迭代,两次可以让 a 迭代到原先的一半以下
O(log(min{a,b}))
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
exgcd
a=bq1+r1b=r1q2+r2r1=r2q3+r3…rk−1=rkqk+1+rk+1rk=rk+1qk+2+rk+2
rk+2=0rk+1=(a,b)
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) return x = 1, y = 0, a;
int x1, y1, gcd;
gcd = exgcd(b, a % b, x1, y1);
x = y1, y = x1 - a / b * y1;
}