什么是欧拉降幂
欧拉函数（Euler's Totient Function）是指小于等于n的正整数中与n互质的数的个数，通常用符号φ(n)表示。对于一个正整数n，φ(n)表示满足条件的数的个数。
当计算\(a^b \mod n\)时，如果\(a\)和\(n\)互质（即它们的最大公约数为1），那么我们可以利用欧拉函数的性质来简化计算。
欧拉函数\(\varphi(n)\)给出了小于等于\(n\)且与\(n\)互质的正整数的个数。根据欧拉定理，如果\(a\)和\(n\)互质，那么有：
\(a^{\varphi(n)} \equiv 1 \pmod{n}\)
这意味着\(a\)的\(\varphi(n)\)次幂与1对\(n\)取模的结果为1。
现在，考虑指数\(b\)。我们可以将\(b\)表示为：
\(b = k \cdot \varphi(n) + r\)
其中，\(k\)是一个整数，\(r\)是\(b\)除以\(\varphi(n)\)的余数，满足\(0 \leq r < \varphi(n)\)。
将这个表达式代入指数幂的计算中，得到：
\(a^b = a^{k \cdot \varphi(n) + r}\)
根据模指数幂的性质，我们可以将指数分解为两部分相乘：
\(a^b = (a^{\varphi(n)})^k \cdot a^r\)
由于\(a^{\varphi(n)} \equiv 1 \pmod{n}\)，所以第一部分为1，因此我们得到：
\(a^b \equiv a^r \pmod{n}\)
这意味着，我们可以将指数\(b\)取模到\(\varphi(n)\)的范围内，而不改变\(a^b \mod n\)的值。这样做可以显著降低指数幂的大小，从而提高计算效率，特别是在大数取模运算中。
c++代码
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
long long fastpower(long long base, long long power){
//快速降幂（模板来的）
long long ans =1;
base = base % mod;
while(power > 0){
if(power & 1){
//如果指数是一个奇数
ans = (ans * base) % mod;
}
//指数右移一位，底数平方取模
base = (base * base) % mod;
power >>= 1;
}
return ans % mod;
}
long long get_r(long long b, long long phi){
//b = m!
long long res = 1;
for(int i =1; i<= b; i++){
res = res * i % phi;
}
return res % phi;
}
long long eular(long long n){//计算欧拉函数
long long phi = n;
for(int i = 2; i <= n/i; i++){
if(n % i) continue; //i不是n的因数
while(n % i == 0){//
n = n / i;
}
phi = phi * (i - 1) / i; //套公 式无需理解
}
if(n > 1) phi = phi * (n - 1) / n; //例如 12 = 2 * 2 * 33和12就是互质数万一最后一个数比i大比如3 > 2
return phi;
}
int main(){
long long n, m;
cin >> n >> m;
long long phi = eular(mod);//计算欧拉数
long long r = get_r(m, phi);//计算r
cout << fastpower(n, r) << endl;//计算a^r
return 0;
}