[백준 / BOJ] 1629 곱셈

문제

출처 : www.acmicpc.net/problem/1629

1629번: 곱셈

a를 b제곱한 수에 c를 나눈 나머지를 구하는 문제다.

 

풀이

B의 최댓값이 21억이므로 반복문으로 제곱을 해주면 총 21억번 반복을 하게되어서 시간초과가 난다.

분할정복과 수학공식을 이용해서 시간을 최소화해 구해야하는 문제였다.

 

a의 b제곱 = a의 b/2제곱 * a의 b/2제곱 을 사용한다.

단, 지수가 홀수일때는  a의 b제곱 = a의 b/2제곱 * a의 b/2제곱 * a를 해주는것에 유의해야한다.

 

이해를 돕기위해 위 그림을 보자.

2^8을 계속해서 공식을 사용해서 나누고 결국 2^1로 바뀐다.

이때, 곱하는 과정에서 수가 long long int를 넘어갈수있는데, 이를 방지하기위해 C를 중간중간 나눠주는것이 중요하다.

(곱셈의 모듈러 연산)

-> (A * B) % C = (A % C * B % C) % C 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1629%20%EA%B3%B1%EC%85%88/main.cpp

devxb/JJUNalgo