证明:辗转相除法求$a$, $b$最小公约数的正确性
推广一下蒟蒻的Blog
1.设$gcd(a, b)$为$a$, $b$最小公约数
2.设 $p=a/b$,$q=a$%$b$
3.有$a = b * p + q$
4.$a$ 定能被 $gcd(b, q)$ 整除,且$gcd(b, q)$为其最大公约数 (慢慢想)
5.即$gcd(a, b) == gcd(b, a $%$ b)$
6.求得$gcd(b, a $%$ b)$即可
7.同理:$gcd(b, a $%$ b) == gcd(a $%$ b, b $%$(a $%$ b))$ (有点绕慢慢想)
8.终止条件:当$gcd(a, b)$中的$b == 0$,则$gcd(a, b) == a$
未简化Code:
inline int gcd(int a, int b){
if(b) return gcd(b, a % b);
return a;
}
三目运算符$+long long$究极宇宙无敌简化版Code:
inline LL gcd(LL a, LL b){
return b ? gcd(b, a % b) : a;
}
//LL是long long
