(CF906D)Power Tower

发表于 分类于 ，

原题链接

思路:

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

\[ a^p \equiv \begin{cases} a^p & p<\varphi(m) \\ a^{p\ \mathrm{mod}\ \varphi(m) + \varphi(m)} & p \ge \varphi(m) \end{cases} \pmod m \]

\(\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
92
#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;
}