최대공약수

문제

a와 b의 최대공약수를 반환하세요. 유클리드 알고리즘은 (a, b)를 (b, a mod b)로 반복해서 바꾸다가 b가 0이 될 때까지 진행합니다.

gcd(a, b)를 구현하세요.

a: 첫 번째 수입니다. b: 두 번째 수입니다.

gcd(a, b)를 반환하세요. gcd(0, 0)은 0입니다.

0 ≤ a, b ≤ 10¹⁸

예시 1

입력:
a = 48
b = 18

예상 출력:
expected = 6

입력:
long long a = 48;
long long b = 18;

예상 출력:
long long expected = 6;

입력:
long a = 48;
long b = 18;

예상 출력:
long expected = 6;

48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0이므로, 정답은 6입니다.

예시 2

입력:
a = 17
b = 5

예상 출력:
expected = 1

입력:
long long a = 17;
long long b = 5;

예상 출력:
long long expected = 1;

입력:
long a = 17;
long b = 5;

예상 출력:
long expected = 1;

17과 5는 1 외에 공약수가 없습니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

나머지 연산으로 바꿔도 gcd는 변하지 않습니다.

힌트 2

두 수의 역할을 바꿔가며 두 번째 값이 0이 될 때까지 반복하세요.

힌트 3

두 입력이 모두 0인 경우를 반드시 처리하세요.

예상 복잡도

시간 O(log min(a, b)), 추가 공간 O(1)

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.