注：若无说明，数值范围均为\mathbf{Z}Z的子集
\large\texttt{欧几里得算法}欧几里得算法若a<b,\gcd(b,a\bmod b)=\gcd(b,a)=\gcd(a,b)a<b,gcd(b,amodb)=gcd(b,a)=gcd(a,b)
若a\geqslant b,a=q\times b+r,0\leqslant r<ba⩾b,a=q×b+r,0⩽r<b
r=a\bmod br=amodb
对于a,ba,b的任意公约数dd，d|(a-qb)d∣(a−qb)，即d|rd∣r，因此dd也是b,rb,r的公约数。
递归写法：
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}非递归写法：
int gcd(int a,int b){
while(a^=b^=a^=b%=a);return b;
}\large\texttt{欧拉函数 }\varphi\left(N\right)=N\prod_{\text{质数}p|N}\left(1-\frac{1}{p}\right)欧拉函数 φ(N)=N质数p∣N∏(1−p1)
证明：[1,N][1,N]中不与NN含有共同质因子pp或qq的个数为N-\dfrac{N}{p}-\dfrac{N}{q}+\dfrac{N}{pq}=N\left(1-\dfrac{1}{p}-\dfrac{1}{q}-\dfrac{1}{pq}\right)=N\left(1-\dfrac{1}{p}\right)\left(1-\dfrac{1}{q}\right)N−pN−qN+pqN=N(1−p1−q1−pq1)=N(1−p1)(1−q1)
可推广至多个数的情况
性质：
1.1. 是积性函数
2.2. \forall n>1,[1,n]∀n>1,[1,n]中与nn互质的数的和为\dfrac{n\times\varphi(n)}{2}2n×φ(n)
3.3. 若p|np∣n且p^2|n,p2∣n,则\varphi(n)=\varphi\left(\dfrac{n}{p}\right)\times pφ(n)=φ(pn)×p
4.4. 若p|np∣n但p^2\nmid n,p2∤n,则\varphi(n)=\varphi\left(\dfrac{n}{p}\right)\times(p-1)φ(n)=φ(pn)×(p−1)
5.5. \sum\limits_{d|n}\varphi(d)=nd∣n∑φ(d)=n
int phi(int n){
int ans=n;
for(int i=2;i*i<=n;++i)
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)ans=ans/n*(n-1);
return ans;
}线性筛欧拉函数
phi[1]=1;
for(int i=2;i<=N;++i){
if(!np[i]){
p[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*p[j]<=N;++j){
np[i*p[j]]=true;
phi[i*p[j]]=phi[i]*(i%p[j]?p[j]-1:p[j]);
if(i%p[j]==0)break;
}
}\large\texttt{扩展欧几里得}扩展欧几里得求解同余方程 ax\equiv1\pmod bax≡1(modb)
即ax+by=1ax+by=1
\because \gcd(a,b)|ax+by∵gcd(a,b)∣ax+by
\therefore 1\bmod \gcd(a,b)=0∴1modgcd(a,b)=0
\therefore∴ 方程有解的必要条件是 \gcd(a,b)=1gcd(a,b)=1
以下为解的求法
设x,yx,y是ax+by=\gcd(a,b)ax+by=gcd(a,b)的一组解
x_2,y_2x2,y2是ax_2+by_2=\gcd(b,a\bmod b)ax2+by2=gcd(b,amodb)的一组解
ax+by=\gcd(a,b)=\gcd(b,a\bmod b)=bx_2+(a\bmod b)y_2ax+by=gcd(a,b)=gcd(b,amodb)=bx2+(amodb)y2
=bx_2+\left(a-b\left\lfloor \dfrac{a}{b}\right\rfloor\right)y_2=bx2+(a−b⌊ba⌋)y2
=bx_2+ay_2-by_2\left\lfloor \dfrac{a}{b}\right\rfloor=bx2+ay2−by2⌊ba⌋
=ay_2+b\left(x_2-y_2\left\lfloor \dfrac{a}{b}\right\rfloor\right)=ay2+b(x2−y2⌊ba⌋)
当x_2,y_2x2,y2求出后，方程一组解为x=y_2,y=x_2-y_2\left\lfloor \dfrac{a}{b}\right\rfloorx=y2,y=x2−y2⌊ba⌋
综上，当b\ne 0b=0时，递归求解，否则x=1,yx=1,y取任意整数
对于一般的线性同余方程ax\equiv b\pmod cax≡b(modc)
可以写成ax+cy=bax+cy=b，有解的充要条件是\gcd(a,c)|bgcd(a,c)∣b
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b){ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;}
x=1;y=0;return a;
}\large\texttt{乘法逆元}乘法逆元若ax\equiv1\pmod pax≡1(modp)，且aa与pp互质，则定义xx为aa的逆元，记为a^{-1}a−1
用于在模意义下做除法
费马小定理
如果pp是质数，那么a^{p-1}\equiv1\pmod pap−1≡1(modp)
\because ax\equiv 1\pmod p∵ax≡1(modp)
\therefore ax\equiv a^{p-1}\pmod p∴ax≡ap−1(modp)，即x=a^{p-2}x=ap−2，用快速幂求解
欧拉定理
如果a,pa,p互质，a^{\varphi(p)}\equiv1\pmod paφ(p)≡1(modp)
当pp为质数时，\varphi(p)=p-1φ(p)=p−1
x=a^{p-2}x=ap−2，快速幂
解同余方程
由于\gcd(a,p)=1gcd(a,p)=1，原方程等价于ax+py=1ax+py=1，扩欧求解即可
线性递推
令k=\left\lfloor\dfrac{p}{i}\right\rfloor,r=p\bmod ik=⌊ip⌋,r=pmodi则p=ki+rp=ki+r
则ki+r\equiv0\pmod pki+r≡0(modp)
kr^{-1}+i^{-1}\equiv0\pmod pkr−1+i−1≡0(modp)
i^{-1}\equiv-kr^{-1}\pmod pi−1≡−kr−1(modp)
即i^{-1}=-\left\lfloor\dfrac{p}{i}\right\rfloor(p\bmod i)^{-1}i−1=−⌊ip⌋(pmodi)−1
为了保证0<i^{-1}<p0<i−1<p，将上式写成i^{-1}=\left(p-\left\lfloor\dfrac{p}{i}\right\rfloor\right)(p\bmod i)^{-1}\bmod pi−1=(p−⌊ip⌋)(pmodi)−1modp
inv[1]=1;
for(int i=2;i<=N;++i)inv[i]=(p-p/i)*inv[p%i]%p;阶乘逆元
\dfrac{1}{n!}\equiv\dfrac{n+1}{(n+1)!}\pmod pn!1≡(n+1)!n+1(modp)
可以先求出n!n!的逆元，倒推求出i!i!的逆元(1\le i<n)(1≤i<n)
也可以线性求[1,n][1,n]的逆元后递推得到
离线逆元
要离线求nn个数的逆元
线性递推出前缀积和前缀积逆元即可
\mathcal O(n+\log p)O(n+logp)
\large\texttt{裴蜀定理}裴蜀定理\gcd(a,b)|c\texttt{是}ax+by=c\left(x,y\in \mathbf Z\right)\texttt{有解的充要条件}gcd(a,b)∣c是ax+by=c(x,y∈Z)有解的充要条件
必要性证明：
设d=\gcd(a,b)d=gcd(a,b)，则d|a,a|bd∣a,a∣b
\therefore d|ax,d|by∴d∣ax,d∣by
\therefore d|c∴d∣c，即\gcd(a,b)|cgcd(a,b)∣c
解可用扩欧求得
\large\texttt{莫比乌斯函数 }\mu莫比乌斯函数 μ
设NN的质因数分解为N=\prod\limits_{i=1}^{m}p_i^{c_i}N=i=1∏mpici
\mu(N)=\begin{cases}1&N=1\\(-1)^{m}&N>1,\forall i\in[1,m],c_i=1\\0&N>1,\exists i\in[1,m],c_i>1\end{cases}μ(N)=⎩⎪⎪⎨⎪⎪⎧1(−1)m0N=1N>1,∀i∈[1,m],ci=1N>1,∃i∈[1,m],ci>1
性质：
1.1. 是积性函数
2.2. \sum\limits_{d|n}\mu(d)=[n=1]=\begin{cases}1&n=1\\0&n>1\end{cases}d∣n∑μ(d)=[n=1]={10n=1n>1
，且\muμ是满足该性质的唯一积性函数
3.3. \sum\limits_{d|n}\dfrac{\mu(d)}d=\dfrac{\varphi(n)}{n}d∣n∑dμ(d)=nφ(n)
线性筛\muμ：
mu[1]=1;
for(int i=2;i<=N;++i){
if(!np[i]){
p[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot&&i*p[j]<=N;++j){
np[i*p[j]]=true;
mu[i*p[j]]=(i%p[j]?-mu[i]:0);
if(i%p[j]==0)break;
}
}莫比乌斯反演
F(n)=\sum\limits_{d|n}f(d)\Leftrightarrow f(n)=\sum\limits_{d|n}\mu(d)F\left(\dfrac{n}{d}\right)F(n)=d∣n∑f(d)⇔f(n)=d∣n∑μ(d)F(dn)
\Large\texttt{中国剩余定理 CRT/EXCRT}中国剩余定理 CRT/EXCRT
用于求解同余方程组\begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \\ x\equiv a_2\ ({\rm mod}\ m_2) \\ ... \\ x \equiv a_n\ ({\rm mod}\ m_n)\end{cases}⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧x≡a1 (mod m1)x≡a2 (mod m2)...x≡an (mod mn)
CRT
若m_1,m_2,\dots,m_nm1,m2,…,mn两两互质
设M_i=\dfrac{\prod\limits_{j=1}^nm_j}{m_i},t_iMi=mij=1∏nmj,ti是M_it_i\equiv 1\pmod{m_i}Miti≡1(modmi)的一个解
则原方程的一个解为x=\sum\limits_{i=1}^na_iM_it_ix=i=1∑naiMiti，通解为x+k\prod\limits_{j=1}^nm_j,k\in\mathbf{Z}x+kj=1∏nmj,k∈Z
将解代入方程即可证明
EXCRT
若m_imi不一定两两互质
设m=\mathrm{lcm}(m_1,m_2,\dots,m_{k-1})m=lcm(m1,m2,…,mk−1)
假设前k-1k−1个方程的解为xx，且存在t\in\mathbf{Z}t∈Z使x+tm\equiv a_k\pmod{m_k}x+tm≡ak(modmk)
x'=x+tmx′=x+tm就是前kk个方程的一个解
上述同余方程可用扩欧求解
\Large\texttt{Baby Step,Giant Step}Baby Step,Giant Step
用于求解同余方程a^x\equiv b\pmod max≡b(modm)
BSGS
若a,ma,m互质，可以在模mm意义下进行除法
设t=\left\lceil\sqrt m\right\rceil,x=it+j~(0\le i\le t~0\le j< t)t=⌈m⌉,x=it+j (0≤i≤t 0≤j<t)
即a^{it+j}\equiv b\pmod mait+j≡b(modm)
对于0\le j<t0≤j<t，将a^jaj插入\texttt{Hash}Hash表
枚举ii，查找是否有解
EXBSGS
不保证a,ma,m互质
\because a^x\equiv b\pmod m∵ax≡b(modm)
\therefore a^{x-1}\times a\equiv b\pmod m∴ax−1×a≡b(modm)
\therefore a\times a^{x-1}+m\times k=b∴a×ax−1+m×k=b
设d=\gcd(a,m)d=gcd(a,m)
由裴蜀定理，若d\nmid bd∤b，方程无整数解
若d\mid bd∣b，则a^{x-1}\dfrac ad\equiv\dfrac b d\pmod{\dfrac m d}ax−1da≡db(moddm)
即a^{x-1}\equiv\dfrac{\dfrac bd}{\dfrac ad}\pmod{\dfrac md}ax−1≡dadb(moddm)
若\gcd\left(a,\dfrac md\right)=1gcd(a,dm)=1，用BSGS求解
否则，重复上述过程
\Large\texttt{Lucas定理}Lucas定理
用于求\binom nm\bmod p(mn)modp
Lucas
若pp为质数，则\binom nm\equiv \binom{\left\lfloor\frac np\right\rfloor}{{\left\lfloor\frac mp\right\rfloor}}\times \binom{n\bmod p}{m\bmod p}\pmod p(mn)≡(⌊pm⌋⌊pn⌋)×(mmodpnmodp)(modp)
引理:(1+x)^p\equiv1+x^p\pmod p:(1+x)p≡1+xp(modp)
用二项式定理展开即得证
设k=\left\lfloor\dfrac np\right\rfloor,r=n\bmod pk=⌊pn⌋,r=nmodp，则n=kp+rn=kp+r
\therefore(1+x)^n=(1+x)^{kp+r}=((1+x)^p)^k(1+x)^r\equiv(1+x^p)^k(1+x)^r\pmod p∴(1+x)n=(1+x)kp+r=((1+x)p)k(1+x)r≡(1+xp)k(1+x)r(modp)
\therefore\sum\limits_{i=0}^n\binom nix^i\equiv\sum\limits_{i=0}^k\binom kix^{pi}\sum\limits_{j=0}^r\binom rjx^j\pmod p∴i=0∑n(in)xi≡i=0∑k(ik)xpij=0∑r(jr)xj(modp)
观察x^mxm项的系数，得
\binom nm\equiv \binom k{\left\lfloor\frac mp\right\rfloor}\binom r{m\bmod p}\pmod p(mn)≡(⌊pm⌋k)(mmodpr)(modp)
EXLucas
若pp为合数，分解质因数得到p=\prod_{i=1}^kp_i^{c_i}p=∏i=1kpici
求出所有\binom nm\bmod p_i^{c_i}(mn)modpici，使用\texttt{CRT}CRT合并答案
\binom nm=\frac{n!}{m!(n-m)!}(mn)=m!(n−m)!n!
提出分子分母中的质因数p_ipi，放到最后计算
考虑如何求\frac{n!}{\gcd(n!,p^{\infty})}gcd(n!,p∞)n!，即n!n!剔除质因数