最大公约数定义:若d是自然数a，b的约数，则称d为a，b的公约数。在所有公约数最大的数字则称其为a，b的最大公约数，记为gcd(a,b)。
最小公倍数定义:若m是自然数a，b的倍数，则称d为a，b的公倍数。在所有公倍数最小的数字则称其为a，b的最小公倍数，记为lcm(a,b)。
最大公约数求法
- 枚举法。时间复杂度O（min(a,b)）。其实可以用短除法优化（觉得实现后应该会有一定优化吧）。
- 欧几里得算法
欧几里得算法指出$forall a,b in N,b eq 0 ,gcd(a,b)=gcd(b,a mod b) $
证明:
若 a < b ,则gcd(b,a mod b)=gcd(b,a)=gcd(a,b) 显然成立
$ quad $ 若(a ge b) ，设a=q*b+r,(0 le r <b) ，所以r=a mod b,对于a，b的任意公约数d，都有(d | a,d|q*b),所以(d|(a-q*b),所以d|r)。
证毕
所以d也是b和r的公约数，反之亦然。故a，b的公约数集合也是b和a mod b的公约数集合。
递归形式
inline int gcd(int a,int b){
return b?gcd(b,a%b) :a;
}
迭代形式(C++库里自带的gcd就是这个，以前忘记怎么写经常copy这个)
inline int gcd(int a, int b) {
int r;
while(b) {
r = a % b;
a = b;
b = r;
}
return a;
}
位运算优化法（Get from the Internet，I have not tested it，maybe Boom！）
int gcd(int a, int b) {
while(b ^= a ^= b ^= a %= b);
return a;
}
时间复杂度O（log(a+b)),当a，b是斐波拉契数时会达到上界。但是高精度取模比较慢，更适合用下一个方法：更相损减术。
- 更相减损术
看看下面两个式子
我们可以这样证明:对于a,b的任意公约数d，都有(d|a,d|b),所以(d|(a-b))。所以d也是b和(a-b)的公约数，d也是a和（a-b)的公约数。
模板
迭代形式
inline int gcd(int a,int b){
while(a!=b){
if(a>b) a-=b;
else b-=a
}
return a;
}
递归形式（不推荐。。如果a，b相差过大，会导致堆栈溢出。。如果你扩栈了当我没说)
inline int gcd(int a,int b){
if(a==b)return a;
else if(a>b)a-=b;
else b-=a;
return gcd(a,b);
}
但是这样的时间复杂度为O（n),在高精度运算中不可接受。我们可以利用gcd的另外一些性质进行优化
证明
若d是a，b的公因子，则d | a,d|b。 而根据扩展欧几里得知识，可以知道 存在ax+by=gcd(a,b)所以d|(ax+by)，所以d|gcd(a,b)。所以a,b的所有公因子都是gcd(a,b)的因子 所以可以利用性质3来求gcd
通过以上性质,我们可以将更相损减术的复杂度优化至为(O(log_2 n))
证毕
关于这个的板子，有个板子题，是scoi2009 的supergcd，可以在我博客搜索一下
与欧几里得算法主要差别是一个是除法，一个是减法。前者用除法优化了后者的减法罢了。。减法容易退化O（n),但是本质并无差别
- stein算法，有兴趣的可以看看，感觉用处不大还麻烦。。
最小公倍数求法
定理
证明：
设d为gcd(a,b),(a_0=a/d,b_0=b/d) ,显然(gcd(a_0,b_0)=1,所以a_0 与b_0 互质) ，而lcm(a,b)=(a_0 *b_0)
(所以lcm(a,b)=lcm(a_0*d,b_0*d)=lcm(a_0,b_0)*d=a_0*b_0*d=a*b/d)
证毕
有了这条定理就可以先求出gcd再求出lcm了。
性质
-
若gcd(a,b)=1,那么a，b两数互质。
-
gcd(a,2a)=a;
-
gcd(a,0)=a;
-
gcd(a,b)=gcd(-a,b)=gcd(a,-b)=gcd(-a,-b);
-
gcd(n,n+1)=1;//这个可以证明素数的个数是无穷的
-
区间gcd种类最多(log_2 n)种，因为从gcd(l,l+1）开始向r推，gcd是单调不严格递减的，每次减少，最少/2（每次少一个因子，这个因子最小是2）
//这些貌似无关紧要，了解下就行