백준 2436. 공약수

https://www.acmicpc.net/problem/2436

2436번: 공약수

 

최대공약수 (GCD, Greatest Common Divisor) : 유클리드 호제법으로 구함 

최소공약수 (LCM, Least Common Multiple) : 두 수 A, B에 대하여 A x B = LCM x GCD 이다. 

 

이 문제는 LCM과 GCD는 주어지고 두 수 A와 B를 찾는 것이다. 

A x B = LCM x GCD 식에서 A의 약수를 a라고 하면 A = a x GCD이고, 마찬가지로 B = b x GCD 이다. (두 수가 서로소일때) 

즉 a x GCD x b x GCD = LCM x GCD 이고 양변을 GCD x GCD로 나누면 

a x b = LCM / GCD 이다. 

따라서 a와 b를 구하고 각 값에 GCD를 곱하면 구하는 값인 A와 B를 찾을수 있다.