费马定理/欧拉定理

约 101 个字

欧拉定理

若 $gcd(a,n)=1$

则 $a^{φ(n)}\equiv 1\pmod n$

费马小定理

费马小定理是n为质数的特例，即 $a^{n-1}\equiv 1\pmod n$

欧拉定理推论

若 $gcd(a,n)=1$

$a ^ b =(a \% n) ^ {b \% φ(n)} \pmod n$

例题

给定$a$,$n$,求$S=(((((a^a)^a)^a)^a)^a...)^a \pmod{998244353}$

共有$n$个$a$，$a$,$n$<=$1e18$

运用推论化简原式，得

$S=(a \% 998244353) ^ {a^{n-1} \% (998244353-1)}\pmod{998244353}$