문제
어느 빵집에서 lo부터 hi까지 모든 크기의 상자에 쿠키를 담습니다. 어떤 크기의 상자를 쓰든 남는 쿠키 없이 꽉 채울 수 있는 한 번의 생산량을 정하려고 합니다. 답은 lo부터 hi까지의 모든 정수로 나누어떨어지는 가장 작은 양수, 즉 이 수들의 최소공배수입니다.
smallest_multiple(lo, hi) 함수를 구현하세요.
입력
lo: 가장 작은 상자의 크기입니다.
hi: 가장 큰 상자의 크기입니다.
출력
lo, lo + 1, ..., hi 각각으로 나누어떨어지는 가장 작은 양의 정수를 반환합니다.
제약 조건
1 ≤ lo ≤ hi ≤ 40 (답은 부호 있는 64비트 정수 범위 안에 들어갑니다)
예시
입력:
lo = 1
hi = 6
예상 출력:
expected = 60
입력:
long long lo = 1;
long long hi = 6;
예상 출력:
long long expected = 60;
입력:
long lo = 1;
long hi = 6;
예상 출력:
long expected = 60;
설명
60은 1, 2, 3, 4, 5, 6으로 모두 나누어떨어지고 이보다 작은 양수 중에는 그런 수가 없으므로 답은 60입니다.
입력:
lo = 4
hi = 6
예상 출력:
expected = 60
입력:
long long lo = 4;
long long hi = 6;
예상 출력:
long long expected = 60;
입력:
long lo = 4;
long hi = 6;
예상 출력:
long expected = 60;
설명
lcm(4, 5) = 20이고 lcm(20, 6) = 60이므로 이번에도 답은 60입니다. 작은 크기들은 결과에 영향을 주지 않았습니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
구간 전체의 최소공배수는 수를 하나씩 더해 가며 구할 수 있습니다.
힌트 2
lcm(a, b) = a / gcd(a, b) × b입니다.
힌트 3
곱하기 전에 먼저 나누면 중간 값이 답보다 커지지 않습니다.
예상 복잡도
시간 O(n log M), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.