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