转载
同余
定义
若 \(a,b\) 为两个整数，且它们的差能被某个自然数 \(m\) 所整除，则称 \(a\) 就模 \(m\) 来说同余于 \(b\)，或者说 \(a\) 和 \(b\) 关于模 \(m\) 同余，记为 \(a \equiv b \pmod m\)。它意味着 \(a - b = m \times k\)（\(k\) 为某一个整数）。
例如 \(32 \equiv 2 \pmod 5\)，此时 \(k\) 为 \(6\)。
对于整数 \(a\)、\(b\) 和 \(m\)，若 \(a \bmod m = b \bmod m\)，则称 \(a\) 与 \(b\) 在 \(\bmod m\) 的意义下同余，记为 \(a \equiv b \pmod m\)。
由概念易得：
- 若 \(a \equiv b \pmod m\)，则定有 \(\sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c\)；
- 若 \(a \equiv b \pmod m\)，当且仅当 \(m \mid (a - b)\)。
\(\because a \equiv b \pmod m\)
\(\therefore \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c\)
\(\therefore m \mid (a - b) \Rightarrow m \mid (km + c - lm - c) \Rightarrow m \mid (km - lm) \Rightarrow m \mid (k - l)m\)
\(\therefore \text{结论成立}\)
性质
自反性：\(a \equiv a \pmod m\)。
对称性：若 \(a \equiv b \pmod m\)，则 \(b \equiv a \pmod m\)。
传递性：若\(a \equiv b \pmod m,b \equiv c \pmod m\)，则 \(a \equiv c \pmod m\)。
同加性：若 \(a \equiv b \pmod m\)，则 \(a + c \equiv b + c \pmod m\)。
\(\because a \equiv b \pmod m\)
\(\therefore \sqsupseteq k,l,\alpha \in \mathbb{Z},a = km + \alpha,b = lm + \alpha\)
\(\therefore a + c \equiv b + c \pmod m\)
\(\Rightarrow km + \alpha + c \equiv lm + \alpha + c \pmod m\)
\(\Rightarrow km + (a + c) \equiv lm + (a + c) \pmod m\)
\(\text{结论成立}\)
同乘性：若 \(a \equiv b \pmod m\)，则 \(a \times c \equiv b \times c \pmod m\)；
若 \(a \equiv b \pmod m,c \equiv d \pmod m\)，则 \(a \times c \equiv b \times d \pmod m\)。
\(\because a \equiv b \pmod m,c \equiv d \pmod m\)
\(\therefore \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c\)
\(\because c \equiv d \pmod m\)
\(\therefore \sqsupseteq k,l,\gamma \in \mathbb{Z},c = \alpha m + \gamma,d = \beta m + \gamma\)
\(\therefore ac \equiv bd \pmod m\)
\(\Leftrightarrow (km + c)(\alpha m + \gamma) \equiv (lm + c)(\beta m + \gamma) \pmod m\)
\(\Leftrightarrow k\alpha m^2 + c\alpha m + c\gamma \equiv l\beta m^2 + \gamma m + c\gamma \pmod m\)
\(\text{结论成立}\)
不满足同除性，但若 \(\gcd(c,m) = 1\)，则当 \(a \times c \equiv b \times c \pmod m\) 时，有 \(a \equiv b \pmod m\)。
\(ac \equiv bc \pmod m\)
\(\Rightarrow c(a - b) \equiv 0 \pmod m\)
\(\Rightarrow c \% m \times (a - b) \% m = 0\)
\(\Rightarrow m \mid c \text{或}m \mid (a - b)\)
\(\text{又}\because (m,c) = 1\)
\(\therefore m \mid (a - b)\)
\(a \equiv b \pmod m\)
同幂性：若 \(a \equiv m \pmod m\)，则 \(a^n \equiv b^n \pmod m\)。
证明1
\(\because a^n \equiv b^n \pmod m \Leftrightarrow \overbrace{a \times a \times \cdots \times a}^{a^n} \equiv \overbrace{b \times b \times b \times \cdots \times b}^{b^n} \pmod m\)
\(\therefore a \equiv b \pmod m\)
\(\because a \equiv b \pmod m\)
\(\therefore a \times a \equiv b \times b \pmod m\ \ \text{（结论6）}\)
\(\because a \times a\equiv b \times b \pmod m,a \equiv m \pmod m\)
\(\therefore (a \times a)\times a \equiv (b \times b)\times b \pmod m\ \ \text{（结论6）}\)
\(\cdots\)
\(\text{上述结论只需多次使用结论6即可得到}\)
证明2
\(\because \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c\)
\(\therefore \text{当}b = 2\text{时，有}(km + c)^2 \Leftrightarrow (km)^2 + 2kmc + c^2,(lm + c)^2 \Leftrightarrow (lm)^2 + 2lmc + c^2\)
\(\therefore \text{当}b = 3\text{时，有}(km + c)^3 \Leftrightarrow (km)^3 + 3(km)^2c + 3kmc^2 + c^3,(lm + c)^3 \Leftrightarrow (lm)^3 + 3(lm)^2c + 3lmc^2 + c^3\)
\(\cdots\)
\(\text{根据二次项定理，系数展开后常数项的为}c^n\text{，即}(a^n) \pmod m = (a \bmod m)^n,(b^n) \bmod m = (b \bmod m)^n\)
\(\because a \equiv b \pmod m\)
\(\therefore a^n \equiv a^n \pmod m\)
推论1：\(a \times b \pmod k = (a \bmod k)\times (b \bmod k)\bmod k\)。
推论2：若 \(p,q\) 互质，\(a \bmod p = x,a \bmod q = x\)，则 \(a \bmod (p \times q) = x\)。
\(\because p,q \text{互质，}a \bmod p = x,a \bmod q = x\)
\(\therefore \text{一定存在整数}s,t\text{，使得}a = s \times p + x,a = t \times q +x\)
\(\therefore s \times p = t \times q\)
\(\text{又}\because t \text{为整数，}p,q \text{互质，将}q \text{移到左边来}\)
\(\therefore q \mid s,\text{即存在整数}r\text{,使得}s = r \times q\)
\(\therefore a = r \times q \times p + x\text{，即}a \bmod (p \times q) = x\)
证明1
\(a \bmod q = x,a \bmod p = x\)
\(\therefore \sqsupseteq k,l \in \mathbb{Z},a = kq + x,b = lq + x\)
\(\therefore q \mid (a -x),p \mid (a -x)\)
\(\therefore (a -x)\text{是}q\text{与}p\text{的公倍数}\)
\(\therefore \sqsupseteq \alpha \in \mathbb{Z},(a - x) = \alpha pq + x\)
\(a = \alpha pq + x\)
\(a \bmod pq = x\)
证明2
\(\because a \bmod q = x,a \bmod p\)
\(\sqsupseteq k,l \in \mathbb{Z},a = kq + x = lp + x\)
\(\therefore kq + x = lp + x \Rightarrow kq = lp\)
\(\because \gcd(q,p) = 1\)
\(\therefore \sqsupseteq r \in \mathbb{Z},k = rp\)
\(\therefore a= rpq + x\)
\(\therefore a \bmod pq = x\)
素数
定义
一个大于 \(1\) 的自然数，不能被其它自然数整除的数叫做素数（质数），反之，不是素数的数被称为和数。
- \(1\) 既不是素数又不是和数；
- \(2\) 是最小的素数，也是唯一的偶素数；
- 素数的个数是无限的。
假设素数的个数是有限的，那么可以将所有素数表示为 \(a_1,a_2,a_3,\cdots ,a_n\)，设 \(m = a_1 + a_2 + a_3 + \cdots + a_n,p = m + 1\)，那么易证 \(p\) 不会被上述的所有素数整除，那么 \(p\) 也是一个素数，即假设不成立，可得素数的个数是无限的。
定理
算术基本定理（唯一分解定理）
任何一个大于 \(1\) 的正整数一定能被唯一分解为有限个素数的乘积，如下：
\(N = p_1^{c_1}p_2^{c_2}p_3^{c_3} \cdots p_n^{c_n}\)
其中 \(c_i\) 都为正整数，\(p_i\) 都为素数且满足 \(p_1 < p_2 < p_3 < \cdots < p_n\)。
\(N\) 中最多只能含有一个大于 \(\sqrt{N}\) 的因子
如果 \(N\) 的因子中有两个大于 \(\sqrt{N}\) 的因子，那么这两个因子相乘就会大于 \(N\) 了。
分解质因数
试除法
在 \(2\) 到 \(\sqrt{N}\) 中枚举，如果 \(i(2 \le i \le \sqrt{N})\) 可以被 \(N\) 整除且 \(i\) 为素数，那么处净并记录质因子的个数，如果最终个数 \(n > 1\)，这就说明这个就是 \(N\) 大于 \(\sqrt{N}\) 的质因子。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n, a[N];
void decompose(int x) {
for (int i = 2; i * i <= n; i++)
while (x % i == 0) x /= i;
if (x > 1) a[x]++;
}
int main() {
scanf("%d", &n);
decompose(n);
for (int i = 1; i <= n; i++)
if (a[i]) printf("%d %d\n", i, a[i]);
return 0;
}
时间复杂度：\(O(\sqrt{n})\)，最好情况为 \(n = 2^k\)，\(\log n\) 次完成；最坏情况是 \(n\) 本身就为素数，时间复杂度 \(O(\sqrt{n})\)。
例题 CF144A Division
题意：求最大的正整数 \(x\)，使 \(a \mid p\) \(q \nmid x\)。
题解
当 \(q \nmid p\) 时，显然 \(x_{max} = p\)。
当 \(q \mid p\) 时，考虑对 \(q\) 分解质因数。
可得：\(q = m_1^{c_1}m_2^{c_2}m_3^{c_3} \cdots m_n^{c_n}\)。
那么，\(x\) 不为 \(q\) 的倍数，当且仅当存在 \(i\)，使得 \(x\) 分解质因数后 \(m_i\) 的次数大于 \(c_i\)。
所以，可以枚举每一个 \(m_i\)，使 \(x\) 分解质因数后 \(m_i\) 的次数为 \(c_i -1\)，其余全部取最大即可。也就是说，设 \(t\) 是 \(p\) 除尽后剩下的数，则最优解为 \(p_i^{c_i - 1} \times t\)。
最后在这些最优解中遍历取最大值即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int T;
ll p, q, ans, s;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%lld%lld", &p, &q);
ans = 0, s = p;
if (p % q) {
printf("%lld\n", s);
continue;
}
for (ll i = 2; i * i <= q; i++) {
if (q % i == 0) {
ll t = 1;
while (p % i == 0) p /= i, t *= i;
while (q % i == 0) q /= i, t /= i;
ans = max(ans, s / t / i);
}
}
if (q > 1) {
ll t = 1;
while (p % q == 0) p /= q, t *= q;
ans = max(ans, s / t);
}
printf("%lld\n", ans);
}
return 0;
}
你可能要问，啊你这个代码和你讲的不太一样啊，因为代码是我提前打的。
单个素数的判定
单个素数的判定时间复杂度为 \(O(\sqrt{n})\)。
#include <bits/stdc++.h>
using namespace std;
int n, t;
bool prime(int x) {
if (x == 1) return 0;
for (int i = 2; i * i <= x; i++)
if (x % i == 0) return 0;
return 1;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &t);
if (prime(t)) printf("%d ", t);
}
return 0;
}
素数筛
埃氏筛法
对于求出每个范围内的所有素数，可以从 \(2\) 开始1，将 \(2\) 的所有倍数全部晒去，剩下的为被筛掉第一个数（\(3\)）即为第二个素数；再将 \(3\) 的所有倍数筛去，以此类推。由此，我们便可以筛出 \(n\) 以内的所有素数。
埃氏筛法是一种时间复杂度为 \(O(n\log \log n)\) 的筛法。之所以会浪费时间复杂度，是因为埃氏筛法在筛数的过程中有重复筛去同一个数的过程，例如 \(6\) 在 \(i = 2\) 时就被筛过一次，在 \(i = 3\) 时又被筛了一次，浪费了部分时间复杂度。所以，便有了时间复杂度更优的算法——线性筛。
快速线性筛法
又被称为欧拉筛法，每个和数只被它最小的质因子筛去，时间复杂度为 \(O(n)\)。
线性筛的方法是从小到大枚举每一个数，会有以下情况：
- 如果当前函数未被划掉，则这个数定为素数，记录该素数；
- 枚举已记录的素数（如果合数已越界则中断）
(1) 合数未越界，则划掉合数；
(2) 条件 \(i \% p == 0\)，保证合数只被最小质因子划掉。
若 \(i\) 为素数，保证最多枚举到自身中断；
若 \(i\) 为合数，则最多枚举到自身的最小素数中断。
当 \(n = 30\) 时，线性筛过程如下：
\(i = 2;\ p_2;\ v_4;\ (2 \% 2)\ break\)
\(i = 3;\ p_3;\ v_{6,9};\ (3 \% 3)\ break\)
\(i = 3;\ \ \ \ \ \ \ v_8;\ (4 \% 2)\ break\)
\(i = 5;\ p_5;\ v_{10,15,25};\ (5 \% 5)\ break\)
\(i = 6;\ \ \ \ \ \ \ v_{12};\ (6 \% 2)\ break\)
\(i =7;\ p_7;\ v_{14,21};\ (35 > 30)\)
\(i = 8;\ \ \ \ \ \ \ v_{16};\ (8 \% 2)\ break\)
\(i = 9;\ \ \ \ \ \ \ v_{18,27};\ (9 \% 3)\ break\)
\(i = 10;\ \ \ \ \ \ \ v_{20};\ (10 \% 2)\ break\)
\(i = 11;\ p_{11};\ v_{22};\ (33 > 30)\)
\(i = 12;\ \ \ \ \ \ \ v_{24};\ (12 \% 2)\ break\)
\(\cdots\)
\(i = 16;\ \ \ \ \ \ \ (32 > 30)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 100000005;
int cnt;
int vis[N], prime[N];
void get_prime(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) prime[++cnt] = i;
for (int j = 1; 1ll * i * prime[j] <= n; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main() {
int n, m, k;
scanf("%d%d", &n, &m);
get_prime(n);
while (m--) {
scanf("%d", &k);
printf("%d\n", prime[k]);
}
return 0;
}
上面代码中 if (i % prime[j] == o) break; 用于控制每个合数只被筛掉一次。
\(i = 2 \times 3 \times 5\)，此时能筛筛除 \(2 \times i\)，但不能筛除 \(3 \times i\)。如果此时筛除\(3 \times i\) 的话，当 \(i' = 3 \times 3 \times 5\) 时，筛除 \(2 \times i'\) 就和前面重复筛了，也就是说，如果 \(i \bmod prime_j == 0\)，说明 \(i\) 自身有一个最小质因子 \(prime_j\)，根据线性筛的原理，到此终止即可。
欧拉函数
定义
对于正整数 \(n\)，其欧拉函数是指小于等于 \(n\) 的数中与 \(n\) 互质的数的个数，用字母 \(\varphi\) 表示。
通项公式：
\(\varphi(n) = n \times \prod_{i = 1}^k (i - \frac{1}{p_i})\)
其中 \(p_1,p_2,\cdots,p_k\) 为 \(n\) 的所有质因数，\(n\) 为正整数。
\(\varphi(12) = 4\)，即 \(12\) 以内与 \(n\) 互质的数的个数为 \(4\)，有 \(1,5,7,11\)。
利用通项公式计算如下：
\(\varphi(12) = 12 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 4\)
解释：\(12\) 的质因子 \(2,3\)。
性质
- \(\varphi(1) = 1\)。
- 若 \(p\) 为一个素数，则 \(\varphi(p) = p - 1\)。
- 若 \(p\) 为一个素数，则 \(\varphi(p^k) = (p - 1) \times p^{k - 1}\)。
- 欧拉函数为积性函数：对于任意两个正整数 \(a,b\)，且 \(\gcd(a,b) = 1\) 互质，则 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)。特别的，对于奇数 \(n\)，\(\varphi(2n) = \varphi(n)\)。
易证性质 \(1,2\)。
性质 \(3\)：对于 \(n = p^k\)，比 \(n\) 小的正整数有 \(p^{k - 1} - 1\) 个。其中，所有能被 \(p\) 整除的那些数可以表示成 \(p \times t\) 的形式 \((t = 1,2,3,\cdots,p^{k-1} - 1)\)，共有 \(p^{k - 1} - 1\) 个数能被 \(p\) 整除（不能算 \(p^{k - 1}\)，因为 \(p^{k - 1} \times p = n\)），也就是说这些数不与 \(p^k\) 互质。所以 \(\varphi(p^k) = p^k - 1 - (k^{k - 1} - 1) = p^k - p^{k - 1} = (p - 1) \times p^{k - 1}\)。
性质 \(4\)：需要使用中国剩余定理，没学过可以先跳过（我就直接跳过）。
令 \(\mathbb{Z} _ n\) 表示模 \(n\) 剩余类环，则易证 \(\forall a \forall b(\gcd(a,b)) = 1 \wedge ab \Rightarrow \mathbb{Z} _ n \cong \mathbb{Z} _ a \oplus \mathbb{Z} _ b\)。由裴蜀定理，\(k\) 为环 \(\mathbb{Z} _ n\) 中可逆元当且仅当 \(\gcd(k,n) = 1\)，故环 \(\mathbb{Z} _ n\) 中可逆元数量为 \(\varphi(n)\) 且环 \(\mathbb{Z} _ a \oplus \mathbb{Z} _ b\) 中可逆元数量为 \(\varphi(a)\varphi(b)\)。由于 \(\mathbb{Z} _ n \cong \mathbb{Z} _ a \oplus \mathbb{Z} _ b\)，故 \(\varphi(n) = \varphi(a)\varphi(b)\)。
欧拉函数性质变形
- \(p\) 为素数，若 \(n \% p = 0\)，则 \(\varphi(n \times p) = p \times \varphi(n)\)。
\(n \times p\) 的素因子和 \(n\) 是一样的，所以利用欧拉函数公式把 \(\varphi(n \times p)\) 展开即可。（本条变形一些资料都要求 \(p\) 为素数，实际上 \(p\) 不为素数依旧成立，
我不会证，这里不给详细的证明了。）
- \(p\) 为素数，若 \(n \% p \neq 0\)，则 \(\varphi(n \times p) = (p - 1) \times \varphi(n)\)。
\(p\) 为素数，\(n \% p \neq 0\)，所以 \(n\) 和 \(p\) 互质，满足积性函数。
- 当 \(n\) 为奇数时，\(\varphi(2n) = \varphi(n)\)。
- 与 \(n\) 互质的数都是成对出现的，且每对的和为 \(n\)，所以大于 \(2\) 的数的 \(\varphi(n)\) 都为偶数。
假设 \(\gcd(n,x) = 1,x < n,x > 2\)，但是 \(\gcd(n,n - x) = k (k > 1)\)，则可以改写成 \(n = a \times k,n - x = b \times k\)，那么移项可得 \(x = n - k \times k = a \times k - b \times k = (a - b)\times k\)，则 \(\gcd(n,x) = \gcd(ak,(a - b)k)\)，它们至少有一个公约数 \(k\)，与假设矛盾。
欧拉函数证明
欧拉函数计算公式
由唯一分解定理 \(n = \prod_{i = 1}^s p_i^{a_i} = p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_s^{a_s}\)，\(\varphi(n) = \prod_{i = 1}^s \varphi(p_i^{a_i})\)（根据性质4，积性函数）
\(\ \ \ \ \ \ \ \ \ = \prod_{i = 1}^s p_i^{a_i - 1}(p_i - 1)\)（根据性质3）
\(\ \ \ \ \ \ \ \ \ = \prod_{i = 1}^s p_i^{a_i} (1 - \frac{1}{p_i})\)
\(\ \ \ \ \ \ \ \ \ = \prod_{i = 1}^s p_i^{a_i} \times \prod_{i = 1}^s(1 - \frac{1}{p_i})\)
\(\ \ \ \ \ \ \ \ \ = n \times \prod_{i = 1}^s \frac{p_i - 1}{p_i}\)
\(\ \ \ \ \ \ \ \ \ = n \times \frac{p _ 1 - 1}{p _ 1} \times \frac{p _ 2 - 1}{p _ 2} \times \frac{p _ 3 -1}{p _ 3} \times \cdots \times \frac{p _ s - 1}{p _ s}\)
欧拉函数仅由 \(n\) 和质因子决定，与次数无关。
\(\varphi(12) = 12 \times \frac{2 - 1}{2} \times \frac{3 - 1}{3} = 4\)
试除法求欧拉函数
如果只要求一个数的欧拉函数值，那么直接根据定义，在质因数分解的同时求就好了。
int varphi(int n) {
int m = int(sqrt(n + 0.5));
int ans = n;
for (int i = 2; i <= m; i++) {
if (n % i == 0) {
ans /= i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) ans /= n * (n - 1);
return ans;
}
求 \(1\) 到 \(n\) 的所有欧拉函数值
筛法求欧拉函数
若 \(i\) 为素数，则 \(phi _ i = i - 1\)。
在线性筛中，每个合数 \(m\) 都是被最小的质因子筛掉的。
设 \(p_i\) 是 \(m\) 的最小质因子，则 \(m\) 通过 \(m = p _ j \times i\) 筛掉。
- 若 \(i\) 能被 \(p _ j\) 整除，则 \(i\) 包含了 \(m\) 的所有质因子。
\(\varphi(m) = m \times \prod_{k = 1}^s \frac{p _ k - 1}{p _ k} = p _ j \times i \times \prod_{k = 1}^s \frac{p _ k -1}{p _ k} = p _ j \times \varphi(i)\)
\(\varphi(12) = \varphi(2 \times 6) = 2 \times \varphi(6)\)
- 若 \(i\) 不能被 \(p _ j\) 整除，则 \(t\) 和 \(p_j\) 是互质的。
\(\varphi(m) = \varphi(p _ j \times i) = \varphi(p _ j) \times \varphi(i) = (p _ j -1) \times \varphi(i)\)
\(\varphi(75) = \varphi(3 \times 25) = (3 - 1) \times \varphi(25)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int p[N], vis[N], cnt;
int phi[N];
void get_phi(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
p[cnt++] = i;
phi[i] = i - 1;
}
for (int j = 0; i * p[j] <= n; j++) {
int m = i * p[j];
vis[m] = 1;
if (i % p[j] == 0) {
phi[m] = p[j] * phi[i];
break;
} else phi[m] = (p[j] - 1) * phi[i];
}
}
}
int main() {
int n;
scanf("%d", &n);
get_phi(n);
for (int i = 1; i <= n; i++) printf("%d\n", phi[i]);
return 0;
}
线性筛求约数个数与约数和
约数个数根据数字唯一分解定理，设 \(n = p_i^{r_1} \times p_2^{r_2} \times p_3^{r_3} \times \cdots \times p_k^{r_k}\)。
对于每个 \(n\) 的约数，一定是由以上素数 \(p_1 \sim p_k\) 相乘而来，根据乘法原理，每个质因数都可以选择 \(0\) 到 \(r_i\) 这 \(r_i + 1\) 选择。
\(n\) 的约数即为 \(d(n) = (r_1 + 1) \times (r_2 + 1) \times (r_3 + 1) \times \cdots \times (y_k + 1) = \prod_{i = 1}^k (r_i + 1)\)。
筛的过程中需要保存 \(n\) 的最小质因子的出现个数（也就是次幂），即 \(r_1\)。
\(d_i\) 记录 \(i\) 的约数个数；
\(num_i\) 记录 \(i\) 的最小质因数个数（次幂）。
分情况讨论
\(i\) 是素数
\(d_i = 2~~~~~~~~ num_i = 1\)
\(d_i\)：\(i\) 是素数，所以约数只有 \(1\) 和自身，约数个数为 \(2\)；
\(num_i\)：\(i\) 是素数，自小质因子就是自己，个数是 \(1\)。
\(i\) 和枚举的第 \(j\) 个指数取模为 \(0\) ，即 i % prime[j] == 0
\(prime_j\) 为 \(i\) 的因子，\(i \times prime_j\) 唯一分解不会产生新的质因子，依旧是 \(p_1,p_2,p_3,\cdots ,p_k\)，\(prime_j\) 从小到大枚举，所以一定是 \(i\) 的最小质因子。所以 \(i \times prime_j\) 的最小质因子次幂变为 \(r_1 + 1\)，按唯一分解定理展开：\(d_{i \times prime_j} = (1 + r_ +1) \times \cdots \times (1 + r_k)\)。
因为递推的过程是从已知的 \(d_i\) 推出 \(d_{i \times prime_j}\) 的值，所以可以用维护的 \(num_j\) 将 \(d_i\) 转移到 \(d_{i \times prime_j}\)。转移方程为：\(d_{i \times prime_j} = d_i \div (num_i + 1) \times (num_i + 1 + 1)\)。
\(\begin{cases} d(i) = (r_1 + 1) \times (r_2 + 1) \times \cdots \times (r_k + 1)\\ d(i \times prime_j) = (1 + r_1 + 1) \times \cdots \times (1 + r_k) \end{cases}\)
找出二者之间的地推关系，很明显，就是一式除以 \(r_1 + 1\)再乘以 \(1 + r_1 + 1\)。
即可转换为二式。\(num_{i \times prime_j} = num_j + 1\)。
同时应当注意，\(num_{i \times prime_j}\) 也要进行转移，加上最小质因子 \(prime_j\) 的贡献也就是：\(num_{i \times prime_j} = num_i + 1\)。
当前数取模枚举的第 \(j\) 个素数不为 \(0\)，即 \(prime_j\) 不能整除 \(i\)
已知 \(i \times prime_j\) 这个数中之前一定不包含 \(prime_j\) 这个质因子，那么约数个数要加上 \(prime_j\)，即为：
\(d_{i \times prime_j} = (r_1 + 1) \times (r_2 + 1) \times (r_3 + 1) \times \cdots \times (r_k + 1) \times (1 + 1) = d_i \times 2 = d_i \times d_{prime_j}\)。
对于最小质因子，由于 \(j\) 时从小到大枚举的，所以 \(i \times prime_j\) 的最小质因子也是 \(prime_j\)。
所以可以得到：\(num_{i \times prime_j} = 1\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int prime[N], d[N], num[N]; //prime[i]存储所有素数，d[i]表示i的约数个数，num[i]表示i的最小质因数的个数
int n, cnt;
bool st[N];//st[i]存储i是否被筛掉
void get_prime(int n) {
d[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
prime[cnt++] = i;
d[i] = 2, num[i] = 1;
}
for (int j = 0; i * prime[j] <= n; j++) {
st[i * prime[j]] = 1;
if (i % prime[j] == 0) {
d[i * prime[j]] = d[i] / (num[i] + 1) * (num[i] + 2);
num[i * prime[j]] = num[i] + 1;
break;
}
d[i * prime[j]] = d[i] * d[prime[j]];//于下面两行代码等价
// d[i * prime[j]] = d[i] * 2;
// num[i * prime[j]] = 1;
}
}
}
int main() {
scanf("%d", &n);
get_prime(n);
for (int i = 1; i <= n; i++)//输出1~n之间所有数约数个数
printf("d[%d]=%d\n", i, d[i]);
return 0;
}
约数和
设 \(sd_i\) 表示 \(i\) 的约数和，根据算术基本定理可得：
\(sd_n=(p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{r_1}) \times (p_2^0 + p_2^1 + p_2^2 + \cdots + p_2^{r_2}) \times \cdots \times (p_k^0 + p_k^1 + p_k^2 + \cdots + p_k^{r_k})\)。
设 \(n = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \cdots \times p_k^{a_k}\)，可知 \(p_1^{a_1}\) 的约数为 \(p_1^0,p_1^1,p_1^2,\cdots,p_1^{a_1}\)。
同理，\(p_k^{a_k}\) 的约数为 \(p_k^0,p_k^1,p_k^2,\cdots,p_k^{a_k}\)。
实际上 \(n\) 的约数是在 \(p_1^{a_1},p_2^{a_2},\cdots,p_k^{a_k}\) 的每一个的约数中分别挑选一个相乘得来的，可知共有 \((\alpha_1 + 1) \times (\alpha_1 + 1) \times (\alpha_1 + 1) \times \cdots \times (\alpha_1 + 1)\) 种挑法，即约数的个数。
由乘法原理可知它们的和为：
\(f(n) = (p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{a_1}) \times (p_2^0 + p_2^1 + p_2^2 + \cdots + p_2^{a_2}) \times \cdots \times (p_k^0 + p_k^1 + p_k^2 + \cdots + p_k^{a_k})\)。
设 \(num_i\) 表示最小质因子的一项：\(num_i = p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{r_1}\)。
\(i\) 是素数
\(sd_i = num_i = i + 1\)
\(i\)是素数，它的约数只有 \(1\) 和自己，约数和为 \(i + 1\)；质因子分解也只能分解出之际，\(sd_i = i_0 + i_1 = i + 1\)。
\(i \%\) 枚举的素数 \(prime_j\) 不为 \(0\)，即 \(prime_j\) 不能整除 \(i\)
以下讨论中将使用 \(p_j\) 代指 \(prime_j\)。
\(i \times p_j\) 里原来没有 \(p_j\) 这一项，加上这一项后：
\(\because sd_i = (p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{r_1}) \times (p_2^0 + p_2^1 + p_2^2 + \cdots + p_2^{r_2}) \times \cdots \times (p_k^0 + p_k^1 + p_k^2 + \cdots + p_k^{r_k})\)
\(\text{又} \because sd_{i \times p_j} = (p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{r_1}) \times (p_2^0 + p_2^1 + p_2^2 + \cdots + p_2^{r_2}) \times \cdots \times (p_k^0 + p_k^1 + p_k^2 + \cdots + p_k^{r_k})\)
因为 \(i \% p_j \neq 0\)，所以 \(i\) 中是不含 \(p_j\) 这个素数的，那么 \(i \times p_j\) 中质因子分解就在原来的 \(p_1,p_2,\cdots,p_k\) 的基础上又多能分解出来一个 \(p_j\)，所以在求 \(sd_{i \times p_j}\)
时，需要多 \(\times (p_j^0 + p_j^1)\)。
\(\text{双} \because p_j \text{是素数}\)
\(\therefore sd_{p_j} = p_j^0 + p_j^1\)
\(\therefore sd_{i \times p_j} = sd_i \times sd_{p_j} \text{（注：积性函数）}\)
同时更新 \(num_{i \times p_j}\)：
\(num_{i \times p_j} = num_{p_j} = p_j^0 + p_j^1 = p_j + 1\)。因为质因子从小到大枚举，那么 \(i \times p_j\) 的最小质因子就是 \(p_j\)，\(num_{i \times p_j}\) 也就应该等于 \(num_{p_j}\)。
\(i \%\) 枚举的素数 \(p_j\) 为 \(0\)，即 \(i \% p_j == 0\)
那么 \(sd_{i \times p_j}\) 中的第一项就是 \(num_{i \times p_j}\)。
等比数列变形技巧：
\(1 + p_i + p_i^2 + \cdots + p_i^{r_1}\)，这时可以变成 \(1 + p_i + p_2^i + \dots + p_i^{r_i} + p_i^{r_i + 1}\)，那么只需要所有都乘以 \(p_i\)，然后再加 \(1\)即可。
\((1 + p_i +p_2^i + \cdots + p_i^{r_i}) \times p_i + 1 = 1 + p_i + p_2^i + \cdots + p_i^{r_i} + p_i^{r_i + 1}\)
结论：\(num_{i \times p_j} = num_i \times + 1\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 10005;
bool st[N];
int n, cnt;
int num[N], sd[N], prime[N];//num最小质因子pi组成的等比数列，sd约数和
void get_prime (int n) {
sd[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
prime[cnt++] = i;
sd[i] = num[i] = i + 1;
}
for (int j = 0; prime[j] * i <= n; j++) {
st[i * prime[j]] = 1;
if (i % prime[j]) {
sd[i * prime[j]] = sd[i] * sd[prime[j]];
num[i * prime[j]] = prime[j] + 1;
} else {
sd[i * prime[j]] = sd[i] / num[i] * (num[i] * prime[j] + 1);
num[i * prime[j]] = num[i] * prime[j] + 1;
break;
}
}
}
}
int main() {
scanf("%d", &n);
get_prime(n);
for (int i = 1; i <= n; i++)
printf("sd[%d]=%d\n", i, sd[i]);
return 0;
}
欧拉定理（费马小定理）
剩余类
给定一个正整数 \(n\)，把所有整数根据模 \(n\) 的余数 \(r \in [0,n - 1]\) 分为 \(n\) 类，每类表示为 \(C_r = nx + r\) 的形式，这类数所构成的一个集合成为模 \(n\) 的剩余类。
\(n = 5,r = 3\)，则 \(C_3 = 5x + 3\) 为模 \(5\) 的一个剩余类。
完全剩余类
给定一个正整数 \(n\)，有 \(n\) 个不同的剩余类中各取出一个元素，共 \(n\) 个数，将这些数构成一个全新的集合，则称这个集合为模 \(n\) 的完全剩余系。
\(n = 5\)，则 \({0,1,2,3,4}\) 是模 \(5\) 的完全剩余系，\(5,1,7,8,9\) 也是一个模 \(5\) 的完全剩余系。
简化剩余系
给定一个正整数 \(n\)，有 \(\varphi(n)\) 个不同的模 \(n\) 的余数 \(r\) 和 \(b\) 互质的剩余类，从这 \(\varphi(n)\) 个剩余类中各取出一个元素，共 \(\varphi(n)\) 个数，将这些数构成一个新的集合，称为模 \(n\) 的简化剩余系。
\(n = 5\)，则 \({1,2,3,4}\) 是一个模 \(5\) 的简化剩余系；\(n = 10\)，则 \({1,3,5,9}\) 是一个模 \(10\) 的简化剩余系。
显然，模 \(n\) 的简化剩余系中的所有书都与 \(n\) 互质。
欧拉定理
模的 \(m\) 可以为合数。
若 \(\gcd(a,m) = 1\),则 \(a^{\varphi(m)} \equiv 1 \pmod m\)。
特别的，当 \(m\) 为素数时，与费马小定理一致。
\(n = 3,m = 4\)，则 \(s^{\varphi(4)} \equiv 3^2 \equiv 1 \pmod 4\)。
\(n = 3,m = 5\)，则 \(3^{\varphi(5)} \equiv 3^4 \equiv 1 \pmod 5\)。
证明
构造一个与 \(m\) 互质的数列，再进行如下操作：
设 \(r_1,r_2,r_3,\cdots,r_{\varphi(m)}\) 为模 \(m\) 意义下的一个简化剩余系，则 \(ar_1,ar_2,ar_3,\cdots,ar_{\varphi(m)}\) 也是模 \(m\) 意义下的一个简化剩余系。因为 \(a\) 和 \(m\) 互质，所以 \(r_1,r_2,r_3,\cdots,r_{\varphi(m)}\) 也和 \(m\) 互质。
所以 \(r_1 \times r_2 \times r_3 \times \cdots \times r_{\varphi(m)} \equiv ar_1 \times ar_2 \times ar_3 \times \cdots \times ar_{\varphi(m)} \equiv a^{\varphi(m)} \times r_1 \times r_2 \times r_3 \times \cdots \times r_{\varphi(m)} \% m\)，可约去 \(r_1 \times r_2 \times r_3 \times \cdots \times r_{\varphi(m)}\) 这个集合。
当 \(m\) 为素数时，由于 \(\varphi(m) = m - 1\)，代入欧拉定理即可得到费马小定理。
费马小定理
若 \(m\) 为素数，对于任意数 \(a\)，有 \(a^m = a \pmod m\)。
特殊的，若 \(m\) 为素数，整数 \(a\) 不是 \(m\) 的倍数（即 \(\gcd(a,m) = 1\)），则 \(a^{m - 1} \equiv 1 \pmod m\)。
引理1（同除性）
若 \(a,b,c\) 是任意三个整数，\(m\) 为正整数且 \(m\) 与 \(c\) 互质（之后将写作 \((m,c) = 1\)），则当 \(ac \equiv bc \pmod m\) 时，有 \(a \equiv b \pmod m\)。
可知 \((a-b)c \equiv 0 \pmod m\)
由于 \((m,c) = 1\)，所以 \((a - b)\) 是 \(m\) 的倍数，即 \(a - b \equiv 0 \pmod m\)
根据同余的同加性，可得 \(a \equiv b \pmod m\)。
引理2
\(m\) 是大于 \(1\) 的整数，\(a\) 是整数且 \((m,a) = 1\)，如果 \(b_i(i \in [1,m])\) 是模 \(m\) 的完全剩余系，则 \(a \times b_i(i \in [1,m])\) 也是模 \(m\) 的一个完全剩余系。
若存在两个整数 \(a \times b_i,a \times b_j\) 同余，那么 \(s \times b_i \equiv a \times b_j \pmod m\)。
由引理1可知，\(b_i \equiv b_j \pmod m\)。
与原定义矛盾，故不存在两个整数 \(a \times b_i,a \times b_j\) 同余。
所以 \(a \times b_i (i \in [1,m])\) 是模 \(m\) 的一个完全剩余系。引用一个性质：
设一个素数为 \(p\)，我们取一个不为 \(p\) 的倍数的数 \(a\)。
构造一个序列：\(A = 1,2,3,\cdots,p-1\)，这个序列有这样一个性质：
\(\prod_{i = 1}^{p - 1} A_i = \prod_{i = 1}^{p - 1} (A_i \times a) \pmod p\)。\(\because \gcd(A_i,p) = 1,\gcd(A_i \times a,p) = 1\)（都为 \(A\) 的完全剩余系）
\(\text{又} \because \text{每一个}A_i \times a \pmod p \text{独一无二，且}A_i \times a \pmod p < p\)
\(\therefore \text{每一个}A_i \times a \text{都对应}A_i\)
设 \(f = (p - 1)!\)，则 \(f \equiv a \times A_1 \times a \times A_2 \times a \times A_3 \times \cdots \times A_{p - 1} \pmod p\)。
\(\therefore a^{p - 1} \times f \equiv f \pmod p\)
由以上性质证明中的 \(a^{p - 1} \times f \equiv f \pmod p\)，又因为 \(\gcd(f,p) = 1\)，所以 \(a^{p - 1} \equiv 1 \pmod p\)。得证。
扩展欧拉定理
\(a^b \equiv \begin{cases}
a^{b \bmod \varphi(p)},\gcd(a,p) = 1\\
a^b,\gcd(a,p) \neq 1,b < \varphi(p) \pmod p\\
a^{b \bmod \varphi (p) + \varphi(p)},\gcd(a,p) \neq 1,b \ge \varphi(p)\\
\end{cases}\)
当 \(b\) 较小时，不用降幂，直接跑快速幂；
当 \(b\) 较大时，先用扩展欧拉定理降为小数，再跑快速幂。
\(a = 2,p = 4,b = 1,2^1 \neq 2^{1 \bmod 2+2} \pmod 4 \Leftarrow\)当 \(b < \varphi(p)\) 时，不满足变形式
\(a = 2,p = 4,b = 6,2^6 \equiv 2^{6 \bmod 2 + 2} \pmod 4\)
逝世口算这个： \(7^{555} \bmod 13\)
因为你们都是大佬，相必可以很轻松地想到，\(7\) 和 \(13\) 互质，\(\varphi(13) =13\)，那么我们就应该凑 \(7^{12}\)：\(7^{555} = 7^{12 \times 46 + 3} \times 7^3\)
接下来，就是欧拉定理时间：\((7^{12})^{46} \times 7^3 \equiv 1^{46} \times 7^3 \pmod {13}\)
那么只需求出 \(7^3 \bmod 13\) 即可，易得答案为 \(5\)。
机智的大佬就会想到：\(a^b \equiv a^{b \bmod \varphi(p)} \pmod p\)，目测似乎扩展欧拉定理。
已知欧拉定理：\(a^{\varphi(p)} \equiv 1 \pmod p\)，设 \(b = k \varphi(p) + r,0 \le r \le \varphi(p)\)
\(a^b \equiv (a^{\varphi(p)})^k \times a^r \equiv l^k \times a^r \equiv a^{b \bmod \varphi(p)} \pmod p\)
但是，它只有在 \(a\) 与 \(p\) 互质时才成立（因为欧拉定理的前提就是 \(a\) 与 \(p\) 互质），所以，我们尝试将其扩展到一般情况，即扩展欧拉定理：\(a^b \equiv a^{b \bmod \varphi(n) + \varphi(n)} \pmod n\)。
先分解 \(a\) 的质因数：\(a = p_1^{r_1} \times p_2^{r_2} \times p_3^{r_3} \times \cdots \times p_s^{r_s}\)
如果可以证明 \(p^b \equiv p^{b \bmod \varphi(n) + \varphi(n)} \pmod n\)（\(p\) 为素数）
就可以得到 \(p^{r_i} \equiv p^{b\bmod \varphi(n) + \varphi(n)} \pmod n\)
即可得到 \((p^{r_i})^b \equiv (p^{r_i})^{b \bmod \varphi(n) + \varphi(n)} \pmod n\)
把每个 \((p_i^{r_i})^b\) 乘起来，即可得到 \((p_1^{r_1} \times p_2^{r_2} \times p_3^{r_3} \times \cdots \times p_s^{r_s})^b \equiv (p_i^{r_i})^{b \bmod \varphi(n) + \varphi(n)} \pmod n\)
即 \(a^b \equiv a^{b \bmod \varphi(n) + \varphi(n)}\)
证明 \(p^b \equiv p^{b \bmod \varphi(n) + \varphi(n)} \pmod n\)（\(p\) 为素数）
若 \(p\) 与 \(n\) 互质：
显然 \((p^b \times p^{\varphi(n)}) \equiv p^{b \bmod \varphi(n) + \varphi(n)} \pmod n\)，而 \(p^{\varphi(n)} \bmod n = 1\)（欧拉定理），得证。
若 \(p\) 与 \(n\) 不互质：
由于 \(p\) 为素数，所以 \(n \ge 2p\)。
设 \(n = s \times p^r\)，其中 \(r = \lfloor \log_p^n \rfloor\) （看作把 \(n\) 质因数分解后含有 \(p^r\)，剩余的都在 \(s\) 里，剩下的 \(s\) 不含因数 \(p\)），那么 \(\gcd(s,p^r) = \gcd(s,p) = 1\)；
由于 \(s\) 与 \(p\) 互质，所以可以使用欧拉定理：\(p^{\varphi(s)} \equiv 1 \pmod s\)
易得 \((p^{\varphi(s)})^{\varphi(p^k)} \equiv 1 \pmod s\)
欧拉函数是积性函数，又因为 \(p^k\) 与 \(s\) 互质，所以：\(p^{\varphi(n)} \equiv 1 \pmod s \cdots\)
又因为 \(p^b = (p^{\varphi(n)}) ^ {\lfloor b \div \varphi(n) \rfloor} \times p^{b \bmod \varphi(n)}\)
双因为 \((p^{\varphi(n)}) ^ {\lfloor b \div \varphi(n) \rfloor} \bmod s = 1\)（见上，\(p^{\varphi(n)} \equiv 1 \pmod s \cdots\)，根据同幂性，两边取 \(\lfloor b \div \varphi(n) \rfloor\) 次方后依旧满足性质）
可得 \(p^b \equiv p^{b \bmod \varphi(n)} \pmod {s \times p^k}\)
若 \(a \equiv b \pmod m\)，则易得 \(a \times k \equiv b \times k \pmod {m \times k}\)
所以 \(p^{b + k} \equiv p^{b \bmod \varphi(n) + k} \pmod n\)
两边同乘 \(p^{\varphi(n) - k}\)，得 \(p^{b + \varphi(n)} \equiv p^{b \bmod \varphi(n) + \varphi(n)} \pmod n \cdots\)
又有 \(p^b \equiv p^{b - k} \times p^k \pmod n\)
所以 \(p^b \equiv p^{b + \varphi(n)} \pmod n\)
最后带入 \(p^{b + \varphi(n)} \equiv p^{b \bmod \varphi(n) + \varphi(n)} \pmod n \cdots\)，得 \(p^b \equiv p^{b + \varphi(n)} \pmod n\)
得证
秦九韶算法
详见 https://zhuanlan.zhihu.com/p/51300835 和 https://www.cnblogs.com/fusiwei/p/11782689.html。
我保证我不是懒得写。
最大公约数
最大公约数指两个及以上个整数共有因数中最大的一个，一般用 \(\gcd\) 表示。
欧几里德算法
辗转相除法求最大公约数
在数学上，求最大公约数的方法同样适用于电脑。用信息学的语言表示出来就是 \(\gcd(x,y)=\gcd(x,x\%y)\)，这种方法的事件复杂度为 \(O(\log n)\)。
int gcd(int x, int y) {
return (y == 0 ? x : gcd(y, x % y));
}
辗转相减法
同样是一种数学上通用的思路，不多做介绍。
多个数求最大公约数
逐个求出相邻两数的最大公约数，再把上一次求出的最大公约数和下一个数求 \(\gcd\) 即可。
最小公倍数
对于两个整数 \(a\) 和 \(b\)，先对它们进行质因数分解，对于分解出来的素数 \(pi_i\)，取数量较多的相乘，最后的乘积即为最小公倍数，一般用 \(lcm\) 表示。
\(a=pi_1^{anum_1} \times pi_2^{anum_2} \times \cdots \times pi_n^{anum_n}\)，\(b=pi_1^{bnum_1} \times pi_2^{bnum_2} \times \cdots \times pi_n^{bnum_n}\)，它们的最小公倍数为 \(lcm=pi_1^{\max(anum_1,bnum_1)} \times pi_2^{\max(anum_2,bnum_2)} \times \cdots \times pi_n^{\max(anum_n,bnum_n)}\)。
对于两个整数 \(a\) 和 \(b\)，\(lcm(a,b) \times \gcd(a,b)=a \times b\)。
对于 \(a\) 和 \(b\)：
\(a=pi_1^{anum_1} \times pi_2^{anum_2} \times \cdots \times pi_n^{anum_n}\)；
\(b=pi_1^{bnum_1} \times pi_2^{bnum_2} \times \cdots \times pi_n^{bnum_n}\)；
\(lcm=pi_1^{\min(anum_1,bnum_1)} \times pi_2^{\min(anum_2,bnum_2)} \times \cdots \times pi_n^{\min(anum_n,bnum_n)}\)；
\(lcm=pi_1^{\max(anum_1,bnum_1)} \times pi_2^{\max(anum_2,bnum_2)} \times \cdots \times pi_n^{\max(anum_n,bnum_n)}\)。
所以 \(gcd \times lcm=pi_1^{anum_1+bnum_1} \times pi_2^{anum_2+bnum_2} \times \cdots \times pi_n^{anum_n+bnum_n} = a \times b\)。
得证。
两个数求最小公倍数
原理同多个数求最大公因数。
裴蜀定理
若 \(a\)、\(b\) 为不全为 \(0\) 的整数，则存在 \(x\)、\(y\)，使得 \(ax + by = \gcd(x,y)\)。
证明：
设取整数 \(x\)、\(y\) 时，\(ax+by\) 的最小正整数为 \(s\)，即 \(ax+by=s\)
\(\because \gcd(a,b) \mid ax\)，\(\gcd(a,b) \mid by\)
\(\therefore \gcd(a,b) \mid s \cdots \cdots (1)\)
设 \(a=qs+r(q \le < s)\)
\(r=a-qs\)
\(~=a-q(ax-by)\)
\(~=a(1-qx)+b(-qy)\)
\(~=ax+by\)
因为 \(s\) 时最小正整数，所以 \(r=0\)
所以 \(s \mid a\)，同理可得 \(s \mid b\)
故 \(s \mid \gcd(a,b) \cdots \cdots (2)\)
由 \((1)(2)\) 可得，\(s=\gcd(a,b)\)
证毕
裴蜀定理更多的应用
由原定理可得：
- 一定存在整数 \(x\)、\(y\)，\(ax+by=\gcd(a,b) \times n\)
- 一定存在整数 \(X_1 \cdots X_i\)，\(\sum_{i=1}^n A_i X_i=\gcd(A_1,A_2,\cdots,A_n)\)
如果系数 \(A_i < 0\)，可以代入绝对值
扩展欧几里德
常由于求解 \(ax+by=\gcd(a,b)\) 的一组解（\(x\)、\(y\) 未知）。
\(ax_1+by_1=\gcd(a,b)\)
\(bx_2+(a\%b)y_2=\gcd(b,a\%b)\)
\(\because \gcd(a,b)=\gcd(a,a\%b)\)
\(\therefore ax_1+by_1=bx_1+(a\%b)y_2\)
\(\because a\%b=a-\lfloor \frac{a}{b} \rfloor \times b\)
\(\therefore ax_1+by_1=bx_2+(a-\lfloor \frac{a}{b} \rfloor \times)y_2=ay_2+b(x_2-\lfloor \frac{a}{b} \rfloor y_2)\)
由于系数相同，所以可以令 \(x_1=y_2\)，\(y_1=x_2-\lfloor \frac{a}{b} \rfloor y_2\)
显然，可以利用递推，先求出下一层的解 \(x_2\)、\(y_2\)，再带回上一层，最终秋初特解 \((x_1,y_1)\)。扩展欧几里德就是利用递推由外到内的求 \(\gcd\)，最后求出特解。
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int ret = exgcd(b, a % b, x, y);
int t = x, x = y, y = t - a / b * y;
return ret;
}
构造通解
考虑 \(ax+by=0\) 时构造：
\(\begin{cases}x=x_0+\frac{b}{\gcd(a,b)} \times k
\\x=y_0-\frac{a}{\gcd(a,b)} \times k
\end{cases}\)
求不定方程的一组解
- 若 \(\gcd(a,b) \mid c\)，则有整数解；
- 若 \(\gcd)a,b) \nmid c\)，则无整数解。
求解过程：
先用扩展欧几里德求出 \(ax+by=\gcd(a,b)\) 的解，再乘以 \(\frac{c}{\gcd(a,b)}\)，即得到原方程的特解 \((x_0,y_0)\)。
#include <bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int X1, Y1, d = exgcd(b, a % b, X1, Y1);
x = Y1, y = X1 - a / b * Y1;
return d;
}
int main() {
int a, b, c, x, y;
cin >> a >> b >> c;
int d = exgcd(a, b, x, y);
if (c % d == 0) cout << c / d * x << " " << c / d * y;
else cout << "none" << endl;
return 0;
}
扩展欧几里德求解线性同余方程
将同余方程转换为不定方程，由 \(ax \equiv b \pmod m\)，得 \(ax \equiv m(-y)+b\)，即 \(ax+by=b\)。
由裴蜀定理，当 \(\gcd(a,m) \mid b\) 时有解。
再用扩展欧几里德求出 \(ax+my=\gcd(a,m)\) 的解，之后把 \(x\) 乘以 \(\frac{b}{\gcd(a,m)}\)，即为原方程的特解。
时间复杂度最坏为 \(O(2 \log n)\)。
乘法逆元
乘法逆元是模意义下的乘法运算的逆元，应用比较广泛。
定义
若 \(a \times x \equiv \pmod b\)，则称 \(x\) 为 \(a\) 在模 \(b\) 意义下的乘法逆元，记作 \(a^{-1}\)。
并非所有情况都存在乘法逆元，当 \(\gcd(a,b)=1\)，即 \(a\)、\(b\) 互质时，存在乘法逆元。
用途
对于除法取模不成立，即 \((a \div b) \% p \neq ((a \% p)\div(b \% p)) \% p\)。
取模运算对乘法是成立的，逆元就是把除法取模运算转化为乘法取模运算。
所以，求 \((a \div b) \% p\) 相当于 \((a \times b^{-1}) \% p\)。
求解
费马小定理
前提：模数 \(p\) 为素数，\(a\) 不为 \(p\) 的倍数
求 \(a\) 在模 \(p\) 意义下的逆元，可以由费马小定理得出 \(a^{p-1} \equiv 1 \pmod p\)，即 \(a^{p-1} \% p = a \times a^{p-2} \% p = 1\)。
结合逆元的定义，可以得出 \(a^{p-2} \% p\) 就是 \(a\) 在模 \(p\) 意义下的逆元。可以用快速幂求解。
#define ll long long
ll qpow(ll a, ll n, ll p) {
ll ans = 1;
while (n) {
if (n & 1) ans = ans * a % p;
a = a * a % p;
n >>= 1;
}
return ans;
}
ll mmi(ll a, ll p) {
return qpow(a, p - 2, p);
}
欧拉定理
\(p\) 可以不为素数
有欧拉定理可得，\(\gcd(a,p) = 1\)，则 \(a^{\varphi(p)}=1 \pmod p\)。所以可以得出，\(a^{\varphi(p-1)}\) 即为 \(a\) 在模 \(p\) 意义下的逆元。时间复杂度为 \(O(\sqrt{p} + \log p)\)。
int inv(int a, int p) {
int phi = p, mod = p, res, t;
for (int i = 2; i <= p; i++) {
if (p % i == 0) {
phi = phi / i * (i - 1);
while (p % i == 0) p /= i;
}
}
if (p > 1) phi = phi / p * (p - 1);
phi--;
while (phi) {
if (phi & 1) res = res * t % mod;
t = t * t % mod, phi >>= 1;
}
return res;
}
扩展欧几里德
前提：\(\gcd(a,b)\)
设 \(a \times x \equiv 1 \pmod b\)则可以得出 \(a \times x = b \times y + 1\)，即 \(a \times x - b \times y = 1\)。由于 \(y\) 是商，可以得出 \(a \times x + b \times y = 1\)，就可以用扩展欧几里德求解了。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll y, p;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll ans = exgcd(b, a % b, x, y), t = x;
x = y, y = t - (a / b) * y;
return ans;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%lld%lld", &y, &p);
ll x = 0, k = 0, sum = exgcd(y, p, x, k);
if (sum == 1) printf("%lld\n", (x % p + p) % p);
else printf("-1\n");
}
return 0;
}