数论题目
Mini_PEKKA
·
·
个人记录
欧拉函数
设 n 的质因数分解为 \prod\limits_{i=1}^{k}p_i^{k_i}。
计算式：\varphi(n)=n\prod\limits_{i=1}^{k}\frac{p_i-1}{p_i}。
性质：n=\sum\limits_{d|n}{\varphi(d)}。
推论：\gcd(x,y)=\sum\limits_{d}[d|x][d|y]\varphi(d)。
例题：P2350
Wilson 定理
## exgcd
已解出 $ax+by=\gcd(b,a\bmod b)$ 的一组特解 $x_1,y_1$。
要解出 $ax+by=\gcd(a,b)$ 的一组特解 $x_2,y_2$。
可令 $x_2=y_1,y_2=x_1-\lfloor\frac{a}{b}\rfloor y_1$。
C++ `a/b` 默认向 $0$ 取整，所以 $a,b$ 中有负数时可能出错。可以手写下取整函数避免此问题。
```cpp
ll floor(ll a, ll b) {
assert(b);
if (b < 0) {
a = -a;
b = -b;
}
return (a > 0 ? a : a - b + 1) / b;
}
```
例题：[LOJ2160](https://loj.ac/p/2160)
## CRT
类似拉格朗日插值。
## EXCRT
合并两个同余方程 $x\equiv a_1\pmod{m_1}$ 和 $x\equiv a_2\pmod{m_2}$。
令 $x=a_1+pm_1=a_2+qm_2$。
则 $pm_1-qm_2=a_2-a_1$，用 $\text{exgcd}$ 求出 $p$ 的一个特解 $p^\prime$。
其通解为 $p=p^\prime+k\cdot\frac{m_2}{\gcd(m_1,m_2)}$。
则 $x$ 可以表示为 $a_1+(p^\prime+k\cdot\frac{m_2}{\gcd(m_1,m_2)})m_1$。
即 $x\equiv{a_1+p^\prime m_1}\pmod{\text{lcm}(m_1,m_2)}$。
例题：[P4774](https://www.luogu.com.cn/problem/P4774)
## Lucas 定理
当 $p$ 为质数时：
$$\binom{n}{m}\equiv\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\binom{n\bmod p}{m\bmod p}\pmod p$$
## BSGS
> 给定 $a,b,p$ 满足 $\gcd(a,p)=1$，求最小的非负整数 $n$，满足 $a^n\equiv b\pmod p$。
设置块长 $B=\lceil\sqrt p\rceil$。
令 $n=iB-j$，因为 $\gcd(a,p)=1$，所以如果 ${(a^B)}^i\equiv b\cdot a^j\pmod p$ 则 $a^{iB-j}\equiv b\pmod p$。
从小到大枚举 $j$ 将 $(b\cdot a_j\bmod p,j)$ 加入哈希表。
从小到大枚举 $i$，如果 ${(a^B)}^i$ 在哈希表中则结束。
## Miller-Rabin
+ 使用 $2,7,61$ 作为底数可对 $2^{32}$ 以内的数判素。
+ 使用前 $12$ 个素数作为底数可对 $2^{78}$ 以内的素数判素。
例题：[ARC191C](https://www.luogu.com.cn/problem/AT_arc191_c)
## Dirichlet 卷积
对于两个数论函数 $f(n)$ 和 $g(n)$，它们的狄利克雷卷积得到的结果 $(f*g)(n)$ 定义为：
$$(f*g)(n)=\sum_{d|n}{f(d)g\left(\frac{n}{d} \right)}=\sum_{a\cdot b=n}{f(a)g(b)}$$
三个规律：
+ 交换律：$f*g=g*f
- 结合律：(f*g)*h=f*(g*h)
- 分配律：(f+g)*h=f*h+g*h
三个常用函数：
- 元函数：\epsilon(n)=[n=1]
- 常数函数：1(n)=1
- 恒等函数：id(n)=n
四个常用关系：
-
\mu*1=\epsilon
-
\varphi*1=id
-
\mu*id=\varphi
-
f*\epsilon=f
Dirichlet 前缀和
类似高维前缀和加完全背包。
例题：U540632
数论分块
左端点为 $l$ 的块右端点为 $\lfloor\frac{n}{\lfloor n/l\rfloor}\rfloor$。
例题：[P2260](https://www.luogu.com.cn/problem/P2260)
## 莫比乌斯函数
含有平方因子即存在一个质因数次数 $>1$。
性质：
+ $\sum\limits_{d|n}\mu(d)=[n=1]$。可以理解为给 $n$ 的每一个因子分配一个容斥系数，使得所有因子的容斥系数和为 $0$。
+ $\sum\limits_{d|n}\mu(d)\frac{n}{d}=\varphi(n)$。
例题：[CF2039F1](https://www.luogu.com.cn/problem/CF2039F1)
### 莫比乌斯反演
主要利用 $\sum\limits_{d}[d|x][d|y]\mu(d)=[\gcd(x,y)=1]$。
例题：[P1829](https://www.luogu.com.cn/problem/P1829)