Least Common Multiple

Q: 두 수의 최소공배수를 구하는 공식은 무엇인가요?

lcm(a, b) = a × b / gcd(a, b) 는 a / gcd(a, b) × b 로 계산하므로 중간 값이 답을 초과하지 않습니다. 4 와 6 의 gcd는 2 이며, 4 / 2 × 6 = 12 입니다.

Q: 왜 gcd(a, b) × lcm(a, b)는 a × b와 같을까요?

각 소수에 대해 gcd는 a 와 b 의 거듭제곱 중 더 작은 것을 사용하고, lcm은 더 큰 것을 사용합니다. 더 작은 것과 더 큰 것을 더하면 두 거듭제곱의 합이 되며, 이는 a × b 에서 해당 소수의 거듭제곱과 정확히 같습니다. 모든 소수가 일치하므로 두 곱은 같습니다.

Q: LCM을 계산하는 시간 복잡도는 얼마인가요?

gcd 공식의 경우 Euclid 알고리즘의 비용인 O(log(min(a, b))) 에 나눗셈 한 번과 곱셈 한 번이 추가됩니다. 추가 공간은 O(1) 이 필요합니다. 배수를 검색하는 방식은 훨씬 느립니다. 더 큰 수만큼 증가시키면 O(min(a, b)) 이고, 1씩 세면 O(lcm(a, b)) 입니다.

Q: 두 개보다 많은 수의 최소공배수(LCM)는 어떻게 구하나요?

목록을 차례로 접습니다: lcm(a, b, c) = lcm(lcm(a, b), c) . [4, 6, 10] 의 경우 lcm(4, 6) = 12 이고 lcm(12, 10) = 60 입니다. 누적 값은 빠르게 커지므로 오버플로에 주의하고 목록이 길면 64비트 정수를 사용하세요.

입문수학과 시뮬레이션

+10

두 개의 양의 정수 a와 b가 주어집니다. 최소공배수를 반환하세요. 최소공배수는 a와 b가 모두 나머지 없이 나누어지는 가장 작은 양의 정수입니다.

예를 들어, 6의 배수는 6, 12, 18, 24 등이고, 8의 배수는 8, 16, 24 등이며, 두 목록에서 처음으로 공통으로 나타나는 수는 24입니다.

함수

lcm(a: integer, b: integer) → integer

ainteger: 첫 번째 양의 정수
binteger: 두 번째 양의 정수
반환값integer: a와 b의 공배수인 가장 작은 양의 정수

제약 조건

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
답은 부호 있는 32비트 정수에 들어갑니다: lcm(a, b) ≤ 2³¹-1. 곱 a × b은 그렇지 않을 수도 있습니다.

예제

입력: a = 4b = 6
출력: 12
설명: 6의 배수는 6, 12, 18부터 시작하고, 4의 배수는 4, 8, 12부터 시작합니다. 두 목록에 모두 있는 첫 번째 수는 12입니다.

입력: a = 7b = 3
출력: 21
설명: 7과 3은 1 이외의 공약수가 없으므로, 최소공배수는 두 수의 곱인 21입니다.

입력: a = 15b = 45
출력: 45
설명: 15는 45를 나누어떨어지게 하므로, 45는 이미 두 수 모두의 배수이며, 45보다 작은 배수는 존재하지 않습니다.

제출 시 숨은 테스트 +15개

후속 질문

나눗셈이나 나머지 연산을 전혀 사용하지 않고 뺄셈과 절반으로 나누기만 사용해 최대공약수를 구할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

최소공배수와 최대공약수는 하나의 사실을 이루는 두 측면입니다. gcd(a, b) × lcm(a, b) = a × b. 따라서 빠르게 답을 구하는 방법은 a × b / gcd(a, b)이지만, 한 가지 주의할 점이 있습니다. 곱은 10^12까지 커질 수 있어 답이 범위 안에 들어가더라도 32비트 정수에서 오버플로가 발생합니다. 그러므로 곱하기 전에 최대공약수로 나눠야 합니다.

더 큰 수부터 세기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

답은 두 수 모두의 배수이므로 두 수 중 더 큰 수 이상입니다. 후보 m을 max(a, b)에서 시작하고 a와 b가 모두 나누어떨어질 때까지 1씩 더합니다. 후보를 오름차순으로 시도하므로, 조건을 만족하는 첫 번째 수가 최소입니다.

4와 6의 경우 6, 7, 8, 9, 10, 11을 시도하지만 모두 조건을 만족하지 않고, 12에서 멈춥니다. a × b가 공배수이므로 루프는 항상 끝납니다.

시도 횟수는 답의 크기 정도입니다. 소수인 46337과 46327의 경우 답은 2146654199이므로 루프가 20억 회 넘게 실행됩니다. 너무 느립니다.

알고리즘

a와 b 중 더 큰 값으로 m을 설정합니다.
m % a 또는 m % b가 0이 아닐 동안 m에 1을 더합니다.
m을 반환합니다.

def lcm(a, b):
    m = max(a, b)
    while m % a != 0 or m % b != 0:
        m += 1
    return m

더 큰 수의 배수만큼씩 건너뛰세요

핵심 아이디어

개수에 포함된 후보 대부분은 가능성이 없습니다. 답은 더 큰 수의 배수여야 하므로, 이를 big이라고 부릅시다. 따라서 big, 2 × big, 3 × big처럼 다음 배수로 바로 넘어가며, 더 작은 수로 나누어떨어지는 첫 번째 수에서 멈춥니다.

