[코딩 테스트 연습(파이썬/Python)] 백준 1629번 _ 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

[문제]

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

 

[입력]

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

[출력]

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

 

[아이디어]

1) 다루는 수가 크기 때문에 단순 연산을 하면 안된다.

2) mod를 이용해 지수인 B를 계속 절반으로 줄여가며 연산을 진행한다.

3) B를 2로 나눈 나머지가 발생할 경우 해당 상황의 밑(A)의 mod 값을 모아두었다가 마지막에 추가로 연산해준다.

 

a,b,c = map(int,input().split())
tmp = []
def f(a,b,c):
    a=a%c
    if b< 2:
        return a**b
    elif b%2:
        tmp.append(a)
        return f((a**2),b//2,c)
    else:
        return f((a**2),b//2,c)
n = f(a,b,c)
for x in tmp:
    n=n*x%c
print(n)

위처럼 열심히 하고 나니 알게된 사실,,^

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

파이썬은 무려 내장함수가 이를 해낼 수 있다. 파이썬 짱짱맨,,