辗转相除法求最大公倍数和最小公约数

这是我的第一篇博客。希望自己以后也能坚持下去,来记录我学习C++的一些历程。

今天做ACM题,是求最小公倍数和最大公因数的。用辗转相除法做。我一开始用int型,发现测试普通数据时均得出正确答案。但是用题目中的测试数据30000000,50000000的时候,最大公约数是没有问题,但最大公倍数显示是负数。后来发现是int型的存储空间不够。换成long或者long long型就可以。

然后还学会了怎样用EOF结束程序。必须在C的环境下,用while(scanf("%d",&a)!=EOF)完成。

以下是我的代码:

#include<iostream>
#include<cstdio>//用有关C程序的函数时,需加此头文件
using namespace std;
main()
{
    
    
    long a,b,c,d,num;//a,b为测试数
    
    while(scanf("%d %d",&a,&b)!=EOF)//输入EOF结束,必须a,b均在scanf里。之前写的时候,b在while中,不成功
    { 
    
       
    
    num=a*b;//为求最小公倍数做准备。最小公倍数=两数乘积/最小公约数
    
    for(;b!=0;)//辗转相除。看网上代码,需要先比较大小,但我测试,不比较也可。
    {
        c=a%b;
        a=b;
        b=c;
    }
    d=num/a;
    cout<<a<<" "<<d<<endl;//a为最大公约数,d为最小公倍数。
}    
    
 } 

学习小结:了解了关于辗转相除法求最大公约数和最小公倍数的方法

     了解了C++中如何用EOF结束程序
     初步了解了long型,以及long long型的相关知识。

评论

暂无评论