数学 | Ziuch の Blog

type

status

date

slug

summary

0 本节习题一览

质数习题1: 204. 计数质数

质数习题2: 1175. 质数排列

质因数分解习题: 172. 阶乘后的零

约数习题1: 1492. n 的第 k 个因子

约数习题2: 1362. 最接近的因数

快速幂习题1: 50. Pow(x, n)

快速幂习题2: 372. 超级次方

欧几里得习题: 1447. 最简分数

1 质数

💡

只能被1和它本身整除的大于1的自然数

1.1 判定 `O()`

💡

一个数x最大的因子(除自身外)会小于等于根号x

1.2 试除法分解质因数 `O()`

💡

合数因子会在小的质因子之前被分解

1.3 朴素筛法 `O(nloglogn)`

💡

合数会被其因子筛掉，但是同一个合数会被筛多次(因子个数不唯一)

1.4 线性筛法 `O(n)`

💡

每个合数只会被它的最小质因子筛一次

质数习题1: 204. 计数质数

质数习题2: 1175. 质数排列

质因数分解习题: 172. 阶乘后的零

2 约数

2.1 试除法求约数 `O(logn)`

💡

约数总是成对出现

约数习题1: 1492. n 的第 k 个因子

约数习题2: 1362. 最接近的因数

2.2 约数的和与积 `O(logn + n)`

如果 N = p1^c1 * p2^c2 * ... *pk^ck

💡

约数个数：(c1 + 1) * (c2 + 1) * ... * (ck + 1)

💡

