BZOJ3884 上帝与集合的正确用法

发表于 | 分类于 |
字数统计: 271 字

题目链接

题解

直接上欧拉定理降幂公式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
ll P,phi[10000005]={0};
ll Pow(ll a,ll b,ll c){
    a%=c;
    ll res=1;
    while(b){
        if(b&1)res=(res*a)%c;
        a=(a*a)%c,b>>=1;
    }
    return res;
}
ll getphi(ll N){
    ll res=N,t=N;
    for(ll i=2;i*i<=N;i++){
        if(t%i==0){
            while(t%i==0)t/=i;
            res/=i,res*=(i-1);
        }
        if(t==1)break;
    }
    if(t!=1)res/=t,res*=(t-1);
    return res;
}
ll dfs(ll p){
    if(p==1)return 0;
    //S=2^S=2^S mod phi P，what is S?
    if(!phi[p])phi[p]=getphi(p);
    return (Pow(2,dfs(phi[p])+phi[p],p));
}
void init(){
    phi[1]=1;
}
void solve(){
    int T=read();
    while(T--){
        P=read(),printf("%lld\n",dfs(P));
    }
}
int main(){
    init();
    solve();
    return 0;
}