bzoj3884: 上帝与集合的正确用法

题目链接

bzoj3884: 上帝与集合的正确用法

题解

官方题解：by popoqqq

代码

#include<cstdio>
#include<algorithm>

#define LL long long
const int maxn = 10000007;
inline LL read() {
    LL x = 0,f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}
    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar(); 
    return x * f;
}
int T,p,cnt;
int prime[maxn],phi[maxn];
bool is_prime[maxn];
void getphi() {
    phi[1] = 1;
    for(int i = 2;i <= 10000000;i ++) {
        if(! is_prime[i])phi[i] = i - 1,prime[++ cnt] = i;
        for(int j = 1;j <= cnt && i * prime[j] <= 10000000;j ++) {
            is_prime[i * prime[j]] = 1;
            if(i % prime[j] == 0){ phi[i * prime[j]] = phi[i] * prime[j];break;}
            else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
int pow(LL a,LL b,int p) {
    LL ret = 1;a %= p;
    for(LL i = b;i;i >>= 1,a = a * a % p) if(i & 1)ret = ret * a % p;
    return ret;
}
int solve(int p) {
    if(p == 1)return 0;
    int k = 0;
    while(~ p & 1)p >>= 1,k ++;
    int Tp = phi[p],ret = solve(Tp);
    ret = (ret + Tp - k % Tp) % Tp;
    ret = pow(2,ret,p) % p;
    return ret << k;
}
int main() {
    getphi();
    T = read();
    while(T--) {
        p=read();
        printf("%d\n",solve(p));
    }
    return 0;
}