最大公约数
自然数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;
}
