BOJ)1629 곱셈

문제:icpc.me/1629

A^B(MOD C)를 구하는 문제이다. A,B,C가 2^31까지 들어오므로 단순 구현으로는 오버플로우나 시간초과를 받게 될 것이다.

하지만 우리는 분할정복을 이용하여 logB 시간에 A^B를 구해줄 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, c;
ll power(ll x, ll y) {
    ll ret = 1;
    while (y > 0) {
        if (y % 2) {
            ret *= x;
            ret %= c;
        }
        x *= x;
        x %= c;
        y /= 2;
    }
    return ret;
}
int main() {
    scanf("%lld%lld%lld", &a, &b, &c);
    printf("%lld\n", power(a%c, b));
    return 0;
}