공약수 > 문제은행



실력키우기 수학

2498 : 공약수

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 1254 회    시도횟수: 4148 회   



어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.


예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.

이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다.

예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.

두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오.

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 
첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 
입력되는 두 자연수는 2 이상 100,000,000 이하이다.


첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 공백을 사이에 두고 출력한다.
입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.

6 180
30 36


2 86486400
11648 14850


 #Euclid Algorithm  
* 용어 정의
   G(최대공약수), L(최소공배수), 
   gcd(a, b) : a와 b의 최대공약수를 구해주는 함수

a = b * Q + r ( 0 <= r < b) 일때,
gcd(a, 0) = a
gcd(a, b) = gcd(b, r) : 재귀적으로 적용됨
예)    a = 8, b = 12
step1 : a = 8, b = 12
step2 : a = 12, b = 8 ( 8%12 )
step3 : a = 8, b = 4  ( 12%8 )
step4 : a = 4, b = 0  (  8%4 )

* c_code recursion version
int gcd(int a, int b){return b? gcd(b, a%b):a;}

 # 두 수와 최대공약수(G)와 최소공배수(L) 
a = x*G, b = y*G, G = gcd(a, b) 이면 gcd(x, y) = 1이다.
L = x*y*G = a / gcd(a, b) * b,   
(참고: L = a * b / gcd(a, b)는 결과가 overflow가 발생할 수 있으므로 비추천)





수학알고리즘

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.