求最小公倍数更简单的算法

有味发布于 2010-04-03 20:18， 656 次点击

这是在judgeolineshang做的一道题，不过超时了
一下是程序#include<iostream>
using namespace std;
int main(){
    int N,a,b;
    cin>>N;
    while(N--){
        cin>>a>>b;
        int m,n,i;
        if(a>b)
          {m=a;n=b;}
        else
          {m=b;n=a;}
        for(i=1;i<=n;i++){
            if((m*i)%n==0){
            cout<<m*i;
            break;
                }
             }
           }
      return 0;
    }  请各位指点，更简单的算法。

6 回复

有味2010-04-03 20:19

请各位多提提意见，我也能好好学习学习

书呆2010-04-03 21:05

程序代码：

#include <iostream>
using namespace std;

// 辗转相除法求最大公约数
int gcd(int a, int b)
{
    int temp;
    if (a==0) return b;
    if (b==0) return a;
    if (a<b)
        a^=b^=a^=b;
    while (b)
    {
        temp = a%b;
        a = b;
        b = temp;
    }
    return a;
}

int main(void)
{
    int N,a,b;
    cin>>N;
    while(N--)
    {
        cin>>a>>b;
        cout<<a*b/gcd(a,b)<<endl;
    }
    return 0;
}

yyblackyy2010-04-03 21:54

LS说的不错，两个数的最小公倍数等于这两数的乘积除以这两个数最大公约数

写出最大公约数的算法两数乘积除以他的返回值（最大公约数函数）就OK了

有味2010-04-05 00:16

回复 3楼书呆

能不能帮我分析// 辗转相除法求最大公约数啊

初学者。。。。

lyb1512010-04-05 09:36

不太清楚，不过学习了。。。。

月光3212010-04-05 11:06

a^=b^=a^=b;
与两数交换有什么不同啊？