泉州营销型网站设计/百度搜索引擎优化指南最新版

题目链接：Problem - 1108 (hdu.edu.cn)

Problem Description

给定两个正整数，计算这两个数的最小公倍数。

Input

输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.

Output

对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。

Sample Input

10 14

Sample Output

70

Source

POJ

解题过程及思路

此题第一次提交的时候,出现了 Wrong Answer。然后又看了一遍题目发现题目要求输入多组测试数据，所以在源代码基础之上再套一个循环，再将输入语句放至 while判断条件的括号里，就可以成功Accepted。

附上第一次提交的WA代码：

#include<iostream>
using namespace std;int main()
{int xiao,da,temp,t;cin>>xiao>>da;t=xiao*da;while(xiao!=0){temp=da%xiao;da=xiao;xiao=temp;}cout<<t/da<<endl;return 0;
}

这里说明一下：为了保证可以输入多组测试数据且避免出现死循环，因此可以使用如下3条语句（这3条语句是等价的任选其一即可）：

//while(scanf("%d%d",&a,&b)!=EOF){}
//while(scanf("%d%d",&a,&b)==2){}
//while(cin>>a>>b){}

1) 修改代码后先用暴力求法，AC代码如下：

#include<iostream>
using namespace std;int main()
{int a,b,i;//while(scanf("%d%d",&a,&b)!=EOF)//while(scanf("%d%d",&a,&b)==2)while(cin>>a>>b){for(i=a;;i++){if(i%a==0 && i%b==0){cout<<i<<endl;break; }}}return 0;
}

其实这里可以采用枚举大数的倍数，相较上面代码减少了一定的循环次数，下面附上代码：

#include<iostream>
using namespace std;int main()
{int a,b,i,t;//while(scanf("%d%d",&a,&b)!=EOF)//while(scanf("%d%d",&a,&b)==2)while(cin>>a>>b){if(a<b){t=a;a=b;b=t;} // 保证前面一个数字比后面一个数字小for(i=b;;i+=b){if(i%a==0){cout<<i<<endl;break; }}}return 0;
}

2) 此题使用辗转相除法（欧几里得算法）更能方便求解且当数据庞大时能大幅减少循环次数，AC代码如下:

涉及公式：LCM(A,B)=A*B/GCD(A,B)（其中LCM为最小公倍数，GCD为最大公约数）

#include<iostream>
using namespace std;int main()
{int xiao,da,temp,t;//while(scanf("%d%d",&xiao,&da)!=EOF)//while(scanf("%d%d",&xiao,&da)==2)while(cin>>xiao>>da) // 考虑到多组数据 	{t=xiao*da;while(xiao!=0){temp=da%xiao;da=xiao;xiao=temp;}cout<<t/da<<endl; // 此时da为最大公约数，而最小公倍数=(xiao × da)/最大公约数}return 0;
}

再次看此代码还有可以需要优化的地方，为了防止 A*B 爆 int，可以将公式LCM(A,B)=A*B/GCD(A,B)改为LCM(A,B)=A/GCD(A,B)*B，优化后代码如下：

#include<iostream>
using namespace std;int main()
{int xiao,da,temp,t,a,b;//while(scanf("%d%d",&xiao,&da)!=EOF)//while(scanf("%d%d",&xiao,&da)==2)while(cin>>xiao>>da) // 考虑到多组数据 	{a=xiao;b=da; // 将输入的两个数赋值给a和bwhile(xiao!=0){temp=da%xiao;da=xiao;xiao=temp;}cout<<a/da*b<<endl; // 此时da为最大公约数，而最小公倍数=(xiao × da)/最大公约数}return 0;
}

​​​​​​​