对于两个数的最大公约数 gcd(m, n),有
m<n 时,gcd(m, n)=gcd(n, m)
m 偶 n 偶时,gcd(m, n)=2*gcd(m/2, n/2)
m 偶 n 奇时,gcd(m, n)=gcd(m/2, n)
m 奇 n 偶时,gcd(m, n)=gcd(m, n/2)
m 奇 n 奇时,gcd(m, n)=gcd(n, m-n)
采用递归即可。
2 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
inlineintGCD(intx,inty){inti,j;if(x==0)returny;if(y==0)returnx;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))returny<<i;// 若 x == y,gcd == x == y(就是在辗转减,while(1) 控制)
while(0==(x&1))x>>=1;// 去掉所有的 2
}}