icpc数论费马小定理
小学一波数论
费马小定理
若 $p$ 为素数,$\gcd(a, p) = 1$,则 $a^{p - 1} \equiv 1 \pmod{p}$.
另一个形式:对于任意整数 $a$,有 $a^p \equiv a \pmod{p}$.
设一个质数为 $p$,我们取一个不为 $p$ 倍数的数 $a$.
构造一个序列:$A={1,2,3\dots,p-1}$,这个序列有着这样一个性质:
\prod_{i=1}^{n}\space A_i\equiv\prod_{i=1}^{n} (A_i\times a) \pmod p
\because gcd(A_i,p)=1,gcd(A_i\times a,p