最大公约数（二进制算法）

1 2 3 4 5 6 7 8 9 10 11 12 13 14

inline int GCD(int x,int y) { int i,j; if(x==0) return y; if(y==0) return x; for(i=0;0==(x&1);++i)x>>=1; // 去掉所有的 2 for(j=0;0==(y&1);++j)y>>=1; // 去掉所有的 2 if(j<i) i=j; while(1){ if(x<y)x^=y,y^=x,x^=y; // 若 x < y 交换 x, y if(0==(x-=y)) return y<<i; // 若 x == y， gcd == x == y （就是在辗转减，while(1) 控制） while(0==(x&1))x>>=1; // 去掉所有的 2 } }

1 2 3 4 5 6 7 8 9 10 11 12

int get_lcm(int a,int b)///获得最小公倍数 { int x=a; int y=b; while(b) { int t=a; a=b; b=t%b; } return x/a*y; }