백준 1629

문제 링크

설명.

간단한 거듭제곱 문제. 문제 설명은 A,B,C가 주어졌을 때,
(A**B)%C를 구하는 것이다.

깡으로 계산하기에는 A,B,C가 충분히 많이 큰 수가 될 수 있기 때문에 곱하는 구간을 어느정도 나눠줄 필요가 있는 문제였다. 주어진 예시로는 충분히 큰 수를 체크할 수 없기 때문에 임의로 2개정도의 예시를 만들고, 넣는 그대로 작동하는 코드를 만든 후 결과를 비교하며 코드를 짜게 되었다.

아래 코드는 test 코드와 예시로 뽑은 결과들.

# test code.
from sys import stdin

A,B,C = map(int,stdin.readline().strip().split())

print((A**B)%C)
'''
test1
input : 1000 1234 965

output : 795

test2
input : 38685 99162 1234

output : 329
'''

작동 방식.

이런 문제에 관해 기준이 되는 숫자에 대해서는 예전부터 생각했지만 100이 적당하다고 생각해서 100을 사용했다.

코드의 작동 원리는 다음과 같다. A를 B번 곱하는 것에 대한 구간을 나눈다.
이 구간의 경우 test2의 예시를 사용하게 된다면 다음과 같이 나뉜다.(unit = 100)
B = 99162 = 62 + unit*91 + (unit**2)*9
그리고 이를 사용해서 마지막 결과는 다음과 같은 식으로 쓰이게 된다.
result = ((A**62) * ((A**unit)**91) * ((A**(unit**2))**9))%C

제출 코드.

# 제출 코드.
from sys import stdin

A,B,C = map(int,stdin.readline().strip().split())
result = 1
mul = 1
while B>100:
    for _ in range(B-B//100*100):
        result = (result*A)%C
        
    B = B//100
    for _ in range(100):
        mul = (mul*A)%C
    
    A = mul
    mul = 1
for _ in range(B):
    result = (result*A)%C
    
print(result)