约数之和：(p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

3 欧拉函数

💡

phi(i)定义为1~i中与i互质的个数

3.1 定义法求单个数的欧拉函数`O()`

💡

把质因子和其倍数去掉，剩下的就是答案

质因数分解

首先，将 n 分解为质因数的乘积，即：

其中，是 n 的不同质因数，是相应的指数。

通过容斥定理推导

设表示小于且是的倍数的集合。那么：

对于两个质因数和，它们的交集（即同时是和的倍数）是：

通过容斥定理，我们可以计算小于且是任意质因数的倍数的数的个数为：

这个表达式实际上是在逐步加减交集的部分，确保每个倍数的数只被计算一次。

最终公式推导

我们需要的不是这些倍数的数的个数，而是小于且与互质的数的个数。因此，我们从中减去这些倍数的数的个数即可。

3.2 素数筛法求1~n的欧拉函数`O(n)`

1. 当前数是质数

如果当前数 \(i\) 是质数，即 \(\text{is\_prime}[i]\) 为 \(\text{True}\)，则我们知道 \(i\) 没有比它更小的质因数。此时：

将 \(i\) 加入质数列表 \(\text{primes}\)：因为 \(i\) 是质数，所以将其加入质数列表，方便后续处理 \(i\) 的倍数。

将 \(\varphi[i]\) 更新为 \(i - 1\)：对于质数 \(i\) 来说，只有自身与 \(i\) 不互质，其余所有小于 \(i\) 的数都与 \(i\) 互质。因此，根据欧拉函数的定义，\(\varphi[i]\) 应更新为 \(i - 1\)。

2. 当前数是某个质数的倍数

对于每个质数 \(p\) 和当前数 \(i\) 的倍数 \(j = i \times p\)，我们根据 \(i\) 是否是 \(p\) 的倍数来决定如何更新 \(\varphi[j]\)：

情况1：如果 是 的倍数

如果是的倍数，即可以表示为，则：

因为此时 \(j = k \times p \times p\)，即 \(j\) 包含质因数 \(p\) 的次数多于一次。我们只需将 \(\varphi[i]\) 乘以 \(p\) 即可更新 \(\varphi[j]\) 的值。这是因为在这种情况下，\(i\) 的所有质因数都会在 \(j\) 中多出现一次，因此 \(\varphi[j]\) 是 \(\varphi[i]\) 乘以一个额外的 \(p\)。

情况2：如果 不是 的倍数

如果 \(i\) 不是 \(p\) 的倍数，即 \(i\) 和 \(p\) 互质，则：

因为此时 \(j\) 是两个互质数的乘积（即 \(i\) 和 \(p\) 互质），根据欧拉函数的乘法性质，可以将 \(\varphi[j]\) 更新为 \(\varphi[i] \times (p - 1)\)。这利用了欧拉函数的性质：对于互质的两个数 \(a\) 和 \(b\)，有。由于 \(\varphi(p) = p - 1\)，因此我们更新 \(\varphi[j]\) 为 \(\varphi[i] \times (p - 1)\)。

3.3 欧拉定理及费马小定理

欧拉定理（Euler's Theorem）

严格定义

设 \( a \) 和 \( n \) 是正整数，且 \( a \) 与 \( n \) 互质（即 \(\gcd(a, n) = 1\)）。则有：

其中，是欧拉函数，表示小于或等于 \( n \) 且与 \( n \) 互质的正整数的个数。

简单证明

定义集合：设 \(\mathbb{Z}_n^* = \{ x \mid 1 \le x \le n, \gcd(x, n) = 1 \}\)，其大小为 \(\phi(n)\)。

乘法群性质：集合 \(\mathbb{Z}n^*\) 在模 \(n\) 意义下构成一个乘法群，记其元素为 \(\{ x_1, x_2, \ldots, x{\phi(n)} \}\)。

乘法同余：对于任意 \( a \) 与 \( n \) 互质，有： \[ \{ ax_1, ax_2, \ldots, ax_{\phi(n)} \} \] 是 \(\mathbb{Z}_n^*\) 的一个排列。

等式变换：因此： \[ \prod_{i=1}^{\phi(n)} (ax_i) \equiv \prod_{i=1}^{\phi(n)} x_i \pmod{n} \] 即： \[ a^{\phi(n)} \prod_{i=1}^{\phi(n)} x_i \equiv \prod_{i=1}^{\phi(n)} x_i \pmod{n} \]

消去因子：因为 \(\prod_{i=1}^{\phi(n)} x_i\) 与 \(n\) 互质，可以消去这个因子，得到： \[ a^{\phi(n)} \equiv 1 \pmod{n} \]

费马小定理（Fermat's Little Theorem）

严格定义

如果 \( p \) 是一个质数，且 \( a \) 是一个不被 \( p \) 整除的整数（即 \(\gcd(a, p) = 1\)），则有：

简单证明

定义集合：设 \(\mathbb{Z}_p^* = \{1, 2, \ldots, p-1\}\)。

乘法同余：对于任意 \( a \) 与 \( p \) 互质，有： \[ \{ a \cdot 1, a \cdot 2, \ldots, a \cdot (p-1) \} \] 是 \(\mathbb{Z}_p^*\) 的一个排列。

等式变换：因此： \[ \prod_{i=1}^{p-1} (a \cdot i) \equiv \prod_{i=1}^{p-1} i \pmod{p} \] 即： \[ a^{p-1} \prod_{i=1}^{p-1} i \equiv \prod_{i=1}^{p-1} i \pmod{p} \]

消去因子：因为 \(\prod_{i=1}^{p-1} i = (p-1)!\) 与 \( p \) 互质（因为 \( p \) 是质数），可以消去这个因子，得到：

4 快速幂 `O(logn)`

💡

底数倍增，指数减半 eg:

💡

可拓展至矩阵的幂运算，求乘法逆元(a与p互质)

快速幂习题1: 50. Pow(x, n)

快速幂习题2: 372. 超级次方

5 欧几里得算法及其扩展

5.1 欧几里得算法(求最大公约数) `O(logn)`

💡

gcd(a, b) = gcd(b, a % b)

💡

a b的最大公倍数 = a * b / gcd(a, b)

欧几里得习题: 1447. 最简分数

5.2 拓展欧几里得求ax + by = gcd(a, b) `O(logn)`

💡

可求线性同余方程的解 eg: ax≡1(mod b)等价与ax+by=1

6 乘法逆元

求逆元主要涉及数论中的模逆运算。模逆元是满足以下条件的数：

即找到一个整数，使得在模意义下等于 1。

示例计算

假设，，：

首先计算的模逆元：因此，3 的模逆元是 4。

然后计算：

最终结果是 7。

6.1 使用扩展欧几里得算法求逆元

解释

extended_gcd 函数使用递归来实现扩展欧几里得算法，返回 gcd（最大公约数）以及满足贝祖等式的系数 \( x \) 和 \( y \)。

mod_inverse 函数调用 extended_gcd 来计算模逆元。如果 gcd 不等于 1，说明 \( a \) 和 \( m \) 不是互质的，因此逆元不存在。如果 gcd 等于 1，则返回 \( x \) 对 \( m \) 取模的结果作为逆元。

6.2 使用快速幂求逆元

根据 Fermat 小定理，对于一个素数 \( p \) 和任意整数 \( a \)，如果 \( a \) 和 \( p \) 互质，则：

\[ a^{p-1} \equiv 1 \ (\text{mod} \ p) \]

由此可得：

\[ a^{p-2} \equiv a^{-1} \ (\text{mod} \ p) \]

利用这个性质，可以用快速幂算法计算模逆元。

快速幂算法实现模逆元(p是质数)

下面是使用快速幂算法计算模逆元的 Python 代码：

代码解释

fast_exp 函数：实现快速幂算法，通过不断地将指数减半和基数平方，来高效地计算大整数幂取模。

mod_inverse 函数：利用 Fermat 小定理，通过计算 \( a^{p-2} \ (\text{mod} \ p) \) 来求得模逆元。

示例

对于 \( a = 3 \) 和 \( p = 11 \)：

\[ 3^{11-2} \ (\text{mod} \ 11) = 3^9 \ (\text{mod} \ 11) \]

运行上述代码将返回 4，因为：

\[ 3 \cdot 4 \equiv 1 \ (\text{mod} \ 11) \]

注意事项

该方法仅适用于模数 \( p \) 为素数的情况。如果 \( p \) 不是素数或 \( a \) 和 \( p \) 不是互质，则需要使用扩展欧几里得算法或其他方法。

6.3 使用pow求逆元

当然，可以通过求模逆元的方法来计算分数 \( \frac{a}{b} \mod p \)。这涉及到先求出 \( b \) 的模逆元，然后将其与 \( a \) 相乘并取模。

下面是具体的步骤和代码示例：

步骤

计算 \( b \) 的模逆元 \( b^{-1} \)。

计算 \( \frac{a}{b} \mod p \)，这等价于 \( a \cdot b^{-1} \mod p \)。

代码示例

假设我们使用快速幂算法来求模逆元，并计算 \( \frac{a}{b} \mod p \)。

解释

fast_exp 函数：实现快速幂算法，用于高效计算大整数幂取模。

mod_inverse 函数：利用快速幂算法计算模逆元。对于素数 \( p \)，计算 \( b^{p-2} \mod p \) 作为 \( b \) 的模逆元。

mod_divide 函数：先计算 \( b \) 的模逆元 \( b^{-1} \)，然后计算 \( a \cdot b^{-1} \mod p \)。

0 本节习题一览

1 质数

1.1 判定 O()

1.2 试除法分解质因数 O()

1.3 朴素筛法 O(nloglogn)

1.4 线性筛法 O(n)

2 约数

2.1 试除法求约数 O(logn)

2.2 约数的和与积 O(logn + n)

3 欧拉函数

3.1 定义法求单个数的欧拉函数O()