gcd和lcm 居然忘掉了这个。。

/*==================================================*\ 
| GCD 最大公约数 
\*==================================================*/ 
int gcd(int x, int y)
{ 
    if (!x || !y) return x > y ? x : y; 
    for (int t; t = x % y; x = y, y = t); 
    return y; 
} 
/*==================================================*\ 
| 快速 GCD 
\*==================================================*/ 
int kgcd(int a, int b)
{ 
    if (a == 0) return b; 
    if (b == 0) return a; 
    if (!(a & 1) && !(b & 1)) 
        return kgcd(a>>1, b>>1)<<1;
    else if (!(b & 1))
    return kgcd(a, b>>1); 
    else if (!(a & 1)) return kgcd(a>>1, b); 
    else return kgcd(abs(a - b), min(a, b)); 
} 
/*==================================================*\ 
| 扩展 GCD  
| 求x, y使得gcd(a, b) = a * x + b * y;  
\*==================================================*/ 
int extgcd(int a, int b, int & x, int & y)
{ 
    if (b == 0) { x=1; y=0; return a; } 
    int d = extgcd(b, a % b, x, y); 
    int t = x; x = y; y = t - a / b * y; 
    return d; 
} 

以上代码转自兔子的算法集中营。
lcm只需lcm=a/gcd(a,b)*b即可
至于求一组数的gcd和lcm
可以先求两个数的,在用求出的gcd与第三个数求gcd,以此类推,代码样例:

  for(j=1;j<=m-1;j++)
  {
    s[j+1]=lcm(s[j],s[j+1]);    //将两个数的lcm存放在较大位置那个元素中
  }

欧几里得算法的通俗描述:
两个数a、b ,用较大的数除以较小的数取余,用余数更新较大的数,对新生成的a、b循环执行上述过程直至相除为0。此时较小的数就是两个数的gcd,这样lcm也可得到。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>