| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 (추가 시간 없음) | 128 MB | 155590 | 45056 | 32590 | 27.941% |
문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
풀이
def times(num, cnt, div):
if cnt == 1:
return num
if cnt % 2 == 0:
return (times(num, cnt//2, div)*times(num, cnt//2, div)) % div
else:
return (times(num, cnt//2, div)*times(num, cnt//2+1, div)) % div
A,B,C = map(int, input().split())
A %= C
print(times(A, B, C))- 원래는 그냥 (A**B)%C 하면 되는데,
- 문제는 숫자가 너무 커서 중간에 overflow가 생길 수 있다는 점이다.
- 그래서 for 문으로 A 하나하나 곱할 때 마다 %C를 해주는 방식을 취하면 O(N)으로 시간 초과가 난다 (0.5초짜리 문제임)
- 분할 정복을 그래서 사용해야하는데, B번 곱해야할 걸 B//2번, B//4번, … 이렇게 작은 문제로 쪼개는 거다.
- 여기서는 쪼갤 때, (B//2) * (B//2)같은 방식으로 하면 똑같이 시간 초과가 난다. 따라서 (B//2)**2와 같이 작성
- 또한 홀수의 경우 딱 이등분이 되지 않으므로, * A를 한번더 해준다. #Computer #PS