수퍼바이러스
Prob
1 ≤ K ≤ \(10^8\) 인 정수
1 ≤ P ≤ \(10^8\) 인 정수
1 ≤ N ≤ \(10^{16}\) 인 정수
\(KP^{10N}\) 을 1000000007로 나눈 나머지
Solv
Lv.2 바이러스와 마찬가지로 숫자가 커지면 int나 long의 범위를 넘어서므로 P를 곱할 때 마다 나머지 값을 구해서 오버플로 방지
하지만 P를 곱할 때마다 반복문을 사용하면 10N만큼 연산이 필요함
N=\(10^{16}\)인 경우 \(10^{17}\)번 P를 곱하는 연산을 해야하고 복잡도는 \(O(n)\)
P를 일일이 곱하는 대신 이전 P를 다시 곱해서 \(P^2\)로 만들면 \(O(log_2n)\)으로 연산이 단축됨
\(10N\) 에 도달하기 전까지 P를 곱한 값들을 배열에 저장하고 \(10N\) 에서 저장된 값을 빼가면서 해당되는 부분만 곱해주면서 나머지를 구하면 됨
Check
K 1
P 2
N 10
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| i | 1 | 2 | 4 | 8 | 16 | 32 | 64 |
| ans | \(P^1\) | \(P^2\) | \(P^4\) | \(P^8\) | \(P^{16}\) | \(P^{32}\) | \(P^{64}\) |
| n | \(2^{n-1}\) | 10N |
|---|---|---|
| 7 | 64 | 100 |
| 6 | 32 | 36 |
| 3 | 4 | 4 |
Feedback
오버플로와 연산량 모두를 고려해야하는 신박한 문제
