欧拉降幂公式-目前只会公式

$一：降幂公式$
$A^{B}(\%n)\equiv A^{B\%\phi (n)+\phi (n)}(\%n)$
$\phi (n)是n的欧拉函数,A和n互质$
$二：欧拉函数$
$1.\phi (1)=1$
$2.\phi (n)=n-1,n为质数$
$3.欧拉定理：对于互质的正整数a和n，有a^{φ(n)} \equiv 1(\%n)$
$4.欧拉函数是积性函数：若m,n互质，φ(n*m)=φ(n)*φ(m)$
$5.n是质数p的k次幂，有φ(n)=p^k-p^{(k-1)}=(p-1)p^{(k-1)}，因为除了p的倍数外，其他数都跟n互质。$
$p*(1\sim p^{(k-1)})都和n不互质，多算了一个数p^k$
$p^k个数1\sim n，也多算了一个p^k$
图片说明
$欧拉函数模板：$
模板