1）求最大公约数
int gcd(int a,int b)
{if(b==0) return a;return gcd(b,a%b);
} 2）求最小公倍数
int lcm(int a,int b)
{return a*b/gcd(a,b);
}3）扩展欧几里得算法
求 ax+by=c的方程的解：
先求出ax+by=gcd(a,b) 的一个解(x,y) ，为求出这个解，要找出一个递推式，如下：
根据ax+by=gcd(a,b) <=> bx+(a%b)y = gcd(a,b) 有整数解(x1,y1)，且 x = y1, y = x1-[a/b]*y1
证明：因为a-b*[a/b]=a%b ,将x，y带入方程就是原式子了
那么可以写出程序：
int gcdEx(int a,int b,int& x,int& y)
{ //求ax+by=gcd(a,b) 的整数解 返回gcd(a,b); if(b==0) {x=1; y=0; return a;}int x1,y1;int gcd=gcdEx(b,a%b,x1,y1);x=y1;y=x1-a/b*y1;return gcd;
}求出ax+by=gcd(a,b) 的一个解(x,y) 后，就可以求ax+by=c了
但首先要符合：ax+by=c 有解的充要条件是 gcd(a,b)|c 即c可以整除gcd(a,b)
设 d= gcd(a,b) ,k=c/d;
若ax+by = d的解是 (x1,y1) 则 ax+by = c的解集是： x = k*x1 + t*(b/d) y = k*y1 – t*(a/d) t为任意整数
4)扩展欧几里得算法求ax ≡ c(mod b)
ax≡c(mod b)等价于ax+by=c，所以问题就转化为方程中求x的值
设 d = gcd(a,b), k = c/d， ax+by = d的解是 (x1,y1) 则
上式中 x = k*x1 + t*(b/d) t为任意整数
其中解一共有d个
所以 t=0~(d-1)
其中ax ≡ c(mod b) 的最小非负整数解：
设s=b/d;
所以答案就是 x = (k*x1%s + s) % s