Luogu P4139 上帝与集合的正确用法
题目链接：Click here
Solution:
这道题就考你会不会扩展欧拉定理，根据扩展欧拉定理可知
\[a^b \equiv a^{(b\,mod\,\varphi(p))+\varphi(p)} \,(mod\,p)，b>\varphi(p) \]本题利用扩展欧拉定理，显然可得一个递归式，边界条件是\(\varphi(p)=1\)
线筛预处理\(\varphi(n)\)即可
Code:
#include
#define int long long
using namespace std;
const int N=1e7+11;
bool vis[N];
int Mod,cnt,ans,p[N],phi[N];
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int qpow(int a,int b,int mod){
int re=1;
while(b){
if(b&1) re=re*a%mod;
b>>=1;a=a*a%mod;
}return re%mod;
}
void prepare(){
phi[1]=1;
for(int i=2;i