杭电oj--1019题C++实现

这道题有两个问题：

首先，是求利用数论的辗转相除法求最大公约数，后再求最小公倍数m*n/gcd(m,n),其中，m*n可能会超过int 数据范围，所以，该语句换成m/gcd(m,n)*n。

然后是如果只有一个元素的话直接输入该元素。

#include<iostream>
#include<math.h>
#define N 1000
using namespace std;
int GCD(int a,int b)
{
    return !(b)?a:GCD(b,a%b);
}

int main()
{
    int n,k,i,LCM,a;

    while(cin>>n)
    {
        while(n--)
        {

            cin>>k;
            cin>>a;
            LCM=a;
            for(i=1; i<k; i++)
            {
                cin>>a;
                LCM=LCM/GCD(LCM,a)*a;

            }
            cout<<LCM<<endl;
        }
    }
    return 0;
}

巴特西

杭电oj--1019题C++实现

最新文章

热门文章