解题：BZOJ 3884 上帝与集合的正确用法

好久以前写的，发现自己居然一直没有写题解=。=

扩展欧拉定理：在$b>φ(p)$时有$a^b equiv a^{b\%φ(p)+φ(p)}(mod$ $p)$

然后每次递归那个$a^{b\%φ(p)}$的部分，最后在$φ(p)=1$时返回即可

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=1e7+70;
 6 int pri[N],npr[N],phi[N];
 7 long long T,mod;
 8 void prework()
 9 {
10     phi[1]=1,npr[1]=true;
11     for(int i=2,sz=0;i<=10000000;i++)
12     {
13         if(!npr[i]) pri[++sz]=i,phi[i]=i-1;
14         for(int j=1;j<=sz&&i*pri[j]<=10000000;j++)
15         {
16             npr[i*pri[j]]=true; 
17             phi[i*pri[j]]=phi[i]*pri[j];
18             if(i%pri[j]) phi[i*pri[j]]-=phi[i]; else break;
19         }
20     }
21 }
22 long long qpow(long long x,long long k,long long md)
23 {
24     if(k==1) return x%md;
25     long long tmp=qpow(x,k/2,md);
26     return k%2?tmp*tmp%md*x%md:tmp*tmp%md;
27 } 
28 long long Gas(long long md)
29 {
30     return md==1?0:qpow(2,Gas(phi[md])+phi[md],md);
31 }
32 int main ()
33 {
34     scanf("%lld",&T),prework();
35     while(T--)
36     {
37         scanf("%lld",&mod);
38         printf("%lld
",Gas(mod));
39     }
40     return 0;
41 } 
42

View Code