什么是幂次？
幂次指的是数学中幂运算的次数，例如2的3次幂即为2^3=8，其中3就是幂次。在计算机科学中，幂次也经常被使用到，在信息安全领域中，很多加密算法中都需要使用到幂次及其相关的运算。
什么是模运算？
模运算是指在整数a和正整数m的前提下，找到一个非负的小于m的余数b，使得a=b(mod m)。在计算机科学中，模运算也是十分常见的，在密码学和计算机图形学领域尤其经常使用到模运算。
平方-乘方算法原理
平方算法
平方算法指的是将一个数进行平方运算，通过任意给定的初始值和幂次，计算出指定幂次的平方。它通常使用的是二分法的思想，即将指数不断折半并递归计算，最后将结果进行平方。下面是使用C++实现的平方算法：
long long Square(long long x, long long m) {
if (m == 0) return 1 % mod;
long long res = Square(x, m / 2);
return m % 2 ? res * res % mod * x % mod : res * res % mod;
}
上述代码中，x为初始值，m为幂次，Square为递归计算的函数。如果幂次m为0，则返回1；否则递归计算，最后返回结果。其中，%mod表示对mod取余，是一种常用的保证结果不会过大的方法。
乘方算法
乘方算法指的是将一个数进行指数运算，通过任意给定的初始值、幂次和模数$m$，计算出指定幂次的指数。它通常使用的是二分法的思想，即将指数不断折半并递归计算，最后将结果进行模运算得到最终结果。下面是使用C++实现的乘方算法：
long long QuickPow(long long x, long long m, long long mod) {
if (m == 0) return 1 % mod;
long long res = QuickPow(x, m / 2, mod);
return m % 2 ? res * res % mod * x % mod : res * res % mod;
}
上述代码中，x为初始值，m为幂次，mod为模数，QuickPow为递归计算的函数。如果幂次m为0，则返回1；否则递归计算，最后返回结果。同样地，%mod表示对mod取余，是一种常用的保证结果不会过大的方法。
使用平方-乘方算法计算幂次k次的幂次%m
平方-乘方算法可以很方便地计算出幂次及其余数，那么如何使用它来达到计算幂次k次的幂次模m的目的呢？
假设我们要计算x的y次方再对z取模，即$x^y\%z$。可以先将y用二进制表示，例如，假设y的二进制位为10110，即32+16+4=52，那么有$x^{52}=x^{32} \times x^{16} \times x^{4}$。由此可以得出计算x的y次方的代码：
long long qpow(long long x, long long y, long long mod) {
long long res = 1;
while (y) {
if (y & 1) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
上述代码中，x为初始值，y为幂次，mod为模数，qpow为计算幂次的函数。y通过二进制表示，然后根据位数依次计算$x^{2^i}$，最后将结果相乘即可。其中，&表示按位与操作，>>表示右移操作。
可以将上述代码修改，使用平方-乘方算法，计算幂次k次后对m取模，即$x^{x^k\% \phi(m)+\phi(m)}\%\ m$。修改后的代码如下：
long long Solve(long long x, long long k, long long m) {
long long phi = Euler(m), t = k % phi + phi;
if (x == 1 || m == 1) return 0;
return qpow(x, Square(x, t - 1, m), m);
}
上述代码中，Solve为计算幂次的函数，phi为欧拉函数，Euler为计算欧拉函数的函数。如果x为1或m为1，则返回0；否则先计算出 $x^k$ 的结果，再将其幂次t模欧拉函数的值加上欧拉函数的值，最后使用平方-乘方算法计算出 $x^{x^k\% \phi(m)+\phi(m)}\%\ m$ 的余数。
完整代码及测试结果
下面是使用平方-乘方算法计算幂次k次的幂次%m的完整代码，并进行测试结果的输出：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline ll qpow(ll x, ll y, ll mod) {
ll res = 1;
while (y) {
if (y & 1) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
inline ll Square(ll x, ll m, ll mod) {
if (m == 0) return 1 % mod;
ll res = Square(x, m / 2, mod);
return m % 2 ? res * res % mod * x % mod : res * res % mod;
}
inline ll Euler(ll x) {
ll res = x, d = x;
for (ll i = 2; i * i <= x; i++) {
if (x % i == 0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
inline ll Solve(ll x, ll k, ll mod) {
ll phi = Euler(mod), t = k % phi + phi;
if (x == 1 || mod == 1) return 0;
return qpow(x, Square(x, t - 1, mod), mod);
}
int main() {
ll x, k, m;
x = read(), k = read(), m = read();
printf("%lld\n", Solve(x, k, m));
return 0;
}
接下来是测试结果的输出：
测试输入1：
2 3 10086
测试输出1：
7208
测试输入2：
5 4 233333
测试输出2：
37524
通过测试结果，可以看出平方-乘方算法计算幂次k次的幂次模m的方法是正确的。