这个笔记想写得稍微详细一点，部分内容来自我自己之前的博客: OI 里的数学内容整理（提高组）。
其中一些公式是 AI 从 PPT 上识别的，格式混乱，还请谅解。
整数分解与筛法
欧几里得算法
用于求解两个数的最大公因数。
$\gcd(a,b)=\gcd(b,a\bmod b)$。
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
扩展欧几里得算法与裴蜀定理
用于求解 $ax+by=\gcd(a,b),\ a,b \in N$ 的一组整数解 $(x,y)$。
int exgcd(int a,int b,int &x,int &y){//注意：结果x,y可能是负数,但是输入的a,b需要均为正数！！！
if(b==0){x=1;y=0;return a;}
int GCD=exgcd(b,a%b,x,y);
int tmp;tmp=x;
x=y;y=tmp-a/b*y;
return GCD;
}
也可以用于求逆元：
求 $a\pmod{b}$ 意义下的逆元等价于求一个 $x$ 满足 $ax\equiv1\pmod{b}$，由于逆元存在，$a$ 与 $b$ 互质，故 $\gcd(a,b)=1$，所以即求 $ax+by=1=\gcd(a,b)$ 的解 $x$，显然可以用扩欧解决。
例题：青蛙的约会
裴蜀定理（前置定理）：对于 $ax+by=\gcd(a,b),\ a,b \in N$，一定存在一组整数 $x,y$ 使得该式成立。
裴蜀定理扩展：对于 $a_1x_1+a_2x_2 \dots+a_nx_n=\gcd(a_1,a_2 \dots a_n),\ a_i\in N$，一定存在一组整数 $x_1,x_2\dots x_n$ 使得该式成立。
算术基本定理（整数的分解）
任何一个大于 $1$ 的正整数 $N$ 都能唯一分解为有限个质数的乘积，即：$N=p_1^{c_1}p_2^{c_2}\dots p_m^{c_m}$。
埃氏筛
bool not_prime[N];
int tot;
int pri[N];
void Sieve_of_Eratosthenes(int nn){
for(int i=2;i<=nn;i++){
if(!not_prime[i]){
pri[++tot]=i;
for(int j=2*i;j<=n;j+=i){
not_prime[j]=1;
}
}
}
}
时间复杂度：$O(n\log(\log n))$。
欧拉筛
bool not_prime[N];
int tot;
int pri[N],phi[N];
void Euler_Sieve(int nn){
for(int i=2;i<=nn;i++){
if(!not_prime[i]) pri[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&i*pri[j]<=nn;j++){
not_prime[pri[j]*i]=1;
if(i%pri[j]==0){
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
}
时间复杂度：$O(n)$。其中的 $phi$ 数组表示欧拉函数，将在后面的内容中提及。
例题：Sum of Consecutive Prime Numbers
质因数分解
暴力 $O(\sqrt n)$，预处理所有质数可以做到单次询问 $O(\frac{\sqrt n}{\log n})$。
例题：Prime Land
Stein 算法（大整数的 GCD）
- 如果 $a=0$ 或 $b=0$，则 $(0,b)=b,(a,0)=a$
- 如果 $a,b$ 均为偶数，则 $(a,b)=(\frac{a}{2},\frac{b}{2})$
- 如果 $a$ 是偶数，$b$ 是奇数，则 $(a,b)=(\frac{a}{2},b)$
- 如果 $a$ 是奇数，$b$ 是偶数，则 $(a,b)=(a,\frac{b}{2})$
- 如果 $a,b$ 均为奇数，不妨设 $a> b$则 $(a,b)=(b,a-b)$
时间复杂度为 $O((\log(\max{a,b}))^2)$，这个算法的应用场合是高精度，因为高精度取模速度很慢，而减法和除以 $2$ 则较快。
同余与模
逆元
若 $ab\equiv 1(\mod m)$，则称 $a,b$ 在 $\mod m$ 意义下互为逆元。
可以通过扩展欧几里得算法求出。若 $m$ 是质数，也可以通过费马小定理求出（稍后介绍）。
但如果要求出 $n$ 个数的逆元，有以下线性求法：
ll inv[N];
void init_inv(int nn,int p){
inv[1]=1;
for(int i=2;i<=nn;i++){
inv[i]=(ll)(p-p/i)*inv[p%i]%mod;
}
}
该算法利用了 $\lfloor \frac{p}{i}\rfloor +p\%i=p$ 即 $\lfloor \frac{p}{i}\rfloor +p\%i \equiv 0 (\mod p)$ 这一公式推导而得。
模板题：乘法逆元
欧拉函数
记 $\varphi(n)$ 为 $\le n$ 的正整数中与 $n$ 互质的数的个数（因此 $\varphi(1)=1$）。
通式：$\varphi(n)=n \prod\limits_{i=1}^{n}(1-\frac{1}{p_i})$，其中 $p_1,p_2\dots p_n$ 为 $n$ 的所有不重复的质因数。
记 $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$，则也有 $\varphi(n)=(p_1-1)p_1^{\alpha_1-1}\times(p_2-1)p_2^{\alpha_2-1}\times \dots \times (p_k-1)p_k^{\alpha_k-1}$。
容易发现，当 $p$ 为一个质数时，有 $\varphi(p)=p-1$。
可以通过欧拉筛线性求出所有欧拉函数（见上文），但如果只需要求一项欧拉函数，也可以暴力求。
ll phi(int x){
int ret=1,ori=x;
for(int i=2;i*i<=ori;i++){
int cnt=0;
while(x%i==0){
x/=i;cnt++;
if(cnt==1) ret*=(i-1);
else ret*=i;
}
}
if(x>1) ret*=(x-1);
return ret;
}
欧拉定理和费马小定理
欧拉定理：对于任意互素的 $a$ 和 $p$，有 $a^{\varphi(p)}\equiv 1\pmod{p}$。
欧拉定理推论：若 $a$ 和 $p$ 互素，则有 $a^b\equiv a^{b \operatorname{mod} \varphi(p)} \pmod{p}$。
费马小定理：若 $p$ 为素数且 $a$ 和 $p$ 互素，则有 $a^{p-1}\equiv 1\pmod{p}$。
费马小定理求逆元：若 $p$ 为质数，由 $a^{p-1}\equiv 1\pmod{p}$，故 $a \times a^{p-2}\equiv 1 \pmod{p}$，故 $a^{p-2}$ 即为 $a\pmod{p}$ 意义下的逆元，显然可以快速幂解决。
同余方程组与扩展中国剩余定理
求解 $x$，满足方程组 $x ≡ a_i \pmod {m_i}$，这就是同余方程组。
利用 $x=y_1m_1+a_1=y_2m_2+a_2$，结合扩展欧几里得算法可以完成同余方程组的合并，建议读者自己推导一遍式子。
int msc(int a,int b,int mod){//慢速乘，用于防止乘法溢出
if(a<0&&b<0) a=-a,b=-b;
else if(b<0) swap(a,b);
int ret=0;
while(b){
if(b&1) ret=(ret+a)%mod;
a=(a+a)%mod;b>>=1;
}
return ret;
}
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
int exgcd(int a,int b,int &x,int &y){//注意：结果x,y可能是负数,但是输入的a,b需要均为正数！！！
if(b==0){x=1;y=0;return a;}
int GCD=exgcd(b,a%b,x,y);
int tmp;tmp=x;
x=y;y=tmp-a/b*y;
return GCD;
}
void merge_equation(int &A,int &B,int a,int b){
int y1,y2;
int d=exgcd(B,b,y1,y2);
if((a-A)%d!=0){A=-1;return;}
y1=msc(y1,(a-A)/d,b/d);
int m=lcm(B,b);
A=((B*y1+A)%m+m)%m;
B=m;
}
pi excrt(int nn,int a[],int b[]){//x=a(mod b)
int A,B;
for(int i=1;i<=nn;i++){
if(i==1) A=a[i],B=b[i];
else merge_equation(A,B,a[i],b[i]);
if(A==-1) return mk(-1,-1);
}
return mk(A,B);
}
模板题：扩展中国剩余定理
例题：Biorhythms
中国剩余定理
求解 $x$，满足方程组 $x ≡ a_i \pmod {m_i}$，其中 $m_i$ 两两互质。
令 $M = m_1m_2 … m_n, M_i = M/m_i$。
显然 $(M_i, m_i) = 1$，所以 $M_i$ 关于模 $m_i$ 的逆元存在。把这个逆元设为 $t_i$。
于是有：$M_it_i ≡ 1\pmod {m_i}, M_it_i ≡ 0\pmod {m_j}(j \ne i)$。
进一步：$a_iM_it_i ≡ a_i \pmod {m_i},a_iM_it_i ≡ 0 \pmod {m_j}(j \ne i)$。
因此解为 $x ≡ a_1M_1t_1 + a_2M_2t_2 + ⋯ + a_nM_nt_n \pmod M$，且在 $\bmod M$ 意义下是唯一解。
扩展欧拉定理
$$
a^b\equiv\begin{cases}\quad a^b&b<\varphi(m)\newline a^{b\operatorname{mod}\varphi(m)+\varphi(m)}&b\geq\varphi(m)&\end{cases}(\mathrm{mod~}m)
$$
例题：Power Tower
在题目中，你可以通过修改快速幂的代码来帮助使用扩展欧拉定理，具体如下：
ll ksm(ll a,ll b,int p){
ll ret=1;
while(b){
if(b&1){ret=ret*a;if(ret>=p) ret=ret%p+p;}
a=a*a;if(a>=p) a=a%p+p;
b>>=1;
}
return ret;
}
该代码计算的是 $\begin{cases}a^b\mod p&a^b<p\newline a^b\mod p + p&a^b\geq p&\end{cases}$ 的值。
威尔逊定理
$p$ 是质数等价于 $(p-1)!\equiv-1\pmod p$。即两者互为充要条件。
排列组合与容斥原理
约定符号
- 下降幂：$n^{\underline{r}}=n\cdot(n-1)\cdot(n-2)\cdot…\cdot(n-r+1)$
- 上升幂：$n^{\bar{r}}=n\cdot(n+1)\cdot(n+2)\cdot…\cdot(n+r-1)$
- 阶乘：$n!=n\cdot(n-1)\cdot…\cdot1,\quad0!=1$
注：$n^{\underline{r}}=(n-r+1)^{\bar{r}}$
加法和乘法原理
加法原理：做某件事情有几种选择，每种选择的方案数之和就是做这件事情的方案数。
乘法原理：做某件事情分为几步，每步的方案数是独立的，则它们的积就是做这件事情的方案数。
排列与组合
排列数：$P^m_n/A^m_n=\frac{n!}{m!}$
组合数：$C^m_n/\dbinom{n}{m}=\frac{n!}{(n-r)!r!}$
容斥原理
基础形式
设 $S$ 是一个有限集，$A_1, A_2,\dots , A_n$ 是 $S$ 的 $n$ 个子集，则
$$
|S-\bigcup_{i=1}^nA_i|=\sum_{i=0}^n(-1)^i\sum_{1\leq j_1<j_2<…<j_i\leq n}|\bigcap_{k=1}^iA_{j_k}|
$$
符号形式
设 $S$ 是一个有限集，$a_1,a_2,\dots ,a_n$ 是 $n$ 种性质。
- 记 $N(a_i)$ 为 $S$ 中有 $a_i$ 性质的元素的数量。特殊的，记 $N(1)=|S|$。
- 记 $N(1-a_i)$ 为 $S$ 中没有 $a_i$ 性质的元素的数量。
- $N(a_{i_1}a_{i_2}…a_{i_k})$ 为 S 中同时有 $a_{i_1},a_{i_2},…,a_{i_k}$ 性质的元素的数量。
- 记 $N(a\pm b)=N(a)\pm N(b)$。
则容斥原理可以写成
$$
N((1-a_1)(1-a_2)…(1-a_n))=\sum_{i=0}^n(-1)^i\sum_{1\leq j_1<j_2<…<j_i\leq n}N(a_{j_1}a_{j_2}…a_{j_i})
$$
如果需要有其中一些性质，而不需要其他的性质，可以写作
$$
N(a_1…a_x(1-a_{x+1})…(1-a_{x+n}))=\sum_{i=0}^n(-1)^i\sum_{x+1\leq j_1<j_2<…<j_i\leq x+n}N(a_1…a_xa_{j_1}….a_{j_i})
$$
例题：大水题
第二类斯特林数
有 $n$ 个互不相同的球，放到 $k$ 个互不区分的盒子里，每个盒子里至少要有一个球，求方案数。
- 记号 $S_2(n,k)$,$n \brace m$
- 递推式 ${{n} \brace {k}}={n-1\brace k-1}+k{n-1 \brace k}$
- 容斥${n \brace k}=\frac{1}{k!}\sum_{i=0}^{k}(-1)^{i}\binom{k}{i}(k-i)^{n} $
- 重要的公式 $n^m=\sum_{k=0}^m {m \brace k}n^{\underline{k}}$
积性函数
定义与求法
积性函数如果函数 $f:\mathbb{N}\to\mathbb{R}$ ,满足对于任意一对互质的正整数 $p,q$, 都有 $f(pq)=f(p)f(q)$, 则称 $f$ 为积性函数。
使用质因数分解求解单个 $f(n)$
int calc_f(int x,int y){//计算 f(x^y)
//return y+1;
}
ll get_f(ll nn) {
ll ans=1;
for (int i=2; i*i<=nn;i++){
int cnt=0;
while (nn%i==0) cnt++,nn/=i;
if(cnt!=0) ans*=calc_f(i,cnt);
}
if (nn>1) ans*=f(nn,1);
return ans;
}
使用欧拉筛求解多个 $f(n)$
int f[N];
bool not_prime[N];
int tot;
int pri[N],cnt[N];//cnt 表示最小的质因子的次数
int calc_f(int x,int y){//计算 f(x^y)
//return y+1;
}
void Euler_Sieve(int nn){
f[1]=1;//根据情况定初始值
for(int i=2;i<=nn;i++){
if(!not_prime[i]) pri[++tot]=i,f[i]=calc_f(i,1),cnt[i]=1;
for(int j=1;j<=tot&&i*pri[j]<=nn;j++){
not_prime[pri[j]*i]=1;
if(i%pri[j]==0){
cnt[i*pri[j]]=cnt[i]+1;
f[i*pri[j]]=f[i]/calc_f(pri[j],cnt[i])*calc_f(pri[j],cnt[i]+1);
break;
}
cnt[i*pri[j]]=1;
f[i*pri[j]]=f[i]*calc_f(pri[j],1);
}
}
}
模板题：【线性筛求积性函数】
例题：华华给月月出题
莫比乌斯反演
前置定义：$\mu(n)$
$\mu(n)=\begin{cases}(-1)^k,&\text{if }n\text{无平方因子且有}k\text{个质因子}\newline 0,&\text{if }n\text{有平方因子}\end{cases}$
定理 (莫比乌斯反演)
设 $f:\mathbb{N}\to\mathbb{R},g:\mathbb{N}\to\mathbb{R}$ 是两个函数，则
$$
f(n)=\sum_{d\mid n}g(d)\Leftrightarrow g(n)=\sum_{d\mid n}\mu(\frac nd)f(d)
$$
To be continued…