欧拉降幂_杂项

欧拉降幂

扩展欧拉定理：

$$a^b\equiv\left\{\begin{aligned}&a^{b\bmod\varphi (m)},&&a\perp m\\&a^b,&&a\not\perp m,b<\varphi(m)\\&a^{b\bmod \varphi (m)+\varphi (m)},&&a\not\perp m,b\ge \varphi(m)\end{aligned}\right.\pmod m$$

运用欧拉定理 $\forall a\perp m,a^b\equiv a^{b\bmod \varphi(m)}\pmod m$，可以将上式简化为：

$$a^b\equiv\left\{\begin{aligned}&a^b,&&b<\varphi(m)\\&a^{b\bmod \varphi (m)+\varphi (m)},&&b\ge \varphi(m)\end{aligned}\right.\pmod m$$

考虑幂塔方程 $a^{b^{c^{d^{e}}}}\pmod m$ 这种东西，我们可以递归求解，每一层就是套了一层 $\varphi$，不断套 $\varphi$ 的复杂度其实是 $\Theta(\log m)$。

所以我们套了几步之后就变成了 $\bmod \ 1$，此时就可以返回，加上快速幂的复杂度为 $\Theta(\log^2 m)$，可以提前预处理 $\varphi(m),\varphi(\varphi(m)),\cdots$，使用根号求 $\varphi$ 即可。

CF906D Power Tower

给定一个数列 $w_1,w_2,...,w_n$ 和模数 $p$，每次询问一个区间 $[l,r]$ 求 $w_l^{w_{l+1}^{w_{l+2}^{{...}^{w_r}}}} \pmod p$。

$n\le 10^5$。

套用模板即可，注意快速幂的写法不一样。

ll ksm(ll a,ll n,ll p) {
    auto mo=[&](ll a) {return a>p?a%p+p:a;};
    ll res=1;for(;n;n>>=1,a=mo(a*a)) if(n&1) res=mo(res*a);
    return res;
}
ll dfs(ll c) {
    if(c>r-l||ph[c]==1) return 1;
    return ksm(a[l+c],dfs(c+1),ph[c]);
}
ph[0]=p;F(i,1,1e3) if(ph[i-1]^1) ph[i]=phi(ph[i-1]);else break;
F(i,1,read()) {
    l=read();r=read();
    printf("%lld\n",dfs(0)%p);
}

P4139 上帝与集合的正确用法

给定 $p$，求 $2^{2^{2\cdots}}\pmod p$ 收敛于什么值。

$p\le 10^7$。

套用模板即可。

有一个很容易产生的误区就是我以为可以初始令 $a=2$，然后每次令 $a\gets 2^a\bmod p$，若 $a=2^a$ 则结束。

但是你取 $p=7$ 发现根本没有这种值。

事实上我们错在每次对 $p$ 取模，这也表明了遇到类似的题一定要看清楚是 $a\gets 2^a\bmod p$ 还是 $a\gets 2^a$ 最后 $\bmod\ p$。

P3747 [六省联考 2017] 相逢是问候

维护一个长度为 $n$ 的数组。

一共有 $m$ 个操作：

• 0 l r 表示将第 $l$ 个到第 $r$ 个数中的每一个数赋值 $a_i = c^{a_i}$。
• 1 l r 求第 $l$ 个到第 $r$ 个数的和，也就是输出： $\sum_{i=l}^{r}a_i$

输出结果 $\bmod \space p$ 的值。

$n,m\le5\times 10^4$。

套用模板即可，势能线段树。

$\Theta(n\log^3 n)$ 难以通过，考虑模数种类很少，且底数唯一，光速幂优化即可。