【学习笔记】基础数论
2huk
·
2023-07-20 15:36:34
·
算法·理论
【学习笔记】基础数论
欧拉函数 \varphi(x)
https://oi-wiki.org/math/number-theory/euler/
欧拉函数是一个积性函数，但不是完全积性函数。
- 积性函数：$f(1) = 1$，且当 $\gcd(x, y) = 1$ 时，$f(xy) = f(x)f(y)$。
- 完全积性函数：$f(1) = 1$，且 $\forall x, y ,f(xy) = f(x)f(y)$。
## 性质
- $\varphi(n) = n \times \prod\limits_{p \mid n, p\ is\ a\ prime} \dfrac {p-1}p
\varphi(p^k) = p^k - p^{k-1}
\sum\limits_{\gcd(i, n) = 1} i = \dfrac{\varphi(n) \times n}2
欧拉定理
若 \gcd(k, n) = 1 ，则有 k^{\varphi(n)} \equiv 1 \pmod n
证明
设序列 a 为 1 \sim n 中与 n 互质的数，为 \{a_1,a_2,a_3,\dots,a_{\varphi(n)}\} ，显然有以下两条性质：
现在找到一个数 k ，满足 \gcd(k, n) = 1 ，也就是 k 与 n 互质，并重新定义一个序列 b = \{ka_1, ka_2, ka_3,\dots,ka_{\varphi(n)}\} ，那么现在证明仍然满足上面的性质：
若将所有的 b_i 对 n 取模，也就是 b_i' = ka_i \bmod n ，那么根据上面的证明，可知 b' 中的元素互不相同。而且由于有过取模，所以 b_i' 一定是在 [0, n) 的范围内的，所以 b_i' 与 n 互质。像这样大小为 \varphi(n) ，各不相同，且与 n 都互质的数构成的序列有且仅有一个，所以 b' = a 。
所以可以得到：
\prod\limits_{i=1}^{\varphi(n)}a_i = \prod\limits_{i=1}^{\varphi(n)}b_i' = \prod\limits_{i=1}^{\varphi(n)} (ka_i \bmod n) = \left( \prod\limits_{i=1}^{\varphi(n)} a_i \right) \times k^{\varphi(n)} \bmod n
等式两边同时 \div \prod\limits_{i=1}^{\varphi(n)}a_i ，则有：
k^{\varphi(n)} \equiv 1 \pmod n
应用
求逆元：\dfrac 1k \equiv k^{\varphi(p)-1} \pmod p 。
降低指数：k^a \equiv k^{a \bmod \varphi(p)} \pmod p 。
扩展欧拉定理：p 可以不是质数，k 可以不与 p 互质。
k^a \equiv \left\{\begin{matrix}
k^a & a < \varphi(p)\\
k^{a \bmod \varphi(p) + \varphi(p)} & a \ge \varphi(p)
\end{matrix}\right. \pmod p
求解
\Theta(\sqrt n)$ 求一个 $\varphi(n)$：$\varphi(n) = n \times \prod\limits_{p \mid n, p\ is\ a\ prime} \dfrac {p-1}p
- 若 $i$ 是质数，显然 $1 \sim i-1$ 都与 $i$ 互质，故 $\varphi(i) = i - 1$；
- 枚举 $j$，找到 $p_j \times i$，分两种情况求解 $\varphi(p_j \times i)$：
- 若 $i \bmod p_j = 0$，也就是 $p_j$ 是 $i$ 的最小质因子。那么也就是说在原来的 $i$ 中就已经有了一个质因子 $p_j$，所以 $i$ 和 $i \times p_j$ 的质因子是相同的。假设 $i$ 的所有质因子是 $q_k$，那么 $i \times p_j$ 的质因子也是 $q_k$，所以有 $\varphi(p_j \times i) = p_j \times i \times \prod\limits_{q \mid i, q\ is\ a\ prime}\dfrac{q-1}q$。其中后面的 $\prod\limits_{q \mid i, q\ is\ a\ prime}\dfrac{q-1}q$ 就是 $\varphi(i)$ 的值，所以 $\varphi(p_j \times i) = p_j \times \varphi(i)$；
- 若 $i \bmod p_j \ne 0$，也就是 $p_j$ 不是 $i$ 的最小质因子。那么根据积性函数的定义，显然有 $\varphi(p_j \times i) = \varphi(p_j) \times \varphi(i)$，也就是 $\varphi(p_j \times i) = (p_j - 1) \times \varphi(i)$。
```cpp
int p[N]; // p[i] 表示第 i 个质数
bool st[N]; // st[i] 表示 i 是否是质数
int phi[N];
void prime(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) p[ ++ cnt] = i, phi[i] = i - 1;
for (int j = 1; p[j] <= n / i; j ++ )
{
st[p[j] * i] = 1;
if (i % p[j]) phi[i * p[j]] = phi[i] * p[j];
else
{
phi[i * p[j]] = phi[i] * (p[j] - 1);
break;
}
}
}
}
```
---
# 除数函数 $\sigma_k(x)
$k = 0$ 时，含义为 $n$ 的约数个数和。
$k = 1$ 时，含义为 $n$ 的约数和。
除数函数全部是积性函数，但不是完全积性函数。
## $\sigma_0$ 求解
$\Theta(\sqrt n)$ 求一个 $\sigma_0(n)$：若 $n = \prod\limits_{i=1}^mp_i^{c_i}$，那么根据乘法原理，有 $\sigma_0(n) = \prod\limits_{i=1}^m(c_i+1)$。
$\Theta(n)$ 求 $\sigma_0(1) \sim \sigma_0(n)$：线性筛法：
在线性筛约数个数时还需要额外记录一个 $num_i$ 数组，表示 $i$ 的最小质因子的出现次数。
- 若 $i$ 是质数，那么根据质数的定义，$i$ 只有两个约数 $1$ 和 $i$，故 $\sigma_0(i) = 2$，而且显然 $num_i = 1$；
- 枚举 $j$，找到 $p_j \times i$，分两种情况求解 $\sigma_0(p_j \times i)$：
- 若 $i \bmod p_j = 0$，也就是 $p_j$ 是 $i$ 的最小质因子。那么 $i$ 原来有 $p_j$ 这个约数，并且是最小的约数，现在的 $p_j \times i$ 相比 $i$ 又多了一个 $p_j$，也就是原来的 $\times (p_j + 1)$ 变成了 $\times (p_j + 1 + 1)$，也就是 $\times (p_j + 2)$。所以求 $\sigma_0(p_j \times i)$ 时就需要先把原来 $(p_j + 1)$ 的贡献移除，在重新加上 $(p_j + 2)$ 的贡献，也就是 $\sigma_0(p_j \times i) = \sigma_0(i) \times \dfrac{p_j+2}{p_j-1}$；
- 若 $i \bmod p_j \ne 0$，也就是 $p_j$ 不是 $i$ 的最小质因子。那么也就是说原来的 $i$ 中没有 $p_j$ 这个约数，所以把 $p_j \times i$ 分解质因数后应该有一项是 $p_j^1$，剩下的是原来 $i$ 分解质因数的结果。根据约数个数的公式，将所有的指数加 $1$ 后连乘，那么就应该在原来 $\sigma_0(i)$ 的基础上 $\times (1+1)$，所以 $\sigma_0(p_j \times i) = 2 \times \sigma_0(i)$。
```cpp
int p[N]; // p[i] 表示第 i 个质数
bool st[N]; // st[i] 表示 i 是否是质数
int d[N]; // d[i] 表示 σ0(i) 的值
int num[N]; // num[i] 表示 i 的最小质因子出现次数
void prime(int n)
{
d[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) p[ ++ cnt] = i, d[i] = 2, num[i] = 1;
for (int j = 1; p[j] <= n / i; j ++ )
{
st[p[j] * i] = 1;
if (i % p[j]) num[i * p[j]] = 1, d[i * p[j]] = d[i] * 2; // p[j] 不是 i 的最小质因子
else // p[j] 是 i 的最小质因子
{
num[i * p[j]] = num[i] + 1, d[i * p[j]] = d[i] / （num[i * p[j]] + 1) * (num[i * p[j]] + 2);
break;
}
}
}
}
```
---
# 莫比乌斯函数 $\mu(x)
https://oi-wiki.org/math/number-theory/mobius/
\mu(n) = \left\{\begin{matrix}1 & n = 1\\ 0 & n 含有平方因子\\ (-1)^{本质不同质因子个数} & \mathrm{otherwise} \end{matrix}\right.
性质：\sum\limits_{d \mid n}\mu(d) = \left\{\begin{matrix} 1 & n=1\\ 0 & n \ne 1\end{matrix}\right.
莫比乌斯函数是积性函数，但不是完全积性函数。
求解
$\Theta(n)$ 求 $\mu(1) \sim \mu(n)$：线性筛法：
- 若 $i$ 是质数，那么 $i$ 就只有一个质因子 $i$，所以 $\mu(i) = (-1)^1 = -1$；
- 枚举 $j$，找到 $p_j \times i$，分两种情况求解 $\mu(p_j \times i)$：
- 若 $i \bmod p_j = 0$，也就是 $p_j$ 是 $i$ 的最小质因子。设 $q = \dfrac{p_j}i$，那么显然有 $p_j \times i = q \times i^2$，所以 $p_j \times i$ 就有了一个平方因子，所以 $\mu(p_j \times i) = 0$；
- 若 $i \bmod p_j \ne 0$，也就是 $p_j$ 不是 $i$ 的最小质因子。那么 $p_j \times i$ 就比 $i$ 多了一个新的质因子 $p_j$，故它的本质不同的质因子个数就多了 $1$，所以 $\mu(p_j \times i) = -\mu(i)$。
```cpp
void prime(int n)
{
mu[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) p[ ++ cnt] = i, mu[i] = -1;
for (int j = 1; p[j] <= n / i; j ++ )
{
st[p[j] * i] = 1;
if (i % p[j]) mu[p[j] * i] = -mu[i]; // p[j] 不是 i 的最小质因子
else // p[j] 是 i 的最小质因子
{
mu[i * p[j]] = 0;
break;
}
}
}
}
```
---
# 欧几里得算法
[https://oi-wiki.org/math/number-theory/gcd/#%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95](https://oi-wiki.org/math/number-theory/gcd/#%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95)
求 $\gcd(a, b)$，辗转相除法。
$\because\gcd(a, b) = \gcd(b, a \bmod b)
\therefore\gcd(b, a \bmod b) = \gcd(a \bmod b, b \bmod (a \bmod b))
\gcd(a \bmod b, b \bmod (a \bmod b)) = \gcd(b \bmod (a \bmod b), (a \bmod b) \bmod (b \bmod (a \bmod b)))
\vdots
\gcd(a, 0) = a
回溯得到答案。
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}扩展欧几里得算法
https://oi-wiki.org/math/number-theory/gcd/#%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
求二元一次方程 ax + by = c 的解。
裴蜀定理
裴蜀定理：有解当且仅当 \gcd(a, b) \mid c 。
证明：
有解当且仅当 \gcd(a, b) \mid c ：
设 d = \gcd(a, b),a = k_1d,b = k_2d ，则 ax+by = k_1dx+k_2dy = (k_1x + k_2y)\times d 。这个数一定是 d 的倍数。证毕。
设 $d = \gcd(a, b)$， $m$ 是 $ax + by$ 的最小整数解，即 $ax + by = m$。接下来从两个方面证明 $d = m$。
1. $m \ge d$：与上面类似。设 $a = k_1d,b = k_2d$，则 $ax+by = k_1dx+k_2dy = (k_1x + k_2y)\times d = m \ge d$。
2. $m \le d$：因为 $d \mid a$ 且 $d \mid b$，尝试证明 $m \mid a$ 且 $m \mid b$。由于 $d$ 是最大公约数，所以 $m \le d$。
反证法：设 $m \nmid a$，则 $a = km + r, r \in [1, m)$，则 $r = a - km$。因为 $m = ax + by$，则 $r = a - kax - kby$，即 $r = a(1 - kx) + b(-ky)$，即得到一组新的解，使得 $ax + by = r$，于 $m$ 是最小正整数结果矛盾，故 $m \mid a$，同理 $m \mid b$。
证毕。
求解
把这个方程中的 a,b 带入 \gcd(a, b) 欧几里得算法中。
a_1x_1 + b_1y_1 = c
a_2x_2 + b_2y_2 = c
其中 a_2 = b_1,\ b_2 = a_1 \bmod b_1 = a_1 - \left \lfloor \dfrac {a_1}{b_1} \right \rfloor \times b_1 。
这样第二个式子 就变成了 b_1x_2 + \left(a_1 - \left \lfloor \dfrac {a_1}{b_1} \right \rfloor \times b_1 \right) \times y_2 。
整理式子：
b_1x_2 + a_1y_2 - \left \lfloor \dfrac {a_1}{b_1} \right \rfloor \times b_1y_2
a_1y_2 + b_1 \times \left( x_2 - \left \lfloor \dfrac{a_1}{b_1}\right \rfloor \times y_2\right)
至此，这个式子与最开始 a_2x_2 + b_2y_2 = c 变得很像，也就是说如果需要从第二个式子变到第一个式子需要 x_1 \leftarrow y_2,y_1 \leftarrow \left( x_2 - \left \lfloor \dfrac{a_1}{b_1}\right \rfloor \times y_2\right) 。
这是第二层转换到第一层的过程，在这之前如果要求第二个式子需要往下的第三个式子进行推导，那么就需要写递归函数求解了。
当某个 y_m = 0 时，\gcd 函数行该返回 x_m ，此时 x_m = 1, y_m = \text{任意数} ，这里 y_m = 0 ，返回函数即可。
代码：
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 X = x;
x = y, y = X - a / b * y;
return d;
}或：
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;
}如果 (x, y) 是一组解，那么 \left(x + \dfrac bg, y - \dfrac ag \right) 也是一组解，其中 g \ne 0 。
求逆元
求 x ，使得 xk \equiv 1\pmod p 。
也就是求 x \times k + y \times p = 1 。
于是就转化成了二元一次方程，求的是 x 在 [0, p - 1] 区间内的一个解。
这个方法对 p 的素性没有要求。
int inv(int a, int b)
{
int x, y, d = exgcd(a, b, x, y);
if (d == 1) return (x % b + b) % b;
else return -1;
}筛质数
https://oi-wiki.org/math/number-theory/sieve/
埃氏筛：\Theta(n\times \ln(n)) 。
从小到大枚举每一个数字，如果之前被筛掉了，那么不是质数，否则就是质数。
无论当前的 i 是不是质数，枚举已经筛出来的每一个质数 pm_j ，把 i \times pm_j 筛掉，直到 i \times pm_j 大于上街 n 或者质数枚举完毕结束。
这个筛法从来不用。
对于每一个数字 x ，仅在 pm_{j'}\times i' 的时候被筛掉，其中 pm_{j'} 是 x 的最小质因数。
在枚举 pm 的时候，加一句判断，如果 pm_j \mid i ，那说明 i 的最小质因子为 pm_j ，之后再枚举 pm 就不满足要求了，直接 break。
int p[N];
bool st[N];
void prime(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) p[ ++ cnt] = i;
for (int j = 1; p[j] <= n / i; j ++ )
{
st[p[j] * i] = 1;
if (i % p[j] == 0) break;
}
}
}扩展
线筛除了可以筛质数，还可以筛一类满足条件的函数。
设 pm_{j'} 为 x 的最小质因子，pm_{j'}\times i' = x 。
那么已知 f(pm_{j'}) 和 f(i') 可 \Theta(1) 或 \Theta(\log n) 求出 f 值。
中国剩余定理 CRT
https://oi-wiki.org/math/number-theory/crt/
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
给定 a_i, p_i ，其中 p_i 两两互质，求 x ，满足：
\left\{\begin{matrix}x \equiv a_1 \pmod {p_1}
\\x \equiv a_2 \pmod {p_2}
\\\dots \dots \dots \dots
\\x \equiv a_n \pmod {p_n}
\end{matrix}\right.
定义一个 b 数组，b_i \equiv \left\{\begin{matrix} a_i & \pmod{p_i}\\ 0 & \pmod{p_{j \ne i}}\end{matrix}\right. 。
显然 x = \sum\limits_{i=1}^n b_i 。
我们可以这样得到一个 b_i ：\dfrac P {p_i} \times a_i \times \left( \dfrac P {p_i} \right) ^{p_i-2} ，其中 P = \prod\limits_{i=1}^n p_i 。
时间复杂度 $\Theta(n \log n)$。
```cpp
void exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
signed main()
{
cin >> n;
int M = 1;
for (int i = 0; i < n; i ++ )
{
cin >> A[i] >> B[i];
M *= A[i];
}
int res = 0;
for (int i = 0; i < n; i ++ )
{
int Mi = M / A[i], ti, x;
exgcd(Mi, A[i], ti, x);
res += B[i] * Mi * ti;
}
cout << (res % M + M) % M;
return 0;
}
```
## 扩展中国剩余定理 EXCRT
如果 $p_i$ 不两两互质，换一个角度分析问题。
求解 $x$ 实际上是合并方程。最终得到：
$$
x \equiv A\pmod P \Longleftrightarrow x = A + kP(k \in \mathbb{Z})
$$
如果能把两个式子 $x \equiv a_1 \pmod {p_1}$ 和 $x \equiv a_2 \pmod {p_2}$ 合并成 $x \equiv a_{12} \bmod p_{12}$，那么就可以用一般方法不断地合并两个方程，直到仅剩一个方程，得到答案。其中 $p_{12} = \mathrm{lcm}(p_1, p_2) \ne p_1p_2$，$a_{12}$ 是原方程组的任意一个特解。
如何求 $a_{12}$？
- $x \equiv a\pmod p \Longleftrightarrow x = a + kp(k \in \mathbb{Z})
\left\{\begin{matrix}x \equiv a_1 \pmod {p_1}\\x \equiv a_2 \pmod {p_2}\end{matrix}\right.\Longleftrightarrow\left\{\begin{matrix} x = a_1 + k_1p_1\\x = a_2 + k_2p_2\end{matrix}\right.
k_1p_1 - k_2p_2 = a_2 - a_1
根据裴蜀定理，上式有解当且仅当 \gcd(p_1, p_2) \mid a_2 - a_1 。
扩欧求出 k_1 特解，带入得到 x 特解记为 a_{12} 。
然后不断将方程两两合并即可找到 x 。
int exgcd(int a, int b, int &x, int &y) // 扩展欧几里得算法, 求x, y，使得ax + by = gcd(a, b)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
int a1, m1; // 现有方程
int a2, m2; // 读入的方程
int k1, k2; // 系数
int d; // 最大公约数
int t;
signed main()
{
cin >> n >> a1 >> m1;
for (int i = 0; i < n - 1; i ++ )
{
cin >> a2 >> m2;
d = exgcd(a1, a2, k1, k2);
if ((m2 - m1) % d) // 裴蜀定理，判断是否无解
{
puts("-1");
return 0;
}
k1 *= (m2 - m1) / d; // 把 k1a1 - k2a2 = m2 - m1 翻成 k1a1 - k2a2 = d
t = a2 / d;
k1 = (k1 % t + t) % t;
m1 = a1 * k1 + m1;
a1 = abs(a1 / d * a2);
}
cout << (m1 % a1 + a1) % a1;
return 0;
}