今天刷蓝桥杯2021省赛路径那道题是最小公倍数不熟，就重新复习了一下，总结如下

最大公约数

欧几里得算法（辗转相除法） $O(NlogN)$

y总证明：

d能整除a,d能整除b==>d能整除xa+yb
a mod b=a-(a/b)b=a-cb
=>易证gcd(a,b)=acd(b,a-cb) 
=>gcd(a,b)=gcd(b,a mod b)

数学证明：

证明欧几里得算法，即gcd(a,b)=gcd(b,amodb),前提条件:
    a=md
    b=nd    =>d是a和b的最大公约数
    m和n互质
证明：
                        a=md1
    设gcd(a,b)=d1,则    b=nd1
                        m,n互质

    令a=qb+r
    则r=a−qb
       =md1-qnd1
       =(m-qn)d1
    要证明欧几里得算法，只需证明b和r的最大公因数等于d1即可
    由上述过程可得，d1可以被r整除，即d1是r和b的公约数。
    因此只需要证明n和m−qn互质即可。
    下面用反证法来证明：
        假设n与m−qn不互质，设gcd(n,m−qn)=d2(d2>1)
                则有 n=xd2  m-qn=yd2
            即m=(qx+y)d2⇒m,n不互质，这与前提m,n互质相矛盾
            因此假设不成立,n和m−qn互质
            所有r和b的最大公约数为d1
            gcd(a,b)=gcd(b,a mod b)，命题得证

参考文献

辗转相除法， 又名欧几里德算法（Euclideanalgorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
————————————————
版权声明：本文为CSDN博主「慎铭」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_52828510/article/details/120997231

Python3 代码

def gcd(a,b):
    return gcd(b,a%b) if b else a

最小公倍数

欧几里得算法（辗转相除法） $O(n^2)$

最小公倍数可直接用最大公约数求得，如下：

定理：若求a,b的最小公倍数
    则先求a,b的最大公约数c
    再用ab/c即为a,b的最小公倍数

Python3 代码

def lcm(a,b):
    if a<b:   
        a,b=b,a
    c,d=a,b 
    while d!=0:
        c,d=d,c%d
    return (a*b)//c # //结果为整数，/结果保留到小数点后一位