首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。