杭电 2028 Lowest Common Multiple Plus

ゝ一纸荒年。 2022-05-18 06:27 162阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2028  
Problem Description  
求n个数的最小公倍数。

Input  
输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。

Output  
为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。

Sample Input  
2 4 6  
3 2 5 7

Sample Output  
12  
70

GCD求最大公约数，两个数相乘之后除以最大公约数就是最小公倍数  
AC代码：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    int gcd(int a,int b) {
    	return b==0?a:gcd(b,a%b);
    }
    int cmp(int a,int b){
    	return a>b;
    }
    int main() {
    	int n;
    	while(scanf("%d",&n)==1) {
    		int *a=new int[n];
    		for(int i=0; i<n; i++) {
    			scanf("%d",&a[i]);
    		}
    		sort(a,a+n,cmp);
    		
    		int ans=a[0]/gcd(a[0],a[1])*a[1];
    		
    		
    		for(int i=2; i<n; i++) {
    			if(ans>a[i]) {
    				ans=ans/gcd(ans,a[i])*a[i];
    			
    			} else {
    				ans=ans/gcd(a[i],ans)*a[i];
    				
    			}
    		}
    		printf("%d\n",ans);
    		delete a;
    	}
        return 0;
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关 S - Lowest Common Multiple Plus 求n个数的最小公倍数

求n个数的最小公倍数 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6

曾经终败给现在/ 2022年12月23日 09:45/ 0 赞/ 183 阅读

相关【杭电oj2028】Lowest Common Multiple Plus

Lowest Common Multiple Plus Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 6553

我不是女神ヾ/ 2022年09月25日 06:16/ 0 赞/ 127 阅读

相关【杭电oj1159】Common Subsequence

Common Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K

太过爱你忘了你带给我的痛/ 2022年09月25日 04:27/ 0 赞/ 155 阅读

相关 Least Common Multiple Ⅰ

Least Common Multiple Ⅰ Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述

缺乏、安全感/ 2022年08月10日 04:53/ 0 赞/ 175 阅读

相关杭电-1159Common Subsequence(LCS)

Common Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K

以你之姓@/ 2022年08月10日 04:40/ 0 赞/ 134 阅读

相关 1143. Lowest Common Ancestor (30)

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that

迷南。/ 2022年05月28日 10:25/ 0 赞/ 174 阅读

相关杭电 2028 Lowest Common Multiple Plus

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2028 Problem Description 求n个数的最小公倍数。

ゝ一纸荒年。/ 2022年05月18日 06:27/ 0 赞/ 163 阅读

相关 HDU2028 Lowest Common Multiple Plus

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

秒速五厘米/ 2022年05月11日 09:24/ 0 赞/ 163 阅读

相关 SP14932 LCA - Lowest Common Ancestor

include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; struct

谁践踏了优雅/ 2022年01月12日 13:33/ 0 赞/ 150 阅读

相关 SP14932 LCA - Lowest Common Ancestor

include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; struct

柔情只为你懂/ 2021年12月23日 23:59/ 0 赞/ 209 阅读