比较基础的GCD与LCM

最简单的gcd算法:
int gcd( int a, int b)
{
    if(a<b)swap(a,b);
    if(b==0) return a;
    else  return gcd(b,a%b);
}
最常用的gcd算法:
int gcd(int a,int b){return a==0?b:gcd(b%a,a);}
经过优化的gcd算法(分奇偶数):
 1 int gcd(int x,int y)
 2 {
 3     if(x<y) return gcd(y,x);//大数放在前面
 4     if(y==0) return x;
 5     else{
 6         if(!(x%2)){
 7             if(!(y%2))
 8                 return 2*gcd(x>>1,y>>1);//x,y皆为偶数
 9             else
10                 return gcd(x>>1,y);//x为偶数,y是奇数
11         }else
12         {
13             if(!(y%2))
14                 return gcd(x,y>>1);//x是奇数,y是偶数
15             else
16                 return gcd(y,x-y);//x,y都是奇数
17         }
18     }
19 }
最简单的LCM算法:
int lcm( int a, int b)
{
    return a/gcd(a,b)*b;//先除后乘防止超范围
}

一些很基础的东西

上一篇:POJ2429--GCD & LCM Inverse (UNSOLVED)


下一篇:算法训练 最大最小公倍数