문제:
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 A,B,C가 빈 칸을 사이에 두고 순서대로 주어진다. A,B,C는 모두 2,147,483,647 이하의 자연수이다.
출력:
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
풀이방법:
주어질 A,B,C의 값이 매우 크므로 pow 연산을 활용하는 것은 시간초과가 발생하게 될 것이다. 따라서 효율적인 연산이 필요하다. 그러면서 사용하게 되는 것이 모듈러 연산의 분배법칙이다.
모듈러 X=x1*x2라고 가정하자. 그러면 X mod y = (x1 mod y)*(x2 mod y) mod y 가 성립한다. 이 것과 10^n*10^m=10^(n+m)임을 사용하면 시간복잡도를 O((logN)^2)까지 줄일 수 있다.
우선 지수를 2의 지수 단위로 분할한다. 이 문제의 예시와 같은 경우 11은 8+2+1로 482는 256+128+64+32+2와 같이 분할할 수 있다. 즉 10^11 mod 12 = (10^8 mod 12)(10^2 mod 12)(10^1 mod 12) mod 12 이고, 10^482 mod 12 = (10^256 mod 12)(10^128 mod 12)(10^64 mod 12)(10^32 mod 12)(10^2 mod 12) mod 12가 된다.
2의 지수를 사용하는 것에는 이유가 있다. 10^1부터 DP 방식을 사용하면 나머지의 값들도 쉽게 구할 수 있기 때문이다. 10^2 mod 12 = (10^1 mod 12)(10^1 mod 12) mod 12 이고 10^4 mod 12 = (10^2 mod 12)(10^2 mod 12) mod 12 ...와 같이 구하면 된다.
위와 같이 dp table을 다 채우고 난 뒤에 해당하는 값들만 곱한뒤에 다시 c로 나누면 나머지를 출력하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
import math
def Near2(n):
temp=1
while True:
if temp >= n:
break
temp*=2
return temp//2
a,b,c=map(int,input().split())
twos=[]
while b!=1:
t=Near2(b)
twos.append(t)
b=b-t
twos.append(b)
twos.reverse()
dp=[0]*(int(math.log(twos[-1],2))+1)
dp[0]=a%c
for i in range(1,len(dp)):
dp[i]=(dp[i-1]*dp[i-1])%c
final=1
for two in twos:
final*=dp[int(math.log(two,2))]
print(final%c)
|
cs |
문제링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1834. 나머지와 몫이 같은 수 (0) | 2019.10.11 |
|---|---|
| [BOJ]1357. 뒤집힌 덧셈 (0) | 2019.10.08 |
| [BOJ]1789. 수들의 합 (0) | 2019.10.06 |
| [BOJ]1075. 나누기 (0) | 2019.10.05 |
| [BOJ]1890. 점프 (0) | 2019.10.04 |