题意：
- 根据题面可以推出一个公式
其中
的个数是
,输出
思路：
欧拉降幂(广义欧拉定理)
=
其中
结构1
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1000000;
ll prim[M+10];
ll phi[M+10];
ll vis[M+10];
ll a,b,m;
void getphi( )
{
int cnt=0;
memset(vis,0,sizeof(vis));
memset(prim,0,sizeof(prim));
memset(phi,0,sizeof(phi));
phi[1]=1;
for(int i=2; i<=M; i++)
{
if(!vis[i])
{
prim[cnt++]=i;
phi[i]=i-1;
}
for(int j=0; j<cnt&&i*prim[j]<=M; j++)
{
vis[i*prim[j]]=1;
if(i%prim[j]==0)
{
phi[i*prim[j]]=phi[i]*prim[j];
break;
}
else
{
phi[i*prim[j]]=phi[i]*(prim[j]-1);
}
}
}
}
ll pow(ll a,ll n,ll mod)
{
ll ans=1;
ll base=a;
while(n)
{
if(n&1)
{
ans=ans%mod*base%mod;
}
base=base%mod*base%mod;
n>>=1;
}
return ans%mod;
}
ll solve(ll a,ll b,ll mod)
{
if(mod==1)//模数为1时停止计算，因为之后的结果都是相同的
{
return 0;
}
if(b==1)//最后一个a,最上面的a上面没有a了，所以最上面的a的指数为1
{
return a%mod;
}
ll d=solve(a,b-1,phi[mod]);//d=0假如d==0就一定是通过模phi[mod]得来的0
//所以它一个加上phi[mod]就是else语句;
if(d<phi[mod]&&d)//d小于phi[mod]并且d不等于0
{
return pow(a,d,mod);
}
else
{
return pow(a,d+phi[mod],mod);
}
}
int main( )
{
getphi( );
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&m);
if(b==0)
{
printf("%lld\n",1%m);
continue;
}
printf("%lld\n",solve(a,b,m)%m);
}
return 0;
}
结构2
powmod(a, solve(l + 1, r, phi[m]), m);
，
个
;
个
m->phi[m]->phi[phi[m]]
根据扩展欧拉定理等于x >= m ? x % m + m : x;
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1000000;
ll prim[M+10];
ll phi[M+10];
ll vis[M+10];
ll a,b,m;
void getphi( )
{
int cnt=0;
memset(vis,0,sizeof(vis));
memset(prim,0,sizeof(prim));
memset(phi,0,sizeof(phi));
phi[1]=1;
for(int i=2; i<=M; i++)
{
if(!vis[i])
{
prim[cnt++]=i;
phi[i]=i-1;
}
for(int j=0; j<cnt&&i*prim[j]<=M; j++)
{
vis[i*prim[j]]=1;
if(i%prim[j]==0)
{
phi[i*prim[j]]=phi[i]*prim[j];
break;
}
else
{
phi[i*prim[j]]=phi[i]*(prim[j]-1);
}
}
}
}
ll mod(ll x, ll m)
{
return x >= m ? x % m + m : x;
}
ll powmod(ll a, ll b, ll MOD)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = mod(ans * a, MOD);//根据广义欧拉定理,大于指数大于模数的欧拉函数就要变换，否则就是原数
// ans = ans * a % MOD;
// a = a * a % MOD;
a = mod(a * a, MOD);
b>>=1;
}
return ans;
}
ll solve(ll l,ll r,ll m)
{
if (l == r || m == 1)
return mod(a, m);
return powmod(a, solve(l + 1, r, phi[m]), m);
}
int main( )
{
getphi( );
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&m);
if(b==0)
{
printf("%lld\n",1%m);
continue;
}
else
{
printf("%lld\n",solve(1,b,m)%m);
}
}
return 0;
}
