[BOJ] 곱셈 C++ 풀이

문제

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

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

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

접근 방법

나머지 연산에 대한 처리를 해줘야 하는 문제였다.

주어진 문제에서 요구하는 출력값은 다음과 같은 형태로 변형시킬 수 있다.

A^B % C = (((A^(B/2)) % C )* ((A^(B/2)) % C)) % C

이는 전체의 mod값$($%)은 절반의 mod값을 제곱한 뒤 mod한 값과 같다는 명제를 활용한 것으로 이 절반을 다시 반으로 나눠도 명제는 성립하며 이를 계속 반으로 나누어도 마찬가지로 명제는 성립한다.

위의 식을 사용하여 지수가 짝수일때, 홀수일때의 연산을 다르게 하여 계산을 줄인다면 문제를 해결할 수 있다.

구현

#include<iostream>
#define ll long long
using namespace std;

ll mul(int a, int b, int c)
{
    if(b == 1) return a % c;
    ll mult = mul(a, b / 2, c);

    if(!(b % 2)) return mult % c * mult % c;
    else return mult % c * mult % c * (a % c) % c;
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll res;
    ll a, b, c;
    ll ans = 1;
    cin>>a>>b>>c;
    
    cout<<mul(a % c, b, c);
    return 0;
}

오답노트

입력값의 범위를 고려하지 않고 고속 거듭제곱으로 문제를 해결하면 될 것이라고 생각하였다. 자료형 범위를 넘어가는 계산 결과에 의한 오버플로우를 해결해야만 했던 문제였다.