三个定理
费马小定理
对于\(gcd(a,m)=1\)且\(m\)为质数，有\(a^{m-1}=1(mod\space m)\)。这个定理可以求模质数时的逆元。
(扩展)欧拉定理
欧拉定理
对于\(gcd(a,m)=1\)，有\(a^{\varphi(m)}=1(mod\space m)\)。这个定理可以求模任何数的逆元。
扩展欧拉定理
若\(b<\varphi(m)\)，\(a^b=a^b(mod\space m)\)，否则\(a^b=a^{b\space mod \space \varphi(m)+\varphi(m)}(mod\space m)\)。它的大致意思是，\(a^b(mod\space m)\)会先有一个长小于\(\varphi(m)\)的非循环部分，再是长为\(\varphi(m)\)因数的循环部分。模版题\(P5091\)。
\(Wilson\)定理
\((p-1)!=-1(mod\space p)\)，当且仅当\(p\)为质数。\(p\)不为质数，显然右边不等于\(-1\)。\(p\)为质数，\(2\)显然对，奇素数中，除\(1\)和\(p-1\)以外所有数都有逆元，且不等于自身，所以没有贡献。那\(1\times (p-1)=-1(mod\space p)\)，定理成立。
三个算法
(ex)Lucas定理
\(Lucas\)定理：
在\(p\)为质数时，\(\binom{n}{m} = \binom{n/p}{m/p}*\binom{n\space mod\space p}{m\space mod\space p}(mod\space p)\)。
所以，对于\(p\)进制数\(n=n0n1n2...\)和\(m=m0m1m2...\)，有\(\binom{n}{m}=\binom{n0}{m0}\binom{n1}{m1}\binom{n2}{m2}...(mod \space p)\)。这是一个十分良好的性质，可以用来进行数位\(dp\)等操作。
同时，它也有许多推论：
推论\(1\)：\(\binom{n}{m}=1(mod\space 2)\)，当且仅当二进制下，\(n\supseteq m\)。因为\(\binom{1}{1}\space \binom{1}{0}\space \binom{0}{0}=1\)，而\(\binom{0}{1}=0\)。这是一个十分良好的性质。
推论\(2\)：\(\binom{n}{m}\ne 0(mod\space p)\)，当且仅当\(p\)进制下\(n\)和\(m\)的加法无进位。因为一旦进位，就会乘一个\(\binom{a}{b},(a<b)\)。
推论\(2.2\)：\(\binom{n}{m}\)中\(p\)的因子个数为\(n+m\)的进位次数。这个我也不知道为什么。
所以，\(O(p)\)预处理好\(1\sim p-1\)的阶乘和逆元，就可以在\(O(logn)\)的时间内回答一次询问了。模版题\(P3807\)。
\(exLucas\)定理：
要求\(\binom{n}{m}\space mod \space p\)，其中\(1\le n,m\le 1e18,2\le p \le 1e6\)。此时\(Lucas\)定理彻底失效。
首先一个合数是很难处理的，我们要用\(CRT\)分解为\(\binom{n}{m}\space mod \space p^k\)的子问题，处理好之后合并起来即可。
显然\(\binom{n}{m}=\frac{n!}{m!(n-m)!}\)。此时最难的问题是下面没有逆元，所以很难处理。我们很容易想到把\(p\)部分和非\(p\)部分分开，所以我们对每个阶乘，都要求它非\(p\)部分的乘积和\(p\)的个数。\(p\)的个数即为\(n/p+n/p^2+n/p^3+...\)，这个东西其实等于\(n-n\)在\(p\)进制下的数位和，再除以\(p-1\)。这也能证明\(Lucas\)定理的推论\(2.2\)。
非\(p\)部分其实很好处理：考虑\(n=22,p=3,k=2\)。我们先乘两个\(1*2*4*5*7*8\)，再乘\(1*2*4\)，再乘\((22/3)!=7!\)里的非\(p\)部分即可。
实现上，我们先预处理一个类阶乘\(mtp_i\)，代表\(1\sim i\)内非\(p\)倍数的数之积，求它的逆元\(inv_i\)。然后，我们把整个的\(mtp_{p^k}\)个数算出来，把\(p\)的个数算出来，零散部分直接乘出来。这样，我们的复杂度即为\(O(p^k+logn)\)，算上外面的\(CRT\)，复杂度\(O(p+logplogn)\)。模版题\(P4720\)。
(ex)BSGS
俗称离散对数，是求\(a^x=n(mod\space m)\)的最小自然数解。思想是分块，按\(B\)分块，设\(x=iB-j(1\le i\le m/B,1\le j\le B)\)，则\(a^{iB}=na^j(mod\space m)\)是一个必要条件。此时，两种情况有两种处理办法：
BSGS
若\(gcd(a,m)=1\)，上面的就是充要条件。此时最方便的写法就是把右边放入一个\(map\)中，重复的就应该直接覆盖。然后枚举左边，查\(map\)即可，这样大概只需要\(26\)行。取\(B=\sqrt p\)，复杂度\(O(\sqrt p logp)\)。模版题\(P3846\)。
exBSGS
若无限制，则只能把左边放入\(map\)，对于相同的值，只保留前\(2\)个，然后用右边去查左边，对答案去\(min\)再输出。原因考虑扩展欧拉定理，若左边出现了相同值，由于\(j\le B\)，则只有第一个\(iB-j\)可能在非循环区，剩下的一定在循环区，所以只有前两个有用。这也是为什么不能用左边查右边。这个做法比大众做法简单很多，取\(B=\sqrt{2\varphi (p)}\)，复杂度\(O(\sqrt plogp)\)。模版题\(P4195\)。
一个有用的东西
阶与原根
阶
对于\(gcd(a,m)=1\)，\(a^x=1(mod\space m)\)的最小正整数解为\(a\)模\(m\)的阶，记作\(ord_m(a)\)。
求阶的办法：先求出\(\varphi(m)\)的所有素因子\(p_i\)，显然\(ord_m(a)|\varphi(m)\)。然后设\(ord=\varphi(m)\)，进行不断试除。只要\(p_i|ord\)，且\(a^{ord/p_i}=1(mod\space m)\)，那么\(ord/=p_i\)。这样最后求出的\(ord\)即为\(ord_m(a)\)。这样显然是对的。复杂度预处理\(O(\sqrt p)\)，判定\(O(log\space p)\)。
原根
若\(gcd(a,m)=1\)，有\(ord_m(a)=\varphi(m)\)，则称\(a\)为\(m\)的原根，一般记作\(g\)。
一个数\(m\)存在原根，当且仅当\(m=1,2,4,p^k,2\times p^k\)。其中\(1,2,4\)的原根分别为\(0,1,3\)。重要的是，素数有原根。
要求一个数的原根，首先先判定它有没有原根，并处理掉\(1,2,4\)。原根的判定和阶差不多，方便的是不用除了，能除就说明不行，不能除就说明行。我们要求这个数的最小正原根\(g\)。实验表明，\(g\)最大为\(m^{0.25}\)，且大数\(m\)的\(g\)不为多项式级别。所以直接搜即可。
求出\(g\)后，我们看\(g\)的几次方也是原根。重要的是，\(g^k(k\in[0,\varphi(m)-1])\)两两不同，且都与\(m\)互质，而与\(m\)互质的数恰有\(m\)个，这也是原根为何这么牛的原因。容易发现，\(g^k\)为原根，当且仅当\(gcd(k,\varphi(m))=1\)，所以若\(m\)有原根，则\(m\)的原根有\(\varphi(\varphi(m))\)个。直接输出即可。复杂度\(O(mlogm)\)，\(log\)是\(gcd\)的\(log\)。模版题\(P6091\)。
同时我们要记一下，\(g_{998244353}=3\)。原根在多项式、\(n\)次剩余领域有重要作用，一定要熟练掌握。