思路
乘方可以使用乘法快速幂,可以看看我在 leetcode 上的题解。
因为可能会溢出 int,那么我们使用 long long
对于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; }