「BZOJ 3884」上帝与集合的正确用法

Description

题目链接:BZOJ 3884

求如下式子的值:

本题 $T$ 组数据。

数据范围:$1\le T\le 1000$,$1\le p\le 10^7$


Solution

首先我们可以根据扩展欧拉定理

得到:

很显然这是一个递归式子,边界条件为 $p=1$,此时式子的值为 $0$。

对于 $\varphi(p)$,我们可以线性筛预处理。

时间复杂度:$O(P+T\log p)$


Code

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
#include <cstdio>

const int N=1e7+5,M=N/10;
int n,tot,p[M],phi[N];
bool flg[N];

void sieve(int n) {
phi[1]=1;
for(int i=2;i<=n;++i) {
if(!flg[i]) p[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&i*p[j]<=n;++j) {
flg[i*p[j]]=1;
if(i%p[j]==0) {
phi[i*p[j]]=phi[i]*p[j];
break;
} else {
phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}
}
int pow(int x,int p,int mod) {
int ret=1;
for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ret=1LL*ret*x%mod;
return ret;
}
int solve(int p) {
if(p==1) return 0;
return pow(2,solve(phi[p])+phi[p],p);
}
int main() {
sieve(N-5);
int T;
for(scanf("%d",&T);T--;) {
int p;
scanf("%d",&p);
printf("%d\n",solve(p));
}
return 0;
}
0%