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

Description

求

Input

第一行一个整数TT,表示数据个数。
接下来TT行,每行一个正整数pp,代表你需要取模的值。

Output

TT行,每行一个正整数,为答案对pp取模后的值

Sample Input

1
2
3
4
3
2
3
6

Sample Output

1
2
3
0
1
4

HINT

对于100%100\%的数据,T1000T\leq 1000,p107p\leq 10^7

Solution

扩展欧拉定理

ab={ab%ϕ(c)(c,b)=1abb<ϕ(c)ab%ϕ(c)+ϕ(c)(c,b)1,bϕ(c)a^b=\begin{cases}a^{b\%\phi(c)} & (c, b)=1\\a^b & b<\phi(c)\\a^{b\%\phi(c)+\phi(c)} & (c,b)\neq1,b\ge\phi(c)\end{cases}

std

很显然22的无穷式一定是上面的第三个式子,我们递归就行了。
就剩下线性筛欧拉函数。
ϕ(n)=ni=1s(11pi)\phi(n)=n\prod_{i=1}^s(1-\frac{1}{p_i})

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<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e7 + 6;

int phi[N], b[820420], tot;

void init() {
phi[1] = 1;
for(int i = 2; i <= 1e7; ++i) {
if(!phi[i]) {
b[++tot] = i;
phi[i] = i - 1;
}
for(int j = 1; b[j] <= 1e7 / i && j <= tot; ++j) {
if(i % b[j] == 0) {
phi[i * b[j]] = phi[i] * b[j];
break;
} else phi[i * b[j]] = phi[i] * phi[b[j]];
}
}
}
ll ksm(ll x, ll y, ll p) {
ll res = 1;
for(; y; y >>= 1, x = x * x % p)
if(y & 1) res = res * x %p;
return res;
}
int solve(int x) {
if(x == 1) return 0;
return ksm(2, solve(phi[x]) + phi[x], x);
}
int main() {
init();
int T = read();
while(T--) {
int n = read();
writeln(ksm(2, solve(phi[n]) + phi[n], n));
}
return 0;
}