HDU 1108 최소 공배수 (lcm)

http://acm.hdu.edu.cn/showproblem.php?pid=1108
매주 6 박 의 BestCoder (쌀 이 있 습 니 다!) 에 오신 것 을 환영 합 니 다.
최소 공배수
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 40619    Accepted Submission(s): 22745
Problem Description
두 개의 정 수 를 정 하여 이 두 수의 최소 공 배 수 를 계산 하 다.
 
Input
여러 조 의 테스트 데 이 터 를 입력 하 십시오. 각 조 는 한 줄 만 있 고 1000 보다 크 지 않 은 정수 두 개 를 포함 합 니 다.
 
Output
모든 테스트 용례 에 대해 서 는 이 두 수의 최소 공배수, 인 스 턴 스 마다 한 줄 을 출력 합 니 다.
 
Sample Input

   
   
   
   
10 14

 
Sample Output

   
   
   
   
70

제목: 두 수의 최대 공배수 구하 기.
문제 풀이 방향: 먼저 두 수의 최소 공약수 ged (a, b) 를 구 한 다음 에 최소 공배수 lcm = (a / ged (a, b) * b;
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int gcd(int a,int b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}
int main()
{
	int a,b;
	while(scanf("%d %d",&a,&b) != EOF)
	{
		int ans,lcm;
		if(a<b) swap(a,b);
		ans=gcd(a,b);
		lcm=(a/ans)*b;
		cout << lcm << endl;
	}
	return 0;
}

좋은 웹페이지 즐겨찾기