분할 정복 알고리즘 - (x^y)%m

Divide_And_Conquer_Multiple.cpp

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

ll f (int x, ll y, int m) {
    if (y == 0) return 1;
    if (y == 1) return x % m;
    if (y % 2 == 1) {
        ll sib = f(x, y - 1, m) % m;
        return ((sib % m) * (x % m)) % m;
    }
    else {
        ll al = f (x, y/2, m) % m;
        return ((al % m) * (al % m)) % m;
    }
}

int main () {
    int s = (1 << 27) + 7;
    ll ib = (1LL << 62) + 985;
    int al = (1 << 28) + 879;
    cout << f (s, ib, al);
    return 0;
}