[백준] 1629 - 곱셈

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

1629번: 곱셈

문제 한줄 이해

-A숫자를 B번 곱한뒤 C로 나눈 나머지 구하기

 

생각난 풀이

1번째 방법: A를 1~B번 곱해가면서 각각 C로 나눈 나머지가 규칙을 이룰 것이라 생각하고 다음과 같이 코드를 짰다.

import sys
a,b,c = map(int,sys.stdin.readline().split())

dp = []
cnt = 0
for i in range(b):
    cnt +=1
    now = a**i % c
    if now in dp:
        cnt -= 1
        break
    dp.append(now)
print(dp[b%cnt])

하지만 시간초과 너무 단순한게 생각했다. 2를 2,147,483,647번 곱하고 2,147,483,647로 나눈 나머지 연산을 진행하면 2,147,483,647번의 연산이 발생하는데 말이다!

 

2번째 방법: 방법이 생각이 나질 않아서 알고리즘 분류를 보았다. 바로 분할정복을 활용해 거듭제곱을 하는 것이였다.

B가 홀수이면 (a^b)*(a^b*a)

      짝수이면 (a^b)*(a^b)

이 규칙을 이용해 재귀함수를 통해 확인 하는 것이다. 이때 리턴값은 나머지 연산의 성질을 생각해야한다.

(a^b%c)*(a^b%c)%c

import sys
a,b,c = map(int,sys.stdin.readline().split())

def dac(a,b):
    if b == 1:
        return a % c
    temp = dac(a,b//2)
    
    if b % 2 == 0:
        return temp*temp%c
    else:
        return temp*temp*a%c
print(dac(a,b))