拔山蓋世

可以在 $O(\sqrt{p})$ 的时间里求解方程 $a^x \equiv b\pmod p$ 的整数解 $x$。

设 $t=\lfloor\sqrt{q}\rfloor$，$\forall j\in[0,t)\cap\mathbb{Z}$，都令 $x=i\times t-j$，那么就有：

$a^{i\times t-j}\equiv b\pmod p$

同时乘以 $a^{j}$ 得到：

$(a^{i})^t\equiv b\times a^j\pmod p$

那么枚举所有的 $j$，把 $b\times a^j$ 丢到一个集合里。

然后再枚举 $i$，查询集合里是否有 $(a^t)^i$，这样就知道了 $i,j$ 也就知道了 $x$ 了。

CF919E Congruence Equation

因为 $a^x\equiv a^{x+(p-1)}\pmod p$，$x\equiv x+p\pmod p$，所以 $x\times a^x\bmod p$ 的值是以 $p\times (p-1)$ 为周期的。

令 $x=k(p-1)+r$ 其中 $0\le r< p-1$，$k,r\in\mathbb{Z}^+$。

那么原式就可以写作：

$(r-k)\times a^r\equiv b\pmod p$

移项，得到：

$r-k\equiv b\times a^{-r}\pmod p$

枚举 $r$，计算 $k$，得到 $x$。

CF906D Power Tower

为什么会有一个叫欧拉降幂版的玩意，欧拉就知道 xjb 在哪里乱开发一些东西。

$a^b=\left\{\begin{matrix}a^b& b<\phi (p)\\a^{b\bmod \phi(p)+\phi(p)}&\text{Other wise.}\end{matrix}\right.$

设 $f(l,r,p)$ 表示 $w_l^{w_{l+1}^{\cdots^{w_r}}}\bmod p$，如果 ${w_{l+1}}^{w_{l+2}^{\cdots^{w_r}}}\bmod p\ge \phi(p)$，就有 $f(l,r,p)={w_l}^{f[l+1,r,\phi(p)]+\phi(p)}\bmod p$。

对指数进行递归求解，直到当递归到 $p=1$ 或者 $l=r+1$ 时停止，返回 $1$。

因为当 $p$ 为偶数时 $\phi(p)\le \dfrac{p}{2}$，且当 $p$ 为奇数时 $2\mid \phi(p)$，所以递归的次数不会超过 $\log p$。

CF757E Bash Plays with Functions

设 $g(x)$ 表示 $x$ 互不相同的质因子个数，容易理解 $f_0(n)=2^{g(n)}$。

$f_{r}(n)=\sum\limits_{d\mid n} f_{r-1}(n)$

所以 $f_r$ 是积性函数，所以：

$f_r(n)=\prod f({a_i}^{b_i})$

同时还有：

$f_r({a_{i}}^{b_i})=\sum\limits_{j=0}^{b_i} f_{r-1}({a_i}^j)$

因为 $f_0({a_i}^{b_i})=2$，所以可以递推求解。

因为 $f$ 的值与 $a_i$ 无关，所以对于所有的 $r$ 和 $b_i$ 全部预处理，因为 $b_i\le \log_2(n)$。

时间复杂度为 $O(r\log n)$。

CF1097D Makoto and a Blackboard

对于 $n=p^{\alpha}$ 的情况，设 $f_{i,j}$ 表示有 $i$ 次操作之后变成 $p^j$ 的概率。

那么 $f_{i,j}=\sum\limits_{t=j}^{\alpha}\dfrac{f_{i-1,t}}{t+1}$，那么简化一下就是 $f_{i,j}=f_{i,j+1}+\dfrac{f_{i-1,j}}{j+1}$。

因为每一个质因子相互独立，所以直接乘起来。

HDU 5628 Clarke and math

当 $k=1$ 时：

$g(i)=\sum\limits_{i_1\mid i} f(i_1)=\sum\limits_{ab=1}f(a)\times 1(b)=(f*1)(i)$

当 $k=2$ 时：

$g(i)=\sum\limits_{i_1\mid i}\sum_{i_2\mid i_1} f(i_2)=\sum\limits_{i_1\mid i} g(i_1)=\sum\limits_{ab=i} g(a)\times 1(b)=(f*1^2)(i)$

所以得到：

$g(i)=(f*1^k)(i)$

六省联考 2017 相逢是问候

$a^b=\left\{\begin{matrix}a^b& b<\phi (p)\\a^{b\bmod \phi(p)+\phi(p)}&\text{Other wise.}\end{matrix}\right.$

对于一大堆修改操作之后，肯定是 $c^{c^{c^{a_i}}}$ 这种形式的，考虑欧拉降幂。

对于每一次降幂之后，$p\gets \varphi(p)$ 所以最多 $\log p$ 次。

所以只有前 $\log p$ 操作有效，重口味线段树，有势能所以做完了。