[1629번] 곱셈

문제

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

 

입력

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

 

출력

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

 

나의 답

#include <bits/stdc++.h>

using namespace std;

unsigned long long cal(unsigned long long A, int B, unsigned long long C) {
    if(B==0) {
        return (unsigned long long)1;
    }
    else {
        unsigned long long result = cal(A, B/2, C);
        result *= result;
        result %= C;
        if(B%2==1) {
            result *= A;
            result %= C;
        }
        return result;
    }
}

int main(void) {
    unsigned long long A, C, result;
    int B;
    scanf("%llu%d%llu",&A,&B,&C);
    result = cal(A, B, C);
    printf("%llu\n",result);
    return 0;
}

 

해설

x^2n = x^n * x^n이다. 따라서 x^B/2의 값을 알고 있다고 가정한다면 x^B의 값을 구할 수 있다. 만약 B가 홀수이면 B/2에서 1이 누락되기 때문에 A를 한 번 더 곱해준다.