4와 6의 경우 6을 시도하고(4로 나누어떨어지지 않음), 그다음 12를 시도합니다(나누어떨어짐). 답은 어떤 k에 대해 k × big이며, k는 더 작은 수 이하입니다. small × big은 항상 공배수이기 때문입니다. 따라서 반복문은 최대 min(a, b)번 실행되며, 여기서는 백만 번을 넘지 않습니다.

여기서는 충분히 빠르지만, 입력값이 커질수록 실행 시간도 늘어납니다. 수가 10^18까지라면 이 방법은 충분히 빠르지 않습니다.

알고리즘

big을 더 큰 수로, small을 더 작은 수로 둡니다.
m = big으로 설정합니다.
m % small이 0이 아니면 m에 big을 더합니다.
m을 반환합니다.

def lcm(a, b):
    big, small = max(a, b), min(a, b)
    m = big
    while m % small != 0:
        m += big
    return m

최대공약수로 나눈 다음 곱합니다

핵심 아이디어

두 수를 모두 소인수분해합니다. gcd는 각 소인수를 두 지수 중 작은 지수만큼 취하고, lcm은 큰 지수만큼 취하며, 두 결과를 합치면 a와 b의 모든 인수를 각각 정확히 한 번씩 사용합니다. 따라서 gcd(a, b) × lcm(a, b) = a × b이고, lcm(a, b) = a × b / gcd(a, b)입니다. 4 = 2²와 6 = 2 × 3의 경우 gcd는 2이고 lcm은 2² × 3 = 12입니다.

유클리드 알고리즘으로 gcd를 구합니다. y가 0이 될 때까지 (x, y)를 (y, x % y)로 바꿉니다. 이 과정은 O(log(min(a, b))) 단계가 걸립니다.

그런 다음 a / gcd × b 순서로 계산합니다. gcd는 a를 나머지 없이 나누므로 나눗셈으로 값이 손실되지 않고, 결과는 답을 초과하지 않습니다. 대신 a × b / gcd로 계산하면 a = b = 10^6일 때 32비트 정수에서 오버플로가 발생합니다. 곱은 10^12인 반면 답은 겨우 10^6입니다.

알고리즘

a와 b를 x와 y에 복사합니다.
y가 0이 아닌 동안 (x, y)를 (y, x % y)로 바꿉니다. 이제 x가 최대공약수입니다.
a를 x로 나눕니다.
그 결과에 b를 곱하고 반환합니다.

def lcm(a, b):
    x, y = a, b
    while y != 0:
        x, y = y, x % y
    # x is gcd(a, b). Divide before multiplying.
    return a // x * b

함정과 경계 사례

공식은 한 줄이지만, 버그는 산술 연산의 순서에 있습니다.

a × b를 먼저 계산하는 경우입니다. Java, C, C++, C# 및 Rust에서는 10^6에 가까운 두 수의 곱이 32비트 정수의 범위를 넘어서 결과가 잘못되거나 음수가 됩니다(Rust 디버그 빌드에서는 대신 패닉이 발생합니다). 실제 최소공배수는 범위 안에 들어가는데도 그렇습니다.
a × b를 부동소수점으로 최대공약수로 나누는 경우입니다. 결과가 2.146654199E9로 나오거나 마지막 몇 자릿수가 손실될 수 있습니다. 모든 계산을 정수로 처리하세요.
a와 b 자체에 유클리드 알고리즘의 반복문을 실행한 다음 공식에 사용하는 경우입니다. 반복문이 끝나면 두 변수에는 최대공약수와 0이 들어 있으므로, 복사본을 사용하세요.
답이 a × b라고 가정하는 경우입니다. 두 수가 공통 인수를 갖지 않을 때만 성립합니다. lcm(4, 6)은 24가 아니라 12입니다.

자주 묻는 질문4

두 수의 최소공배수를 구하는 공식은 무엇인가요?

lcm(a, b) = a × b / gcd(a, b)는 a / gcd(a, b) × b로 계산하므로 중간 값이 답을 초과하지 않습니다. 4와 6의 gcd는 2이며, 4 / 2 × 6 = 12입니다.

왜 gcd(a, b) × lcm(a, b)는 a × b와 같을까요?

각 소수에 대해 gcd는 a와 b의 거듭제곱 중 더 작은 것을 사용하고, lcm은 더 큰 것을 사용합니다. 더 작은 것과 더 큰 것을 더하면 두 거듭제곱의 합이 되며, 이는 a × b에서 해당 소수의 거듭제곱과 정확히 같습니다. 모든 소수가 일치하므로 두 곱은 같습니다.

LCM을 계산하는 시간 복잡도는 얼마인가요?

gcd 공식의 경우 Euclid 알고리즘의 비용인 O(log(min(a, b)))에 나눗셈 한 번과 곱셈 한 번이 추가됩니다. 추가 공간은 O(1)이 필요합니다. 배수를 검색하는 방식은 훨씬 느립니다. 더 큰 수만큼 증가시키면 O(min(a, b))이고, 1씩 세면 O(lcm(a, b))입니다.

두 개보다 많은 수의 최소공배수(LCM)는 어떻게 구하나요?

목록을 차례로 접습니다: lcm(a, b, c) = lcm(lcm(a, b), c). [4, 6, 10]의 경우 lcm(4, 6) = 12이고 lcm(12, 10) = 60입니다. 누적 값은 빠르게 커지므로 오버플로에 주의하고 목록이 길면 64비트 정수를 사용하세요.

Python

def lcm(a, b):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

a = 4
b = 6

기대값

Least Common Multiple

함수

제약 조건

예제

힌트

풀이

더 큰 수부터 세기

더 큰 수의 배수만큼씩 건너뛰세요

최대공약수로 나눈 다음 곱합니다

함정과 경계 사례

자주 묻는 질문4

비슷한 문제