解决 $a^{b^c……..} \% p$问题
由欧拉定理可知， 当 $gcd(a,p)=1$
$$a^{\phi(p)} ≡ 1 (mod \ p )$$
可推出降幂公式
- 若$gcd(a,p) =1 $
$$
a^b=a^{b \% \phi(p)}\% \ p
$$
这种情况暴力跌代出所有的$phi(…phi(p))$，然后从小到大枚举phi算即可
- 若$gcd(a,p) \not = 1 , b<\phi(p) $
$$
a^b=a^b\% \ p
$$
- 若$gcd(a,p) \not = 1 , b ≥ \phi(p)$
$$
a^b=a^{b \% \phi(p)+\phi(p)} \% \ p
$$
这种的也可以暴力算$phi$，然后从小到大枚举phi算即可
update：
考虑费马小定理$a^{p-1}\mod p=1$($p$是质数)，显然这也是满足欧拉函数降幂的，因为$p$是质数的时候显然$\phi(p)=p-1$