Illustration of exponial(3) (not to scale),Picture by?C.M. de Talleyrand-Périgord via Wikimedia Commons?Everybody loves big numbers (if you do not,you might want to?stop reading at this point). There are many ways of constructingreally big numbers known to humankind,for instance:
In this problem we look at their lesser-known love-child the?exponial,which is an operation de?ned for all positive integers?n as
For example,exponial(1) = 1 and??
Since the exponials are really big,they can be a bit unwieldy to work with. Therefore?we would like you to write a program which computes exponial(n) mod m (the remainder of?exponial(n) when dividing by m).
Since the exponials are really big,they can be a bit unwieldy to work with. Therefore?we would like you to write a program which computes exponial(n) mod m (the remainder of?exponial(n) when dividing by m).
输入
The input consists of two integers n (1 ≤ n ≤ 109?) and m (1 ≤ m ≤ 109?).
输出
Output a single integer,the value of exponial(n) mod m.
样例输入
2 42
样例输出
2
拓展欧拉定理：
则想到用其降幂，递归即可。
但是要特判n=1,n=2,n=3,n=4,因为此时a^n可能小于phi(m)。
#include <bits/stdc++.h>
#define maxn 50005
using namespace std;
typedef long long ll;
ll prime[maxn];
bool vis[maxn];
int cnt;
void getprime()
{
for(int i=2;i<maxn;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
}
for(int j=0;j<cnt&&prime[j]*i<maxn;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
ll phi(ll n)
{
ll res=n;
for(int i=0;i<cnt;i++)
{
if(n%prime[i]==0) res=res/prime[i]*(prime[i]-1);
while(n%prime[i]==0) n/=prime[i];
}
if(n>1) res=res/n*(n-1);
return res;
}
ll qpow(ll k,ll n,ll mod)
{
ll res=1;
while(n)
{
if(n&1) res=res*k%mod;
k=k*k%mod;
n>>=1;
}
return res;
}
ll cal(ll n,ll m)
{
if(m==1) return 0;
if(n==1) return 1ll;
if(n==2) return 2ll%m;
if(n==3) return 9ll%m;
if(n==4) return 262144ll%m;
ll tmp=phi(m);
return qpow(n,cal((n-1),tmp)+tmp,m);
}
int main()
{
ll n,m;
getprime();
scanf("%lld%lld",&n,&m);
ll ans=cal(n,m);
printf("%lldn",ans);
return 0;
}