문제 34

최대공약수와 최소공배수

태그 보기

유클리드 호제법

두 자연수 $A$, $B$가 주어진다.

$A$와 $B$의 최대공약수와 최소공배수를 출력하라.

입력

첫 번째 줄에 두 자연수 $A$, $B$가 공백으로 구분되어 주어진다. $(1 \le A, B \le 10^9)$

첫 번째 줄에 $A$와 $B$의 최대공약수를 출력한다.

두 번째 줄에 $A$와 $B$의 최소공배수를 출력한다.

12 18

6
36

$A=qB+r$일 때 $A$와 $B$의 공약수는 $B$와 $r$의 공약수와 같다. 이 성질을 이용해 $(A,B)$를 $(B,A\bmod B)$로 반복해서 바꾸는 유클리드 호제법을 사용한다. 두 번째 값이 $0$이 되면 첫 번째 값이 최대공약수 $g$이다.

원래 두 수를 $A=ga$, $B=gb$로 나타내면 $a,b$는 서로소이므로 최소공배수는 $gab=AB/g$이다. 최대공약수와 최소공배수를 각각 출력한다.

원래의 $A,B$를 보관하고 최소공배수는 $(A/g)\times B$로 계산한다. 최소공배수는 $10^{18}$ 이하이므로 이 범위의 정수를 정확히 계산해야 한다.

시간복잡도는 $O(\log(\min(A,B)+1))$, 추가 공간복잡도는 $O(1)$이다.

<numeric>의 gcd로 최대공약수를 구할 수 있다. 두 입력을 long long으로 받고 최소공배수는 A / g * B로 계산한다. 최대공약수를 구하는 동안 원래 입력값을 잃지 않도록 한다.

유클리드 알고리즘으로 gcd를 구하고 A/gcd*B 순서로 lcm을 계산한다. 최대 lcm이 $10^{18}$이므로 long long이 필요하다. 먼저 나누면 중간 곱의 범위도 줄어든다.

math.gcd(A,B)를 사용하고 A // g * B로 lcm을 구한다. 정수 나눗셈을 사용하며 /로 float를 만들지 않는다. 직접 약수를 모두 열거할 필요는 없다.

long A,B에 유클리드 알고리즘을 적용한다. lcm은 A/g*B로 계산하며 int끼리 곱한 다음 long에 저장하는 구현을 피한다.

u64 또는 i64로 유클리드 알고리즘을 구현한다. a/g*b 순서로 lcm을 계산하면 최대 $10^{18}$까지 정확하게 저장할 수 있다.

각 입력은 $10^9$ 이하라 Number로도 읽을 수 있지만 최소공배수는 $10^{18}$까지 커진다. 처음부터 BigInt로 읽어 유클리드 호제법과 최소공배수 계산을 모두 정수 연산으로 처리하면 단순하다.

let x = a, y = b;
while (y !== 0n) [x, y] = [y, x % y];
const g = x;
const lcm = a / g * b;

출력에는 g.toString()과 lcm.toString()을 사용한다. Math 함수에 BigInt를 넘기거나 결과를 다시 Number로 바꾸지 않는다.

언어