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;
}