题解 CF906D Power Tower

一道比较裸的扩欧模板题

扩展欧拉定理

$$a^c=\begin{cases}a^{c~mod`\phi(p)},gcd(a,p)=1\\a^c,gcd(a,p) \ne1,c < \phi(p)\\a^{c~mod~\phi(p)+\phi(p)},gcd(a,p)=1,c\ge \phi(p)\end{cases}$$

具体证明就不再这里讲解了主要是不会

很明显,可以直接用欧拉定理递归降幂,那么怎么保证时间复杂度是对的呢

我们将m分解为 $\prod\limits_{i=1}^k p_i^{q_i}$

那么 $\phi(m)=\phi(\prod\limits_{i=1}^k p_i^{q_i})=\prod\limits_{i=1}^k (p_i-1)p_i^{q_i-1}$

到这里就可以看出,每迭代一遍欧拉函数,就相当于把 $m$ 中的所有质因子全部取出来减个一再乘回去,要得到 $\phi(m)=1$,只需要迭代 $m$ 中每个质因子可以取出来的2的数量,时间复杂度是 $log$ 级的

对于题目中的每一个 $\phi$ 可以先预处理一遍,用 $map$ 存起来

代码

#include<iostream>
#include<cstdio>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;

unordered_map<ll, ll> phi;
ll w[N];

ll pi(ll p)
{
    ll res = p;
    for (ll i = 2; i * i <= p; i++)
    {
        if (p % i == 0)
            res -= res / i;
        while (p % i == 0)
            p /= i;
    }
    if (p > 1)
        res -= res / p;
    return res;
}

ll qmi(ll a, ll b, ll c)
{
    ll res = 1;
    bool flag = false;
    while (b)
    {
        if (b & 1)
        {
            res *= a;
            if (res >= c)
                flag = true;
            res %= c;
        }
        a *= a;
        if (a >= c)
            flag = true;
        a %= c;
        b >>= 1;
    }
    if (flag)
        res += c;//需要满足欧拉定理
    return res;
}

ll dfs(ll l, ll r, ll p)
{
    if (l == r + 1 || p == 1)
        return 1;
    return qmi(w[l], dfs(l + 1, r, phi[p]), p);
}

int main()
{
    ll n, p;
    scanf("%lld%lld", &n, &p);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &w[i]);
    ll now = p;
    while (now != 1)
        phi[now] = pi(now), now = phi[now];
    phi[now] = 1;
    ll q;
    scanf("%lld", &q);
    while (q--)
    {
        ll l, r;
        scanf("%lld%lld", &l, &r);
        printf("%lld\n", dfs(l, r, p) % p);
    }
    return 0;
}