欧拉降幂（扩展欧拉定理）
发布时间
阅读量：
阅读量
欧拉降幂（扩展欧拉定理）
前言：之前+看过欧拉降幂，但误以为gcd(a,mod) > 1也能之间加上phi(mod), 在一次网络名额赛中有道裸欧拉降幂，接下来就是自己写着只有理论上的欧拉降幂来写题，硬搞了4个小时才A了。本想着不能在一个地方失败两次来写了这篇博客。
附上公式：
- 当b<phi(m)时，a^b\%m=a^b\%m
- 当b\ge phi(m) 时，a^b\%m=a^{b\%phi(m)+phi(m)}\%m
当gcd(a,m)=1时候，根据欧拉定理a^{phi(m)}\%m=1, 很容易得出。
当gcd(a,m)\gt1时，根据剩余系得出循环节可以证明公式成立(我也不会)
例题：UVA10692
求a_1^{a_2^{a_3^{...}}}\%m 的值，
思路：
反复使用欧拉降幂即可，注意需要处理b<phi(m)的情况。
对于这种情况可以考虑快速幂的时候先试乘 ，如果不超直接返回结果，否则返回取余再加的结果，可以归纳证明该算法是正确的。不过要在最后返回的时候取余m。
不过这题数据比较水，随便写都能过，推荐看下面计蒜客那题
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
ll a[maxn],phi[maxn];
ll exmod(ll a,ll m)
{
return a>=m?a%m+m:a;
}
ll exqpow(ll a,ll b,ll mod)//a^b>=m 返回a^b%m+m,否则返回a^b
{
ll ans=1;
while(b)
{
if(b&1)
ans=exmod(ans*a,mod);
b>>=1;
a=exmod(a*a,mod);
}
return ans;
}
ll getphi(ll x)
{
if(phi[x]!=-1) return phi[x];
ll xx=x,ans=x;
for(ll i=2; i*i<=x; i++)
{
if(x%i==0)
{
ans=ans*(i-1)/i;
while(x%i==0)
x/=i;
}
}
if(x>1)
ans=ans*(x-1)/x;
phi[xx]=ans;
return ans;
}
int n;//a[]的个数
//val=a[k]^(a[k+1]^(a[k+2]^(...^a[n])))
//现在准备计算val%m,且val>=m返回val%m+m,否则返回val
ll solve(int k,ll m)
{
//并且注意m==1时,a>0应该返回m.这里在exmod会自动计算
if(k==n||m==1) return exmod(a[k],m);//大优化，从满数据迭代到1不会太多次
return exqpow(a[k],solve(k+1,getphi(m)),m);
}
char s[110];
int main()
{
memset(phi,-1,sizeof(phi));
int cas=0;
while(scanf("%s",s)&&s[0]!='#')
{
//m为模数,n个数,求a1^(a2^(a3^(...)))%m
ll m;
sscanf(s,"%lld",&m);
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
cout<<"Case #"<<++cas<<": "<<solve(1,m)%m<<endl;
}
return 0;
}题目：计蒜客-super_log
题意：
给出a,b,m。计算a^{a^{a^{...}}}\%m,这里的a有b个
这题的数据是非常强的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int maxm=1e6+10;
ll phi[maxm];
ll exmod(ll a,ll m)
{
return a>=m?a%m+m:a;
}
ll exqpow(ll a,ll b,ll mod)//a^b>=m 返回a^b%m+m,否则返回a^b
{
ll ans=1;
while(b)
{
if(b&1)
ans=exmod(ans*a,mod);
b>>=1;
a=exmod(a*a,mod);
}
return ans;
}
ll getphi(ll x)
{
if(phi[x]!=-1) return phi[x];
ll xx=x,ans=x;
for(ll i=2; i*i<=x; i++)
{
if(x%i==0)
{
ans=ans*(i-1)/i;
while(x%i==0)
x/=i;
}
}
if(x>1)
ans=ans*(x-1)/x;
phi[xx]=ans;
return ans;
}
int n;
ll a;
ll solve(int k,ll m)
{
//并且注意m==1时,应该返回m.因为a>0这里在exmod会自动计算
if(k==n||m==1) return exmod(a,m);//大优化，从满数据迭代到1不会太多次
return exqpow(a,solve(k+1,getphi(m)),m);
}
int main()
{
memset(phi,-1,sizeof(phi));
int t;
cin>>t;
while(t--)
{
ll m;
cin>>a>>n>>m;
if(n==0){
cout<<1%m<<endl;
}
else
cout<<solve(1,m)%m<<endl;
}
return 0;
}全部评论 (0)
还没有任何评论哟~