清华大学机试 求root(N,k) 需要二刷 *数学推导下的快速幂取模

#include<iostream>
#include<string>
#include<vector>
using namespace std;

typedef long long ll;

int x, y, k;

ll charge(ll x, ll y, ll k) {
    ll res = 1;
    ll base = x;
    while (y != 0) {
        if (y % 2 == 1) {
            res = res * base;
            res %= k;
        }
        base *= base;
        base %= k;
        y /= 2;
    }
    return res;
}

int main() {
    while (cin >> x >> y >> k) {
        ll res = charge(x, y, k - 1);
        if (res == 0)
            cout << k - 1 << endl;
        else
            cout << res << endl;
    }
}