어떤 수를 서로소 쌍의 곱으로 빠르게 분해하는 방법

1. 문제 2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 2. 풀이 최대공약수 G, 최소공배수 L이 주어질때 두 수 x,y는 어떻게 구할까 $$x = Gk_{1}$$ $$y = Gk_{2}$$ 이 때 L은 다음과 같이 구할 수 있다 $$L = Gk_{1}k_{2}$$ 따라서 $k_{1}k_{2}$는 L//G로 일정하다. 그러므로 우리는 L//G를 만드는 두 서로소 $k_{1}$과 $k_{2}$를 찾으면 된다. 여기서 $k_{1}$과 $k_{2}$는 1 이상의 자연..