1629

 

문제 요약

 

자연수 A를 B번 곱한 수를 알고 싶고, 이를 C로 나눈 나머지를 구해라.

 

입력

 

A, B, C 모두 2,147,483,647 이하의 자연수이다.

 

풀이

 

시간제한이 0.5초이다. 21억 번 반복하면서 곱하면 시간 초과가 발생한다.

또한 이 값이 long long 범위를 넘어서기 때문에 중간중간 나머지를 구해야 하고, 

계산값을 중간에 캐싱해야한다.

#include <bits/stdc++.h>

using namespace std;

int r,a,b,c;

long long powMod(int a, int b, int c){
    if(b == 0) {
        return 1;
    }

    long long temp = powMod(a, b/2, c) % c;
    long long result = (temp * temp) % c;

    if(b & 1){
        result = (result * a) % c;
    }

    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> a >> b >> c;

    long long r = powMod(a, b, c);

    cout << r << '\n';

    return 0;
}

 

재귀함수로 풀었다.