Question
문제링크
Silver 1
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
Input
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
10 11 12
Output
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
4
Logic
기본 구조 : recursion
1) (A^B)%C는 다음과 같이 변환할 수 있다.
이를 재귀를 이용하여 표현한다.
Code
from sys import stdin
a,b,c = map(int,stdin.readline().strip().split())
def func(a,b):
if b==1 : return a%c
else:
tmp = func(a,b//2)
if b%2==0 : return (tmp**2)%c
else : return ((tmp**2)*a)%c
print(func(a,b))