gcd
$ gcd(a,b) $ 表示a与b的最大公约数。here
gcd 证明
设有 $ gcd(a,b)=d(a>b) $ ,则 $ d|a $ 、$ d|b $(也就是d既是a的因数也是b的因数)。
设有 $ k=\lfloor\frac{a}{b}\rfloor $ 、 $ r=a \mod b $,则 $ a=bk+r $。
举个栗子,因为 $ a = 5b+1 = 5 \times 2+1 = 11 $ ,则
\[\begin{cases} k=5\\ r=1 \end{cases} \]因为 $ d|b $,所以 $ d|kb $(请感性理解)
因为 $ d|kb+r $ (也就是 $ d|a $ )
所以 $ d|r $ (kb是d的倍数,kb+r也是d的倍数,那么r也就是d的倍数了)
上面整理一下就是 $ d|b $ 且 $ d|r $
所以 $ gcd(b,r)=d $ 了……吗?
并不是,为什么呢?假设有 $ 5|20;5|10 $ 但 $ gcd(20,10)\neq5=10 $,所以是 $ gcd(b,r) \geq d $。
我们希望能证明 $ gcd(a,b)=gcd(b,r)=gcd(b,a\mod b) $
所以我们用反证法去证$ gcd(b,r)>d $是不存在的。
反证$ gcd(b,r)>d $是不存在的
设有 $ gcd(b,r)=D>d $,则 $ D|b $ 且 $ D|r $,所以 $ D|kb $。(这里和上面差不多)
因为 $ D|kb $ 而且 $ D|r $,所以 $ D|kb+r $ (转换一下得 $ D|a $ )。现在我们有了 $ D|a $ $ D|b $ ,所以 $ gcd(a,b) \geq D $。
根据最开始说 $ gcd(a,b)=d $ ,所以 $ gcd(a,b)=d \geq D $ ,与 \(D>d\) 矛盾了。
故只有 \(D=d\) 时该假设成立,即 \(gcd(b,r)=d\)
所以\(gcd(a,b)=gcd(b,r)=d\)
化简一下就可以完结撒花: \(gcd(a,b)=gcd(b,a\mod b)\)
……了吗?
我们要设定一个限制条件,即 \(gcd(a,0)=a\)
为什么一定是\(gcd(a,0)=a\)
倒推上去
\(gcd(ak,a)=gcd(a,0)\)
此时ak与a的最大公约数即为a,故\(gcd(a,0)=a\)
最终就有:
\[gcd(a,b) = \begin{cases} a &\text{如果} b=0\\ gcd(b,a\mod b) &\text{如果} b\neq 0 \end{cases} \]gcd 代码
template<typename T>
T gcd(T a,T b){
if(b==0) return a;
return gcd(b,a%b);
}
标签:kb,geq,gcd,所以,证明,cases,mod
From: https://www.cnblogs.com/znpdco/p/17424447.html