题解 | #求root(N, k)#

#include <math.h>
#include <stdio.h>

int root(int x,int y,int k);

int main() {
    int x, y;
    int k;
    while (scanf("%d %d %d", &x, &y,&k) != EOF) { // 注意 while 处理多个 case
        printf("%d\n",root(x,y,k));
    }
    return 0;
}

int root(int  x,int y,int k){
    if(k==2||y==0) return 1;
    int result=1,mod=k-1;
    x=x%mod;// 把x变成合理数
    while(y){
        if(y%2)result=(result*x)%mod;// 对多出来的单独处理
        x=(x*x)%mod;// 快速幂
        y/=2;
    }
    return result?result:mod;
}