基础数论

cloud2764scallop_eve · 2023-10-08 16:57:14 · 算法·理论

转载

同余

定义

若 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。 由概念易得：

1. 若 a \equiv b \pmod m，则定有 \sqsupseteq k,l,c \in \mathbb{Z},a = km + c,b = lm + c；
2. 若 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 的自然数，不能被其它自然数整除的数叫做素数（质数），反之，不是素数的数被称为和数。

• 素数的个数是无限的。

  假设素数的个数是有限的，那么可以将所有素数表示为 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 的正整数一定能被唯一分解为有限个素数的乘积，如下：

其中 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. 枚举已记录的素数（如果合数已越界则中断）
   (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; 用于控制每个合数只被筛掉一次。

欧拉函数

定义

对于正整数 n，其欧拉函数是指小于等于 n 的数中与 n 互质的数的个数，用字母 \varphi 表示。
通项公式：

其中 p_1,p_2,\cdots,p_k 为 n 的所有质因数，n 为正整数。

利用通项公式计算如下： $\varphi(12) = 12 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 4

解释：12 的质因子 2,3。

性质

2. 若 p 为一个素数，则 \varphi(p) = p - 1。
3. 若 p 为一个素数，则 \varphi(p^k) = (p - 1) \times p^{k - 1}。
4. 欧拉函数为积性函数：对于任意两个正整数 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)。

欧拉函数性质变形

1. >$n \times p$ 的素因子和 $n$ 是一样的，所以利用欧拉函数公式把 $\varphi(n \times p)$ 展开即可。（本条变形一些资料都要求 $p$ 为素数，实际上 $p$ 不为素数依旧成立，~~我不会证~~，这里不给详细的证明了。）
2. >$p$ 为素数，$n \% p \neq 0$，所以 $n$ 和 $p$ 互质，满足积性函数。
3. 当 n 为奇数时，\varphi(2n) = \varphi(n)。
4. 与 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，积性函数）

欧拉函数仅由 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 筛掉。

1. 若 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)

2. 若 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 选择。

$num_i$：$i$ 是素数，自小质因子就是自己，个数是 $1$。

i 和枚举的第 j 个指数取模为 0 ，即 i % prime[j] == 0

找出二者之间的地推关系，很明显，就是一式除以 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，即为：

i \% 枚举的素数 prime_j 不为 0，即 prime_j 不能整除 i

以下讨论中将使用 p_j 代指 prime_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}：

>因为质因子从小到大枚举，那么 $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_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，有 n 个不同的剩余类中各取出一个元素，共 n 个数，将这些数构成一个全新的集合，则称这个集合为模 n 的完全剩余系。

简化剩余系

给定一个正整数 n，有 \varphi(n) 个不同的模 n 的余数 r 和 b 互质的剩余类，从这 \varphi(n) 个剩余类中各取出一个元素，共 \varphi(n) 个数，将这些数构成一个新的集合，称为模 n 的简化剩余系。

显然，模 $n$ 的简化剩余系中的所有书都与 $n$ 互质。

欧拉定理

模的 m 可以为合数。
若 \gcd(a,m) = 1,则 a^{\varphi(m)} \equiv 1 \pmod m。
特别的，当 m 为素数时，与费马小定理一致。

$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

设 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。

由以上性质证明中的 a^{p - 1} \times f \equiv f \pmod p，又因为 \gcd(f,p) = 1，所以 a^{p - 1} \equiv 1 \pmod p。得证。

扩展欧拉定理

当 b 较小时，不用降幂，直接跑快速幂；
当 b 较大时，先用扩展欧拉定理降为小数，再跑快速幂。

$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 与 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 和 b，lcm(a,b) \times \gcd(a,b)=a \times b。

对于 a 和 b：

$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)
证毕

裴蜀定理更多的应用

由原定理可得：

1. 一定存在整数 x、y，ax+by=\gcd(a,b) \times n
2. 一定存在整数 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 时构造：

求不定方程的一组解

1. 若 \gcd(a,b) \mid c，则有整数解；
2. 若 \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);
}

欧拉定理

有欧拉定理可得，\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;
}