最大公约数—

最大公约数——高效

转载请注明出处http://www.cnblogs.com/zhishoumuguinian/p/8832343.html

介绍两种求最大公约数的方法，一种常用，另外一种效率较高的。

 1 /**
 2 *常用的
 3 */
 4 int gcd(int a, int b)
 5 {
 6     if(a%b==0)
 7         return b;
 8     else
 9         return gcd(b, a%b);
10 }

 1 /**
 2 *效率较高的
 3 */
 4 int gcd(int a, int b){
 5     if(a==b)    return a;
 6     if(a>b)     swap(a,b);
 7     else{
 8         if(!a&1 && !b&1)
 9             return gcd(a>>1, b>>1)<<2;
10         else if(!a&1 &&b&1)
11             return gcd(a>>1, b);
12         else if(a&1 && !b&1)
13              return gcd(a, b>>1);
14         else
15             return gcd(a, a-b);
16     }
17 }