[softeer] 나머지 정리 활용

바이러스 - python

https://softeer.ai/practice/6284

 

import sys
# 2초
# 1000000007
# k*p^n % (7+10^8)

input = sys.stdin.readline
k, p, n = map(int, input().split())
result = k % 1000000007
remainder = p % 1000000007
for _ in range(n):
    result = (result * remainder) % 1000000007

print(result)

 

pow 내장함수 사용할 경우

아래와 같이 간단하다.

k*pow(p,n,1000000007)%1000000007

 

 

나머지 정리를 이용한 정답 코드는 아래와 같은 원리로 작동한다.

A * B * C * D ... % Q 는 ((((((A % Q) * B) % Q) * C) % Q ) * D))%Q ... 와 같다.