最大公约数

自然数d同时是a,b的约数，称d是a和b的公约数，d是a和b的公约数中最大的一个，d就是最大公约数，记作。
自然数m同时是a，b的倍数，称m是公倍数。m是所有公倍数中最小的数，那么m就是最小公倍数记作。
定理：都有
证明：
更相减损术：
有

证明：d是a，b的任意约数，那么所以所以这三个集合的公约数集合相等。
欧几里得算法：
,
证明：若a<b,
若a>=b,令其中显然r是。对于a，b任意公约数d。所以因此d也是r的约数。
更相减损法面对特殊数据会非常慢。
更相减损法

int gcd(int a,int b){
    if(a==0||b==0)return max(a,b);
    while(a!=b){
        if(a>b)a-=b;
        else b-=a;
    }
    return a;
}

欧几里得算法

int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}