当前位置：首页 > news >正文

【算法】简单数论

news 来源：原创 2025/9/2 19:11:07

模运算

$a\ mod \ b = a - \lfloor a / b \rfloor \times b$
$\ mod\ p$ 得到的结果的正负至于被除数 $n$ 有关

模运算的性质：

$b)\ mod\ m = ((a\ mod\ m) + (b\ mod\ m))\ mod\ m$

$b)\ mod\ m = ((a\ mod\ m) - (b\ mod\ m))\ mod\ m$ = $((a\ mod\ m) - (b\ mod\ m) + m)\ mod\ m$

$\times b)\ mod\ m = ((a\ mod\ m) \times (b\ mod\ m))\ mod\ m$

但是除法例外，除法的取模需要用到逆元。

计算减法的时候，通常需要加上模数，防止出现负数。

乘法逆元

若 $\times x \equiv 1 \ (mod \ b)$ ，且 $a$ 与 $b$ 互质，我们定义 $x$ 为 $a$ 的逆元，记为 $a^{-1}$ , $x$ 可称为 $a$ 在模 $b$ 意义下的倒数

对于 $\frac{a}{b} \ mod \ p$ ，我们可以求出 $b$ 在 $\ p$ 意义下的逆元，然后乘上 $a$ ，再 $\ p$ 即可

注意对于数 $a$ 在模 $p$ 意义下的乘法逆元，我们需要确保 $a$ 与 $p$ 互质，此时才有 $a$ 的乘法逆元 $a^{-1}$ ，此条件等价于 $p$ 是质数

费马小定理

$a^{p - 1} \equiv 1 \ (mod \ p)$ ，其中 $p$ 是素数

费马小定理求逆元
$\times a^{p - 2} \equiv 1 \ (mod\ p)$ ，根据乘法逆元的定义可知，此时 $a^{-1} = a^{p - 2}$

扩展欧几里得求逆元

根据逆元的定义 $\equiv 1 \ (mod \ p)$ ，我们得到方程： $a x - 1 = y p$ （ $a x - 1$ 是 $p$ 的倍数），则 $a x + p y = 1$

解方程得 $\ mod \ p$ 得到的就是 $a$ 的乘法逆元，同时逆元存在的条件是 $g c d (a, p) = 1$

求阶乘的乘法逆元

同余

两个整数 $a$ 和 $b$ 对用一个正整数 $m$ 取模后余数相同，则称 $a$ 和 $b$ 对模 $m$ 同余，记作 $\equiv b \ (mod\ m)$ ，这意味着 $m\ | \ (a - b)$

同余的性质：

自反性： $\equiv a \ (mod\ m)$
对称性：若 $\equiv b \ (mod \ m)$ ，则 $\equiv a \ (mod \ m)$
传递性：若 $\equiv b \ (mod\ m), b \equiv c \ (mod\ m)$ ，则 $\equiv c \ (mod\ m)$
同加性：若 $\equiv b \ (mod\ m)$ ，则 $\pm c \equiv b \pm c \ (mod\ m)$
同乘性：若 $\equiv b \ (mod\ m)$ ，则 $\times c \equiv b \times c \ (mod\ m)$ ，若 $\equiv b \ (mod \ m), c \equiv d \ (mod \ m)$ ，则 $\times c \equiv b \times d \ (mod\ m)$
同幂性：若 $\equiv b \ (mod \ m)$ ，则 $a^c \equiv b^c \ (mod\ m)$
不满足同除性，但是有，若 $\equiv cb \ (mod \ m)$ ，则 $\equiv b \ (\ mod \ \frac{m}{gcd(m, c)})$

扩展欧几里得定理

对于给定的两个整数 $a$ ， $b$ ，必须存在整数 $x$ 与 $y$ ，使得 $\times x + b \times y = gcd(a, b)$

裴蜀定理

方程 $\times x + b \times y = c$ 有整数解的充分必要条件是 $c$ 是 $g c d (a, b)$ 的倍数

证明：

