[BOJ] 1629 곱셈

문제 이해하기

• A를 B번 곱한 수를 C로 나눈 나머지의 값을 어떻게 알 수 있을까?
• 이때 각 숫자의 크기는 2,147,483,674 라는 매우 큰수이다. 

예제 입력으로 이해하기

• A :10 
  B :11
  C: 12
• 10^11  % 12
• = 10^5  * 10^5 * 10 % 12
• = (10^2 * 10^2 * 10 ) * (10^2 * 10^2 * 10 ) % 12
• = ((10*10) * (10*10) * 10 ) * ((10*10) * (10*10) * 10 ) % 12 

알고리즘

1. 각 변수의 크기가 크기 때문에 long long 타입으로 선언하자
2. 재귀 함수를 이용해서 문제를 쪼개서 풀수 있다.
   cal(10, 11) = cal(10, 5) * cal(10, 5) * 10 % 12
3. B가 홀수인 경우에는 cal(A, B/2) * cal(A,B/2) * A 로 A를 추가로 곱해줘야한다.
4. B가 짝수인 경우에는 cal(A, B/2) * cal(A,B/2) 를 해주면 된다.  

코드 

#include <bits/stdc++.h>
using namespace std;
int a,b,c;
int cal(int a, int b){
	if(b == 1) return a % c;
    int ret = cal(a, b/2);
    ret = (ret * ret) % c;
    if(b & 1) ret = (ret * a) % c;
    return ret;
}

int main(){
	cin >> a >> b >> c;
    cout << cal(a,b);
}

정리

• 아주 간단한 문제인거 같지만, 재귀를 이용해서 문제를 해결해야한다.
• 정수론 중 모듈러 연산에 의해 먼저 나누어도 동일한 결과가 나온다. 

느낀점

• 정수론 관련해서 많이 출제되는 코딩 테스트 문제를 정리하여 대비하자.