欧拉降幂

根据欧拉公式：
若$a$、$p$互质，则有$a^{\varphi (p)}\equiv 1 \space (mod \space p)$ 『$\varphi (p)$是$p$的欧拉函数值』

则有$$
a^b\equiv
\begin{cases}
a^{b \% \varphi(p)} & gcd(a,p)=1 \\
a^b &gcd(a,p) \not= 1,b<\varphi (p)& (mod \space p) \\
a^{b\% \varphi (p) + \varphi (p)} & gcd(a,p) \not= 1,b\geq \varphi (p)
\end{cases}
$$