题解 | 求root(N, k)

#include<iostream>

using namespace std;

long long quickpower(long long x, long long y, int k){
    long long ans = 1, temp = x;
    while(y){
        if(y & 1) ans = ans * temp % (k - 1);
        temp = temp * temp % (k - 1);
        y >>= 1;
    }
    return ans ? ans : k - 1;
}

int main(){
    int x, y, k;
    while(cin >> x >> y >> k){
        cout << quickpower(x, y, k) << endl;
    }
    return 0;
}

这题题解做没做过忘记了，但是这个问题其实不难，我们的核心要知道，我们的一切求幂操作，在求乘法的过程中加上无限多个同样的操作都不会改变结果，只要知道这一点，我们就可以对这个求幂的乘法操作进行修改了，当然，我们要先实现这个求幂，对于求幂，也不是干求一个幂的，有前人研究出来了一个优化度极高的快速幂方法，把乘法和位处理结合到求幂中，使求幂更加简单，感兴趣的同学可以去搜索快速幂，然后就是在求幂的时候我们实现模运算即可完成任务，注意直接算必然爆内存。