首页 > 代码库 > hdu 1019 Least Common Multiple

hdu 1019 Least Common Multiple

这题直接枚举是不可能的

所以想到了一遍输入一边计算 把每次的gcd给除掉 并相乘 得到的就是lcm

 

#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffff#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;ll gcd(ll a,ll b){    return a%b==0?b:gcd(b,a%b);}int main(){    int t,n,tn;    ll a,sum;    cin>>t;    while(t--)    {        cin>>n;        tn=n;        sum=1;        while(n--)        {            //cout<<n<<endl;            scanf("%I64d",&a);            if(n==tn-1) {sum=a;continue;}            sum=sum*a/(gcd(sum,a));        }        cout<<sum<<endl;    }    return 0;}