欧拉降幂-乘积幂次
题目描述
输入描述
输入共一行,包含两个整数 n,m。
输出描述
输出共一行,表示答案。
输入输出样例
示例 1
输入
2 3
输出
64
解题代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=1e9+7; // 定义模数 p = 10^9 + 7
ll n,m;
// 快速幂函数,计算 a^b % p
ll qmi(ll a,ll b)
{
ll res =1;
while(b)
{
if(b&1)res = res*a%p; // 如果 b 的最低位是 1,累乘到结果中
a=a*a%p,b>>=1; // a 自乘,b 右移一位
}
return res;
}
int main()
{
cin>>n>>m; // 输入 n 和 m
// 计算欧拉函数 phi(p),因为 p 是质数,phi(p) = p-1
ll c=1e9+7,phi=c;
for(int i=2;i<=c/i;++i)
{
if(c%i)continue; // 如果 i 不是 c 的因数,跳过
phi=phi/i*(i-1); // 更新 phi 的值
while(c%i==0)c/=i; // 将 c 中的所有 i 因子去掉
}
if(c>1)phi=phi/c*(c-1); // 如果 c 还有剩余的大于 1 的因数,更新 phi
// 计算 F(m) = m! % phi
ll b=1;
for(int i=1;i<=m;++i)b=b*i%phi;
// 输出 n^F(m) % p
cout<<qmi(n,b)<<'\n';
return 0;
}
1. 题目分析:
因此,我们需要利用数论中的欧拉定理来简化计算。
欧拉定理:
方法思路:
为什么想到这个方法?
代码实现的关键点:
2. 数学原理