证明:辗转相除法求$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

点个收藏点个赞吧，球球了 (逃