1629_곱셈(쉬운이해)

문제는 더보기!

 

곱셈

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

56013

14906

10954

25.884%

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1 복사

10 11 12

예제 출력 1 복사

4

 

 

일반적으로 생각하듯이 풀면 시간초과가 나게되는 문제이다.

 

3 ** 10 은

 

3 ** 5  x  3**5 와 같다.  (가독성을 높이려고 곱하기를 x로 씀)

 

3 ** 5 는

 

3 ** 2 x 3 ** 2 x 3 과 같다.

 

즉, 제곱하는수가 짝수일때랑 홀수일때랑만 구분해주면 된다.

 

 

 

 

물론 수학적으로는 이렇게 나누어 계산해도 3을 10번 곱한것과 같지만, 프로그래밍으로 보면 다르다.

 

3 ** 10은 3을 10번 곱하는 연산이지만, 3 ** 5 의 값을 저장해둔다면

 

3 ** 5 x 3 ** 5 는 5 + 1 즉 6번의 연산으로 줄어들게 되는 것이다!

 

a,b,c = map(int,input().split())

def f(a,b):
    print(a,b)
    if b ==1:
        return a%c

    num = f(a,b//2)


    if b%2 ==0:
        return num * num%c
    else:
        return num * num*a%c

print(f(a,b))