gcd与exgcd

gcd

\(a,b\)为不为零的整数，\(c\)满足\(c \mid a\)且\(c \mid b\)的最大整数

那么c为a，b的最大公约数，c = gcd(a, b)

令\(a=p_1^{a_1} p_2^{a_2}......p_n^{a_n} , b = p_1^{b_1} p_2^{b_2}......p_n^{b_n}\)

那么\(gcd(a, b) = p_1^{min(a_1, b_1)}p_2^{min(a_2, b_2)}......p_n^{min(a_n, b_n)}\)

用\((a, b)\) 表示\(gcd(a, b)\)

性质

\((a, a) = (0, a) = a\)

若\(a \mid b , (a, b) = a\)

\((a, b) = (a, a + b) = (a, ka + b)\)

\((ka, kb) = k(a, b)\)

\((a, b, c) = ((a, b), c)\)

代码求解gcd

根据上边这个性质我们可以推出

\(gcd(a, b) = gcd(a, b \% a )\)

证明

设: \(d\)为\(a\)与\(b\)的一个公约数, 则有\(d|b\)$\ \ $ \(d|a\)

设: \(a = k \times b + r\) 则有\(r = a \% b\)

\(r = a - kb\) 同除以\(d\)可得

\(r\over d\) \(=\) \(a\over d\) \(-\) \(kb\over d\)

又\(\because d|b , d|a\)

\(\therefore d | r\)

即 \(d | a\%b\), \(d\)为\(a\%b\)的一个因数.

又 \(\because d|b\)

\(\therefore d\) 为\(b\)与\(a\%b\)的一个公约数,

若\(d\)最大，则\(d\)为\(b\)与\(a\%b\)的最大公约数,

\(\therefore gcd(a, b) = gcd(b, a \% b)\) 得证

然后就可以递归求解gcd了

code

int gcd(int a, int b) {
	if (!b) return a;
	else return gcd(b, a % b);
}
           

[例] CF664 A Complicated GCD

求\(gcd(a, a + 1, a + 2. a + 3.... b) \ \ \ \ 1 \leq a \leq b \leq 10^{100}\)

\(\because gcd(a, a + 1) = 1\)

当\(a < b\)时,答案为\(1\)， 当\(a = b\) 时， 答案为\(a\)

exgcd

求出\(a*x+b*y=c\)（a，b，c为常量）的一组解，时间复杂度\(log(a)\)

证明：

\(a*x+b*y=c\) 有整数解的充要条件是\(c\)整除\(gcd(a,b)\)

设\(gcd(a,b)=p\)

1.充分性：

\(a*x+b*y=c\)

\(a'*p*x+b'*p*y=c(a'=a/p)\)

\(p(a'*x+b'*y)=c;\)

因为\(x,y\)必须为整数

所以\(c\)必须整除\(p\)

2.必要性

使用欧几里得和数学归纳法可证明

首先\(b*x_1+(a \% b)*y_1=c\),有整数解，

则\(a*x_2+b*y_2=c\)有整数解

\(a*x_2+b*y_2\)

\(=b*x_1+(a \% b)*y_1\)

\(=b*x_1+(a-\lfloor \frac{a}{b} \rfloor*b)*y_1\)

\(=a*y_1+b*(x_1-\lfloor \frac{a}{b} \rfloor*y_1)\)

然后就可以得到对应关系\(x_2=y_1,y_2=(1-\lfloor \frac{a}{b} \rfloor)*y_1\)；

显然最后的\(p,0\)有解

所以求这个\(a*x+b*y=c\)整数解的过程只需要不断递归运行到底层即可

最后一层\(p*x+0*y=c\)的解为\(x=\frac {c}{p},y=0\);

之后再不断用关系\(x_2=y_1,y_2=(x_1-\lfloor \frac{a}{b} \rfloor*y_1)\)推出上一层的解即可

void exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1, y = 0;
		return;
	}
	int q = a / b, r = a % b;
	exgcd(b, r, y, x);
	y -= q * x;
}