HDU 2028 Lowest Common Multiple Plus(여러 수의 최소 공배수,변환 을 구하 세 요)

Lowest Common Multiple Plus
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 49348    Accepted Submission(s): 20401
Problem Description
n 개의 최소 공배수 를 구하 다.
 
Input
여러 개의 테스트 인 스 턴 스 를 입력 하 십시오.모든 테스트 인 스 턴 스 의 시작 은 정수 n 이 고 그 다음 n 개의 정수 입 니 다.
 
Output
각 그룹의 테스트 데 이 터 를 위해 최소 공배수 로 출력 하고,각 테스트 실례 의 출력 은 한 줄 을 차지한다.너 는 마지막 출력 이 32 비트 의 정수 라 고 가정 할 수 있다.
 
Sample Input

   
   
   
   
2 4 6 3 2 5 7

 
Sample Output

   
   
   
   
12 70

 
Author
lcy
 
Source
C 언어 프로 그래 밍 연습(5)
원본 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2028
사고방식:공식 에 따라 GCD(a,b)*LCM(a,b)=a*b;최소 공 배 수 를 직접 구하 면 마지막 결과 가 범 위 를 넘 어 WA 를 초래 할 수 있 습 니 다.
그래서 먼저 GCD 를 구하 고,
AC 코드:
#include <iostream>
using namespace std;
int GCD(int x,int y)
{
    return y==0?x:GCD(y,x%y);
}
int main()
{
    int n,x;
    while(cin>>n)
    {
        int ans=1;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            ans=x/GCD(ans,x)*ans;
        }
         cout<<ans<<endl;

    }
    return 0;
}

좋은 웹페이지 즐겨찾기