求
对于 $100%$ 的数据，有数据组数 $T leq 1000$ ， $p leq 10^7$
题目链接戳这里
Solution
根据 扩展欧拉定理 ，即当 $b geq varphi (p)$ 时，
而当 $b < varphi(p)$ 时，
貌似没啥用？
由于题目中的 $b$ 是 $2^{2 cdots}$ ，所以一定有 $b geq varphi(p)$，因此递归一下式子就做完了。
具体如下：
1
2
3
4
|
ll (ll m) {
if (m == 1) return 0;
return qpow(2, work(phi[m]) + phi[m], m);
}
|
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
41
42
43
44
45
|
using namespace std;
typedef long long ll;
const int N = 10000100;
ll T, P, p[700700], phi[N], cnt;
bool vis[N];
inline void prework() {
phi[1] = 1;
for (int i = 2; i <= 1e7; i++) {
if (!vis[i]) p[++cnt] = i, phi[i] = i - 1;
for (int j = 1; j <= cnt && i * p[j] <= 1e7; j++) {
vis[i * p[j]] = true;
if (i % p[j] == 0) { phi[i * p[j]] = phi[i] * p[j]; break ; }
else phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
}
inline ll qpow(ll a, ll b, ll mod) {
ll res = 1;
while (b) {
if (b & 1) (res *= a) %= mod;
(a *= a) %= mod, b >>= 1;
}
return res;
}
inline ll (ll m) {
if (m == 1) return 0;
return qpow(2, work(phi[m]) + phi[m], m);
}
int main() {
prework();
scanf("%lld", &T);
while (T--) {
scanf("%lld", &P);
printf("%lldn", (work(P) + P) % P);
}
return 0;
}
|
PS：我没有研究 long long 是否必要，只是保险罢了
近期评论