gcd（欧几里德算法）以及lcm——

gcd（欧几里德算法又称辗转相除法）求最大公约数

设 a = q * b + r，（a,b,q,r都是整数）gcd（a，b）=gcd（b,r）, 由此可以推出gcd( a, b )=gcd( a, a%b )

板子

int gcd（int a，int b ） //a>=b

{

if（b==0）return 0；

else return gcd (b, a%b);

}

egcd

lcm

lcm（a，b）=a * b / gcd（a，b）