有些比较浅显易懂的就偷懒没写了。
数论-质数
欧拉筛
线性筛
数论-因数倍数（upd：25/1/20）
\(a,b\) 最大公因数记为 \(\gcd(a,b)\)，无歧义时可记为 \((a,b)\)。
\(a,b\) 最小公倍数记为 \(\text{lcm}(a,b)\)，无歧义时可记为 \([a,b]\)。
\(a\) 是 \(b\) 的倍数 \(=\) \(b\) 是 \(a\) 的因数 \(=\) \(b\) 能整除 \(a\) \(=\) \(a\) 能够被 \(b\) 整除 \(=\) \(b|a\)
\(\gcd\)
以下来自 AI 聚合：
-
交换律：\(\gcd(a, b) = \gcd(b, a)\)
-
负数性质：\(\gcd(−a, b) = \gcd(a, b)\)
-
自身性质：\(\gcd(a, a) = |a|\)
-
零性质：\(\gcd(a, 0) = |a|\)
-
模运算性质：\(\gcd(a, b) = \gcd(b, a \mod b)\)（辗转相除法）
-
减法性质：\(\gcd(a, b) = \gcd(b, a − b)\)（辗转相减法）
-
分配律：如果有一个自然数 m，则 \(\gcd(ma, mb) = m ∗ \gcd(a, b)\)
-
线性组合性质：\(m \in \mathbb{Z}\) 则 \(\gcd(a + mb, b) = \gcd(a, b)\)（可用减法性质证明）。
-
乘法性质：\(\gcd(ab, m) = \gcd(a, m) ∗ \gcd(b, m)\)
-
\(\gcd\) 与 \(\text{lcm}\) 关系：\(\forall a,b \in \mathbb{N},\gcd(a,b)\text{lcm}(a,b)=ab\)
往数集中加入一个数，要么 \(\gcd\) 不变，要么最多变为原来的 \(\frac{1}{2}\)。
数论-同余方程
裴蜀定理
对于任意自然数 \(a,b\)，存在整数 \(x,y\) 满足 \(ax+by=\gcd(a,b)\)。
线性同余方程
形如 \(ax \equiv b \pmod m\)，转化为求 \(ax+my=b\) 的解。
若 \(gcd(a,m) \nmid b\) 则无解。
否则利用 exgcd 求得一组 \(ax+my=\gcd(a,m)\) 的特解 \(x_0,y_0\)。
方程的通解为：
\[\left\{ \begin{aligned} x=x_0+\frac{km}{\gcd(a,m)}\\ y=y_0-\frac{ka}{\gcd(a,m)} \end{aligned} \right. \]exgcd/拓展欧几里得算法
貌似这种写法比较多。
int exgcd(int a,int b,int &x,int &y){
if(!b){x=1,y=0;return a;}
int d=exgcd(b,a%b,x,y);
int tmp=x;
x=y;y=tmp-a/b*y;
return d;
}
将递\(x,y\) 交换也可以这样写，注意区别：
int exgcd(int a,int b,int &x,int &y){
if(!b){x=1,y=0;return a;}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
CRT
NOIP 应该没有这么裸的题吧，EXCRT 什么的就不学了。
对于
\[\left\{ \begin{aligned} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \text{...} \\ x \equiv a_n \pmod {m_n} \end{aligned} \right. \]设 \(MOD=\prod_{i=1}^n m_i,M_i= \frac{MOD}{m_i}\)。
令 \(t_i\) 表示 \(M_i\) 在模 \(m_i\) 意义下的逆元。
则\(ans=(\sum_{i=1}^n a_i M_i t_i)\mod MOD\)。
BSGS 求解高次同余方程
数论-卷积
OI 中常见的卷积：
- 加法卷积：\(t(n)=\sum_{i=0}^n f(i)g(n-i)\)。
- 乘法卷积（狄利克雷卷积）：\(t(n)=\sum_{i|n} f(i)g(\frac{n}{i})\)。
- 异或卷积与 FWT（还不会）。
- \((\max,+)\) 卷积：\(g(n)=\max_{i=0}^n (f(i)+f(n-i))\)。
狄利克雷卷积
\[t(n)=\sum_{i|n} f(i)g(\frac{n}{i}) \]\(f\) 与 \(g\) 卷积记为 \(f \star g\)。
数论-数论函数（定义在正整数集上）
Preface
\(I(n)=1\)，常数函数；
\(\epsilon(n)=[n=1]\)，单位函数；
\(\text{id}(n)=n\)，恒等函数。
这三者看似无用，但它们之间的运算可以表达出常见的数论函数：
欧拉函数 \(\varphi(n)\)、约数个数函数 \(\sigma_0(n)\) ……
欧拉函数
\(\varphi(n)\) 表示 \(1\sim n\) 与 \(n\) 互质的数的个数。
若 \(n=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}\)，\(p\) 为两两不同的素数，则 \(\varphi(n)=(p_1-1)(p_2-1)\dots(p_k-1)\)。
-
\(\varphi(1)=1\)。
-
质数 \(p\) 的 \(\varphi(p)=p-1\)。
-
若 \(a,b\) 互质则 \(\varphi(ab)=\varphi(a)\varphi(b)\)（普通积性函数）。
欧拉函数可以在线性筛时 \(O(n)\) 求得。
欧拉定理
\[\forall a,n\in\mathbb{N}_+\gcd(a,n)=1,a^{\varphi(n)} \equiv 1 \pmod n \]欧拉定理的推论
\[\forall a,b,n \in \mathbb{N}_+ \gcd(a,n)=1,a^b \equiv a^{b \bmod \varphi(n)}\pmod n \]拓展欧拉定理
\[\forall b\geq \varphi(n),a^b \equiv a^{(b\bmod \varphi(n))+\varphi(n)} \]证明略复杂。
费马小定理
\[\forall p\in \text{prime},a^p \equiv a \pmod p \]欧拉定理的一个特例。
莫比乌斯函数
两数相乘为 \(1\) 是乘法逆元，类似地，两函数相卷得到幺元 \(ϵ\)，则两函数互为卷积逆元。Mobius 函数实际上就是一个构造出的 \(I\) 的逆元，记作 \(μ\)。
\(μ\) 是一个积性函数，定义式为：
\[\mu(n)=\begin{cases} 1&n=1\\ (-1)^k&n=p_1p_2\cdots p_k,~~~~p\text{ 为两两不同的素数}\\ 0&\text{otherwise} \end{cases} \]\(μ\) 函数是为了满足下式：
\[I⋆μ=ϵ \]即
\[\sum_{d|n}\mu(d)=[n=1] \]Mobius 反演
充分认识 \(μ\) 之后，反演公式其实非常浅显。对于两个数论函数 \(f,g\)，满足：
\(f=g\star I\Longleftrightarrow g=f\star\mu\)
例题
P2568 GCD P4450 P2522 P3455
References
- 王鑫（竞赛教练）初等数论.pdf
- https://www.cnblogs.com/rainybunny/p/14359098.html