题解 | #求root(N, k)，内含证明#

//root(N, k) = N % (k - 1)
#include <stdio.h>

typedef long long LL;

LL fast_pow(LL a, LL b, int mod) {
    LL res = 1;
    while(b > 0) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    LL x, y;
    int k;
    scanf("%lld%lld%d", &x, &y, &k);
    LL res = fast_pow(x, y, k - 1);
    if(res == 0) res += k - 1;
    printf("%lld", res);

    return 0;
}

参考链接https://blog.51cto.com/u_12312066/3638841