必要性：令 $p = g c d (a, b)$ ，则有 $\times a'$ ， $\times b'$ ；则 $\times (a'x + b'y)$ ，即 $g c d (a, b)$ 的倍数。
充分性：考虑 $g c d$ 的欧几里得算法。 $a, b$ 通过 $\% b$ 的方式一直辗转下去，最后会出现 $p, 0$ 的形式。原因是$0 \leq a % b \leq b - 1 $。对于递归出口$ p, 0 $，方程$ a \times p + 0 \times y = c $是否存在解呢？显然有解，由于充分性，这里$ a $取$ \frac{c}{p}$即可。那么辗转相除过程中，下面的成立能否推得上面的成立呢？
- 对于方程 $bx_1 + a \% b \times y_1 = c = ax + by$
- $bx_1 + (a - \lfloor \frac{a}{b} \rfloor \times b) \times y_1 = ay_1 + bx_1 - \lfloor \frac{a}{b} \rfloor \times by_1 = ay_1 + b \times (x_1 - \lfloor \frac{a}{b} \rfloor \times y_1) = 右边 = ax + by$
  
  所以找到一组特解： $x = y_1$ ， $x_1 - \lfloor \frac{a}{b} \rfloor \times y_1$ ，就可以通过最下面的特解推得所有的特解。
- 对于特解 $x_0, y_0)$ ，设下一组解是 $x_0 + d_1, y_0 + d_2)$
  
  有 $\times (x_0 + d_1) + b \times (y_0 + d_2) = c$ ，又， $\times x_0 + b \times y_0 = c$ ，则 $ad_1 + bd_2 = 0$
  
  故， $\frac{d_1}{d_2} = -\frac{b}{a} = -\frac{b / gcd(a, b)}{a / gcd(a, b)}$
  
  则 $d_1 = \frac{b}{gcd(a, b)}$ ， $d_2 = -\frac{a}{gcd(a, b)}$ ，故一般解为：
  
  $x_0 + k \times \frac{b}{gcd(a, b)}$ ， $y_0 - k \times \frac{a}{gcd(a, b)} \ (k \in Z)$
- 若要求 $x$ 的最小整数解，则可以通过 $(x_0 \ mod \ (\frac{b}{gcd(a, b)}) + \frac{b}{gcd(a, b)}) \ mod \ x_0$ ，原因是 $x_0$ 的周期是 $\frac{b}{gcd(a, b)}$ ，所以可通过取模的方式得到结果

扩展欧几里得算法

ex

GCD

最大公约数：欧几里得算法，时间复杂度 $O(log\ a)$

$a\ mod\ b)$

证明如下：

令 $p = g c d (a, b)$ ，则有 $\times a'$ ， $\times b'$ ， $g c d (a^{'}, b^{'}) = 1$
- $a\ mod\ b = a - \lfloor a / b \rfloor \times b = p \times a' - p \times b' \times \lfloor a / b \rfloor$
- 可以看出，$p \ | \ b $， $\ | \ (a \ mod \ b)$
那么 $p$ 是否是最大公约数呢？即我们需要证明 $\times \lfloor a / b \rfloor) = 1$
- 令 $\times \lfloor a / b \rfloor) = d$ ，则有 $\times b''$ ， $\times \lfloor a / b \rfloor = d \times c$
- 转换得到 $\times c + b' \times \lfloor a / b \rfloor = d \times c + d \times b'' \times \lfloor a / b \rfloor$
- 可以发现 $d\ |\ b'$ ， $d\ | \ a'$ ，与上述 $g c d (a^{'}, b^{'}) = 1$ 矛盾，则命题得证。

欧拉函数

$1... N$ 中与 $N$ 互质的数的个数，被称为欧拉函数，记作 $\phi(N)$

在唯一分解定理中， $p_1^{a_1} \times p_2^{a_2} \times ...\times p_m^{a_m}$ ，则 $\phi(N) = N \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times ... \times \frac{p_m - 1}{p_m}$

质数

分解质因数

给定一个数 $x$ ，由唯一分解定理可知， $p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3}...\ (p_1 < p_2 < p_3)$ ，我们从小到大枚举每一个数，最先整除 $x$ 的除数 $n$ 一定是素数。同时将这个数中所有 $n$ 的因子除干净，那么下次 $x$ 被整除时除数也是素数，从而分解了质因数。

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;for (int i = 0; i < n; i ++) {int x;cin >> x;map<int, int> cnt;vector<int> res;for (int j = 2; j <= x / j; j ++) {if (x % j != 0) continue;res.push_back(j);while (x % j == 0) {cnt[j] ++;x /= j;}}if (x > 1) {res.push_back(x);cnt[x] ++;}for (auto& u : res) {cout << u << " " << cnt[u] << endl;}cout << endl;}return 0;
}

普通筛法

给定一个整数 $x$ ，并筛掉所有倍数，如 $2 x, 3 x, 4 x ...$

筛完后， $v i s [i] = f a l se$ 的为素数

这种方法的时间复杂度是 $O(n\ log\ n)$ 级别

