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

2023-03-13,

这道题有两个问题:

首先,是求利用数论的辗转相除法求最大公约数,后再求最小公倍数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++实现的相关教程结束。

《杭电oj--1019题C++实现.doc》

下载本文的Word格式文档,以方便收藏与打印。