GCD的一個(gè)性質(zhì)

$$GCD(a,b)=GCD(a?b,b)$$

• 這是輾轉(zhuǎn)相除法和輾轉(zhuǎn)相模法的依據(jù)
• 沒(méi)有想到這個(gè)性質(zhì)所以想了好久,最后就去看題解了
• 我…

證明

$$\begin{gathered} g:=\gcd (a,b),k_a:=a/g,k_b:=b/g(\gcd (k_a,k_b)=1) \\ \because a=k_{a}g,b=k_{b}g \\ \therefore \gcd (a?b,b)=\gcd ((k_a?k_b)g,k_{b}g) \\ =\gcd (k_a?k_b,k_b)g \\ \text{assume?}h:=\gcd (k_a?k_b,k_b)=1 \\ \text{then?}(k_a?k_b)\mathrm{m}\mathrm{o}\mathrm{d}h=k_a\mathrm{m}\mathrm{o}\mathrm{d}h=0, \\ \text{and?}{k}_b\mathrm{m}\mathrm{o}\mathrm{d}h=0. \\ \text{then?}\gcd (k_a,k_b)>1 \\ \therefore \gcd (k_a?k_b,k_b)=1 \\ \therefore \gcd (a?b,b)=g \end{gathered}$$

• 英語(yǔ)不好,證明也比較復(fù)雜,但應(yīng)該是對(duì)的.

推廣

$$\underset{i=1}{\overset{n}{\gcd }}{a}_i=\gcd (a_1,\underset{i=2}{\overset{n}{\gcd }}{a}_i+(k_a?a_1))$$
例題 codeforces 1459C

總結(jié)

以上是生活随笔為你收集整理的GCD的一个性质的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。