对于每一个外层循环变量 $i$ ，内层循环枚举所有不超过 $n$ 的 $i$ 的倍数，枚举次数是 $\lfloor \frac{n}{i} \rfloor$ ，又 $\lfloor \frac{n}{i} \rfloor < \frac{n}{i}$ ，有调和级数的渐近公式 $\sum^{n}_{i = 1} \frac{1}{i} \approx ln(n + 1) + 0.577218$ ，其中 $0.577218$ 是欧拉常数

所以复杂度是 $O(n\ log\ n)$ 级别

虽然这个筛法的时间复杂度很差，但是调和级数枚举引人深思，这种枚举方式非常巧妙，而且复杂度仅有 $O(log\ n)$ 级别

埃式筛法

在调和级数枚举的筛法中，我们发现枚举4的倍数无意义，因为从这里筛掉的数一定从2的倍数里筛掉了，所以我们想到：只用质数去筛

其复杂度只有 $O(n\ log\ log\ n)$

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int cnt, primes[N], n;
bool st[N];int main() {cin >> n;for (int i = 2; i <= n; i ++) {if (st[i]) continue;primes[cnt ++] = i;for (int j = 2 * i; j <= n; j += i) {st[j] = true;}}cout << cnt << endl;return 0;
}

欧拉筛

通过对埃氏筛法的分析，我们发现 $\times 3$ 会被质数 $2$ 和 $3$ 各筛一次。一个数有多少个质因子，它就会被筛多少次。那么我们能否让一个数只被筛掉一次呢？

欧拉筛法可以做到并且每个数会被它的最小质因子筛掉

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int cnt, primes[N], n;
bool st[N];int main() {cin >> n;for (int i = 2; i <= n; i ++) {if (!st[i]) primes[cnt ++] = i; //是素数for (int j = 0; j < cnt && primes[j] <= n / i; j ++) {st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}cout << cnt << endl;return 0;
}

设 $\times primes[j]$
若 $\ mod \ primes[j] \neq 0$ ，则 $i$ 中没有 $p r im es [j]$ 这个质因子。又因为 $j$ 是从小到大遍历的，所以 $p r im es [j] < i$ ，则 $p r im es [j]$ 是 $x$ 的最小质因子
若 $\ mod \ primes[j] = 0$ ，说明 $p r im es [j]$ 是 $i$ 的一个质因子。又因为 $j$ 是从小到大遍历的，所以 $p r im es [j]$ 是 $i$ 的最小质因子。所以 $p r im es [j]$ 是 $x$ 的最小质因子
综上所述，每个数都是被其最小质因子 $p r im es [j]$ 筛掉且只会被筛掉一次

约数

约数个数

对于一个正整数 $x$ ，由于唯一分解定理， $p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times p_4^{a_4}...$

对于 $x$ 的每一个约数 $y$ ， $y$ 都能写成 $p_1^{b_1} \times p_2^{b_2} \times p_3^{b_3} \times p_4^{b_4}... \ (0 \leq b_1 \leq a_1,0 \leq b_2 \leq a_2, 0 \leq b_3\leq a_3,0 \leq b_4 \leq a_4)$

所以约数个数为$(a_1 + 1) \times (a_2 + 1) \times (a_3 + 1) \times (a_4 + 1) \times … $

约数之和

约数之和 $(p_1^0 + p_1^1 + ... + p_1^{a_1}) \times (p_2^0 + p_2^1 + ... + p_2^{a_2}) \times (p_3^0 + p_3^1 + ... + p_3 ^ {a_3}) \times (p_4^0 + p_4^1 + ... + p_4^{a_4}) \times ...$

由分配律将上述括号拆开可得： $x_1 + x_2 + x_3 + ... +$ ，其中每一项都是 $x$ 的约数

#include <bits/stdc++.h>
using namespace std;using LL = long long;const int mod = 1e9 + 7;int n;
map<int, int> cnt;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 0; i < n; i ++) {int x;cin >> x;for (int j = 2; j <= x / j; j ++) {if (x % j != 0) continue;int t = 0;while (x % j == 0) {t ++;x /= j;}cnt[j] += t;}if (x > 1) cnt[x] ++;}   LL res = 1;for (auto& [u, v] : cnt) {LL t = 0;for (int j = 0; j <= v; j ++) {t = (t * u % mod + 1) % mod;}res = res * t % mod;}cout << res << endl;return 0;
}

模运算

乘法逆元

同余

GCD

欧拉函数

质数

约数

相关文章：