[Softeer] 수퍼바이러스

문제링크

---

수퍼바이러스

풀이과정

---

Softeer | 바이러스 문제와 유사하지만, 이 문제는 0.1초를 기준으로 하고 N값이 굉장해엄청나 하다 ...

기존의 문제에서 사용한 코드를 써도 되지만, 당연히 시간초과가 발생한다.
1 <= N <= 10^16이기 때문이다 ... 하하 ...

그래서 생각한건 팩토리얼 구할 때 재귀를 사용하는 것 처럼 분할해서 계산하는 걸 생각했다.

증가율이 2, 초가 10(0.1초에 P배이므로 10 곱해주기)이고, 이걸 분할하면 아래와 같이 볼 수 있다 !
virus(2, 10) = virus(2, 5) virus(2, 5)
virus(2, 5) = virus(2, 2) virus(2, 2) 2
virus(2, 2) = virus(2, 1) virus(2, 1)
virus(2, 1) = 2

코드

---

import sys
K, P, N = map(int, input().split())

def virus(a, b):
    if b == 1:
        return a
    elif b%2 == 0:
        num = virus(a, b/2)
        return (num * num) % 1000000007
    else:
        num = virus(a, (b-1)/2)
        return (num * num * a) % 1000000007

result = virus(P, 10 * N) * K
print(result % 1000000007)

결과

---