[소프티어] 슈퍼바이러스 - python (레벨 3)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=391 

Softeer

 

풀이

문제를 보았을때 알수있는 힌트

이전에 풀었던 바이러스 문제를 좀더 어렵게 만든 문제인데.. 이전에 이미 분할 정복으로 풀어서 똑같이 풀면.. 해결된다.. 하하;;

문제만 보면 단순하게 생각할수있다. k*(p^10n)이 답이기 때문이다. 하지만 입력값의 최대인 10의 8승은 엄청나게 많아서 계산하기에는 많은 시간이 걸린다. 이를 분할 정복을 이용하여 O(nlogn)으로 줄일 수 있다.

import sys

input= sys.stdin.readline

k,p,n = map(int,input().split())

def recursive_power(c,n):
    if n==1:
        return c
    else:
        y= recursive_power(c,n//2)%1000000007
    if n%2 ==0:
        return (y*y)%1000000007
    else:
        return (y*y*c)%1000000007
a= recursive_power(p,10*n)
print((k%1000000007)*(a)%1000000007)

https://github.com/dydwkd486/coding_test/blob/main/softeer/슈퍼바이러스.py 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리