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

发表于 | | 阅读次数:
字数统计: 333 字

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%