线性筛 欧拉筛 常用数学函数

Login to join training plan

欧拉函数

$\varphi(x) = \sum\limits_{k = 1}^x[\gcd(k, x) = 1]$

$\varphi(x)$ 表示 $1 \sim x - 1$ 中与 $x$ 互质的数。

欧拉函数是一个积性函数，但不是完全积性函数。

• 积性函数：$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$

欧拉定理

对于一个模数 $p$，$p$ 可以不是质数，但 $k$ 与 $p$ 互质，有 $k^{\varphi(p)} \equiv 1 \pmod p$。

• 求逆元：$\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 \mod \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$

• $\Theta(n)$ 求 $\varphi(1) \sim \varphi(n)$：

线性筛法。

int p[N];
bool st[N];
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) = \sum\limits_{d \mid x} d^k$。

$k = 0$ 时，含义为约数个数和。

$k = 1$ 时，含义为约数和。

除数函数全部是积性函数，但不是完全积性函数。

---

莫比乌斯函数

https://oi-wiki.org//math/number-theory/mobius/

https://www.luogu.com.cn/problem/P3455

---

欧几里得算法

求 $\gcd(a, b)$，辗转相除法。

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

扩展欧几里得算法

求二元一次方程 $ax + by = c$ 的解。

裴蜀定理：有解当且仅当 $\gcd(a, b) \mid c$。

如果 $(x_1, y_1)$ 是一组解，那么 $(x_1 + \dfrac bg, y_1 - \dfrac ag)$ 也是一组解。

如何得到一组任意解？

$a_1x_1 + b_1y_1 = c$

$a_2x_2 + b_2y_2 = c$

$a_2 = b_1,\ a_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 \times y_2 \right)$

$b_1x_2 + a_1y_2 - a_1 - \left \lfloor \dfrac {a_1}{b_1} \right \rfloor \times b_1 \times y_2$

......

求逆元

求 $x$，使得 $x \times k \bmod p = 1$。

也就是求 $x \times k + y \times p = 1$。

于是就转化成了二元一次方程，求的是 $x$ 在 $[0, p - 1]$ 区间内的一个解。

这个方法对 $p$ 的素性没有要求。

筛质数

• 埃氏筛：$\Theta(n\times \ln(n))$。

从小到大枚举每一个数字，如果之前被筛掉了，那么不是质数，否则就是质数。

无论当前的 $i$ 是不是质数，枚举已经筛出来的每一个质数 $pm_j$，把 $i \times pm_j$ 筛掉，直到 $i \times pm_j$ 大于上街 $n$ 或者质数枚举完毕结束。

• 线性筛：$\Theta(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;
		}
	}
}

中国剩余定理

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

给定 $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 = \dfrac P {p_i} \times a_i \times \left( \dfrac P {p_i} \right) ^{p_i-2}$。

EXCRT

如果 $p_i$ 不两两互质，合并方程。最终得到：

$$x \equiv A \bmod 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}$ 是原方程组的任意一个特解。

使用扩展欧几里得算法求解特解。

如果两两互质，可以直接求逆元得到 $k_1$。