歐拉降幂：幂特别大的時候可以用快速幂來大幅度降低時間複雜度，而當幂大到10^10000時快速幂也不太行的時候，這時候就需要用到歐拉降幂，它的定理如下：
證明待更。
放一道題目FZU 1759
題目來源：https://vjudge.net/problem/FZU-1759
即求a^b%c的值，b範圍賊大，是以采用歐拉降幂闆子題。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>
#define MAX_len 50100*4
using namespace std;
typedef long long ll;
char b[1000100];
ll a,mod;
ll euler(ll n)
{
ll i,j,res=n,temp=n;
for(i=2;i*i<=temp;i++)
{
if(temp%i==0)
{
res=res/i*(i-1);
while(temp%i==0)
temp/=i;
}
}
if(temp>1)
res=res/temp*(temp-1);
return res;
}
ll quickpow(ll a,ll n)
{
ll res=1;
while(n)
{
if(n&1)
{
res=(res*a)%mod;
}
n>>=1;
a=(a*a)%mod;
}
return res%mod;
}
int main()
{
ll i,j;
while(scanf("%lld %s %lld",&a,b,&mod)!=EOF)
{
ll len=strlen(b);
ll t1=euler(mod);
ll ans=0;
for(i=0;i<len;i++)
{
ans=(ans*10+b[i]-'0')%t1;
}
ans+=t1;
printf("%lld\n",quickpow(a,ans));
}
return 0;
}
BZOJ 3884
題目來源：https://www.lydsy.com/JudgeOnline/problem.php?id=3884
由于指數是無窮大的，我們應該去對模數操作。
擴充歐拉定理：a^b≡a^(b%φ(p)+φ(p))(mod p)a為任意整數，b,p為正整數，且b>φ(p)（a,p不一定要互質）。
f(p)=
(mod p)=
(mod p)
即等于f(phi(p))=
(mod p)
由此找到了f(x)的遞歸式，但是需要終止條件，當phi(phi(...phi(p)))==1的時候，任何數mod 1 都是等于0的作為終止條件。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>
#define MAX_len 50100*4
using namespace std;
typedef long long ll;
char b[1000100];
ll a,mod;
ll euler(ll n)
{
ll i,j,res=n,temp=n;
for(i=2;i*i<=temp;i++)
{
if(temp%i==0)
{
res=res/i*(i-1);
while(temp%i==0)
temp/=i;
}
}
if(temp>1)
res=res/temp*(temp-1);
return res;
}
ll quickpow(ll a,ll n,ll mod)
{
ll res=1;
while(n)
{
if(n&1)
{
res=(res*a)%mod;
}
n>>=1;
a=(a*a)%mod;
}
return res%mod;
}
ll solve(ll mod)
{
if(mod==1)
return 0;
return quickpow(2,solve(euler(mod))+euler(mod),mod);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ll p;
scanf("%lld",&p);
printf("%lld\n",solve(p));
}
return 0;
}