(CF906D)Power Tower

原题链接

思路:

使用扩展欧拉定理计算幂塔, 即:

$\varphi(m)$的收敛速度是$\log m$级别的, 所以直接递归计算即可.

收敛速度的证明
引理: 对于$n>2$, $\varphi(n)$均为偶数.
可以使用更相减损法证明, 由于$(x,n)=(n-x,n)$, 所以这两个数成对互质或不互质
于是$n$有质因子2, 每次求$\varphi$都会至少除2, 所以收敛速度是$\log m$级别的.

分类讨论处理起来可能会稍微有点棘手. 代码中修改了一下快速幂, 当中间值比$m$大时则返回ret+m.

代码:

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <cmath>
#include <cctype>
using LL = long long;
const int Mn(100500);

template<typename T> void qrd(T& x) {
x = 0;
int c = getchar();
while(!isdigit(c)) {
c = getchar();
}
while(isdigit(c)) {
x = x*10+c-'0';
c = getchar();
}
}

int n;
LL p;
LL w[Mn], ph[Mn]; //ph为预处理的phi值

LL pksm(LL a, LL b, LL m) { //修改过的快速幂
LL ret(1), tmp(a%m);
bool isb = a>=m;
while(b) {
if(b&1) {
ret = ret*tmp;
if(ret>=m) {
ret %= m;
isb = true; //中间值>=m打标记
}
}
tmp = tmp*tmp;
if(tmp>=m) {
tmp %= m;
isb = true; //同上
}
b >>= 1;
}
return ret + m*(isb); //若>=m则加上m
}
LL get_phi(LL a) { //计算phi, sqrt(n)的复杂度
LL bn = sqrt(a), ret(1);
for(int i(2);i<=bn;++i) {
if(a%i==0) {
ret *= (i-1);
a /= i;
while(a%i==0) {
ret *= i;
a /= i;
}
if(a==1) {
break;
}
}
}
if(a==1) {
return ret;
} else {
return ret*(a-1);
}
}
LL solve(int l, int r, LL dm) { //计算幂塔
if(l==r+1 || ph[dm]==1) {
return 1; //当phi(m)=1时返回0+phi(m) = 1
}
LL pw = solve(l+1,r,dm+1);
return pksm(w[l],pw,ph[dm]);
}

int main() {
qrd(n); qrd(p);
for(int i(1);i<=n;++i) {
qrd(w[i]);
}
ph[0] = p;
for(int i(1);;++i) {
ph[i] = get_phi(ph[i-1]);
if(ph[i]==1) {
break;
}
}
int q; qrd(q);
while(q--) {
int l, r;
qrd(l), qrd(r);
printf("%lld\n",solve(l,r,0)%p);
}
return 0;
}