BZOJ3884 欧拉降幂(板子 sqrt(n))

题目链接:点此

题意,很简单，

思路：

很简单,直接用欧拉降幂公式开始降幂,

$$2^{2^{2^{2^{2}}}}\ mod \ p$$ = $$2^{2^{2^{2^{2}}}\ mod\ \varphi(p)+\varphi(p)}$$ 一直往前推,会有一项 $\varphi(p)=1$这时候 $2^{2^{...}\ mod \ \varphi(p)+\varphi(p)}=2^{1}$这样就可以算了

模板

求单个欧拉值

ll get_phi(ll  x){ll res=x;for(int i=2;i*i<=x;i++){if(x%i==0){res=res-res/i;while(x%i==0) x/=i;}       }if(x!=1) res=res-res/x;return res;
}

这个在$O(\sqrt{n})$就求出来了,适合一个数求

题解代码:

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm> 
using namespace std;
#define ll long long
#define rd(a) scanf("%d",&a)
#define rld(a) scanf("%lld",&a)
#define rs(a) scanf("%s",a)
#define me(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
const ll maxn=3e5+10;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const double PI=acos(-1);
int n,m;
ll get_phi(ll  x){ll res=x;for(int i=2;i*i<=x;i++){if(x%i==0){res=res-res/i;while(x%i==0) x/=i;}       }if(x!=1) res=res-res/x;return res;
}
ll q_power(ll a,ll b,ll p){ll ans=1;while(b){if(b&1) ans=(ans*a)%p;b>>=1;a=(a*a)%p;}return ans; 
}
ll f(ll p){if(p==1) return 0;ll t=get_phi(p);return q_power(2,f(t)+t,p);}
int main(){int t;rd(t);while(t--){ll p;rld(p);printf("%lld\n",f(p));}return 0;}