童心智造2022.09.05线段树练习

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

$\phi (p)=a_1^{k_1}\ast a_2^{k_2}\ast ........\ast a_n^{k_n}$
$\phi (a_i^{k_i})=(a_i^{k_i}-a_i^{k_i})=a_i^{k_{i-1}}\ast (a_i-1)$
$\phi (p)=$ ${\prod }_{i=1}^n$ $\phi (a_i^{k_i})$
= ${\prod }_{i=1}^n(a_i-1)\ast a_i^{k_{i-1}}$
= ${\prod }_{i=1}^n$ $(1-\frac{1}{a_i})\ast a_i^{k_i}$
= $p\ast$ ${\prod }_{i=1}^n$ $(1-\frac{1}{a_i})$
所以如果遇到了偶数每次的 $\phi (p)$都会除2 遇到了奇数因为每次乘以 $(1-\frac{1}{a_i})$所以下一次必定为偶数 所以只需要log次就可以变为1
那么对于这题来说

如果每次都是最后一种情况
$b^c$ = $b^{cmod(\phi (p))+\phi (p)}modp$

$a^{{}^{b^c}}$ = $a^{{}^{b^{cmod(\phi (\phi (p)))+\phi (\phi (p))}mod(\phi (p))+\phi (p)}}modp$

我们发现其实每次增加一层的话 Cmod 后面的欧拉函数就多一层 所以最后在logn次修改后就剩下 mod 1 + 1 = 1再根据题目的C不变最终就变为 $c^{c^{{}^{c^c}}}$ 所以只要建立一颗线段树来存修改次数就行了
最后的复杂度就在大概 nlogn