모듈러 연산으로 큰 정수 다루기

코딩 테스트 문제를 풀다 보면 overflow에 종종 마주합니다.  

 

이 문제를 보아도 A, B, C 값이 최대 2,147,483, 647 자연수 값이 될 수 있어 

일반적인 반복문을 통한 풀이로는 long long 타입을 붙여도 overflow 가 되는 것을 알 수 있습니다.

 

모듈러 연산은 이러한 문제의 해결 방법 중 하나가 될 수 있습니다.

 

모듈러 연산이란?

어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산(mod) 

 

정수론에서 모듈러 연산(modular arithmetic) 이란,

정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법입니다.

c++ 에서 mod는 %로 표현됩니다

 

모듈러 연산 사칙 연산

덧셈, 뺄셈, 곱셈에 대해서 다음 식이 항상 성립합니다. (mod M 을 % M으로 표현)

0. a = b % M 과 b = c % M 은 a = c % M 을 의미 합니다.
1. ((a % M) + (b % M)) % M = (a+b) % M
2. ((a % M) - (b % M)) % M = (a-b) % M
3. ((a % M) * (b % M)) % M = (a*b) % M

 

 

위 문제에 적용한다면, B의 값을 재귀를 통해서 이진 분할로 나누어 모듈러 연산을 적용해 풀 수 있을 것입니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll A, B, C;

ll go(ll a, ll b) {
    // b 값이 재귀를 통한 이진 분할 끝에 1이 되었을 때 초기 모듈러 값 반환 
    if(b == 1) return a % C;

    // 재귀를 통한 이진 분할
    ll ret = go(a, b/2);
    // 곱셈 모듈러 연산  
    ret = (ret * ret) % C

    // 홀수일 경우
    if(b%2) ret = (ret * a) % C
    return ret;
}

int main () {
    cin >> A >> B >> C;

    cout << go(A, B) << '\n';
    return 0;
}