@NCPC2016 @ Exponial (欧拉降幂)

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 tostop reading at this point). There are many ways of constructing really big numbers known to humankind, for instance:

In this problem we look at their lesser-known love-child the exponial , which is an operation defined for all positive integers n as

For example, exponial(1) = 1 and  which is already pretty big. Note that exponentiation is right-associative:  .
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 ofexponial(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

 

欧拉降幂公式: 

指数爆炸时 a^b % m  =    a^(b%phi(m) + phi(m) ) %m

但是当 b数值小时,  欧拉降幂是 不正确的. 

所以 在处理时 处理到 4

对 m  不断去 phi( phi( phi( m) ) )    发现 个数不多.

然后就可以用递归的形式  去 求值;

 

 

[代码]

#include <bits/stdc++.h>
#include <stdio.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)

typedef long long ll;
const int maxn = 1e5+10;
const int mod =1e9+7;
const int inf = 0x3f3f3f3f;
using namespace std;

int geteular(ll n)
{
	ll ans = n;
	for(int i = 2 ; i*i <= n; i++)
	{
		if( n%i==0)
		{
			ans -= ans/i;
			while(n%i==0)
			    n/=i;
		}
	}
	if (n > 1) ans -= ans/n;
	return ans;
}
ll qpow(ll a, ll n, ll mod)
{
	ll res = 1 ;
	for(;n;n>>=1)
	{
		if( n&1 )
			res  = res*a %mod;
		a = a*a %mod;
	}
	return res;
}
int eular[100];
int tot ;

ll dfs(ll n , ll cot)
{
	if( eular[cot] == 1) return 0;
	else if( n == 4 ) return 262144%eular[cot];
	else
	{
		return (  qpow(n, ( dfs(n-1,cot+1) + eular[cot+1] ) ,eular[cot]) ) ;
	}
}
int main(int argc, char const *argv[])
{
	ll n,m;
	cin>>n>>m;
	tot = 0;
	if( n <=4 )
	{
		if( n==1) printf("%lld\n",1%m);
		else if( n==2 ) printf("%lld\n", 2%m);
		else if( n==3 ) printf("%lld\n", 9%m);
		else if( n==4 ) printf("%lld\n",262144%m);
		return 0;
	}
	eular[tot++] = m;
	while( (m = geteular(m) ) !=1)
	{
		eular[tot++] = m;
	}
	eular[tot++] = 1;
	ll ans = dfs(n,0);
	printf("%lld\n",ans);

	return 0;
}