质数

质数 ( 素数 ) 的定义：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数

试除法判定质数

• 第一重境界：

时间复杂度：$\mathcal O(n)$

bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i < n ; i ++)
        if(n % i == 0)
            return false;
    return true;
}

原理： 枚举$2 \sim (n-1)$的所有数，如果有n的因数 ( n % i == 0 )，说明n不是质数，否则n是质数

• 第二重境界：

时间复杂度：$\mathcal O(\sqrt n)$ ( 一定会循环 $\sqrt n$ 次，即时间复杂度妥妥 $\mathcal O(\sqrt n)$ )

bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i <= n / i ; i ++)  // 注意这里是 <= 不是 < ( 需要枚举所有小因数 )
        if(n % i == 0)
            return false;
    return true;
}

原理：质数都是成对出现的，每次只需要枚举较小的一个因数即可
证明：若 $d \mid n$，则 $\dfrac nd \mid n$ (若 $d$ 能整除 $n$，则 $\dfrac nd$ 也能整除 $n$ )，则由：
$$d \leq \frac nd \implies d \leq \sqrt n$$
故 $d$ 只需要枚举到 $\sqrt n$ 即可

==注意==：
不建议写：i <= sqrt(i) 或者i * i <= n
1.sqrt()函数调用速度慢
2.i * i有溢出风险

分解质因数

算术基本定理：任何一个大于1的正整数都能分解为有限个质数的幂的乘积 ：$N = p_1^{c_1}\cdot p_2^{c_2}\cdots p_m^{c_m}$ 其中都是 $c_i$ 正整数，$p_i$ 都是质数，且满足 $p_1 < p_2 < \cdots <p_m$

$n$ 的所有正约数集合$\{ p_i^{b_i}\}$，其中$0 \le b_i \le c_i$

原理：试除法
枚举 $2 \sim n$ 中的所有质数，如果是i的n的因子，就把n中的i因子除干净

平均时间复杂度：$\mathcal O(n)$

for(int i = 2; i <= n ; i ++)
        if(n % i == 0)
        {
            int s = 0;
            while(n % i == 0)
            {
                n /= i;
                s ++;
            }
            printf("%d %d\n",i, s);  // s 就是质因数 i 的次数
        }

其中枚举的i一定是质数：

原因：
当枚举到i的时候，已经把2 ~ (i - 1)中的质因子都除掉了，当if(n % i == 0)成立的时候，n中已经不包含任何2 ~ (i - 1)的质因子，又因为n是i的倍数，所以i中也不包含2 ~ (i - 1)的因子，所以此时i一定是质数
另一种证明： 一个数除了1之外的最小因数一定是质数 ( 反证法：假设最小因数是合数，那么这个合数的因数也一定是原本这个数的因数，那么原来这个因数就不是最小因数，矛盾 )，由于是从小到大枚举所有的因数i，且如果i是n的因数的话就把i除干净，所以每次枚举的i都是n的最小因数，因此i就是质数
反证法证明： 如果此时i是合数的话，i就可以分解成有限个质数的幂的乘积，而这些质数一定比i小且都是n的因数，但是比i小的因子在之前就应该被除干净了，矛盾，所以i一定是质数
- 优化
原理：
n中最多只包含一个大于 $\sqrt n$ 的质因子
反证法：
如果有两个，那么乘积就> n矛盾

平均时间复杂度：$\mathcal O(\sqrt n)$ ( 不一定循环 $\sqrt n$ 次，当n是2的n次幂的时候，时间复杂度最低：$\mathcal O(\log_2n)$，枚举的第一个数2会直接把n除干净 )

void divisors(int n)
{
    for(int i = 2; i <= n / i ; i ++)
        if(n % i == 0)
        {
            int s = 0;
            while(n % i == 0)
            {
                n /= i;
                s ++;
            }
            printf("%d %d\n",i, s);
        }
    if(n > 1) printf("%d %d\n",n, 1); // 单独处理
}

筛质数

用途： 求 $1\sim n$ 中包含的 $\color{red}所有的$ 质数

朴素筛

• 朴素筛

  原理： 从2 ~ n枚举每一个数字，并把当前数字所有的倍数都删掉，剩下数就都是质数

  证明： 对于某一个没有被删掉的数 $p_i$，就等价于 $2\sim (p_i-1)$ 中的任何一个数都没有把 $p_i$ 删掉，说明 $p_i$ 不是$2\backsim(p_i-1)$ 中的任何一个数的倍数，也就等价于 $2\backsim(p_i-1)$ 中不存在 $p_i$ 的因数，也就是说 $p_i$ 就是质数

void get_primes(int n)
{
    for(int i = 2; i <= n ; i ++)
    {
        if(!st[i]) // st[] 存储每一个数是否被筛过  ( 先存在筛：边界问题 第一个数是 2 是质数 )
        {
            primes[cnt ++] = i;
        }
        for(int j = i + i ; j <= n ; j += i) st[j] = true;
    }
} // 循环结束后 primes[] 中就存有所有的质数

时间复杂度分析：
当i == 2的时候内层循环循环了 $\dfrac n2$ 次，i == 3循环了 $\dfrac n3$ 次
同理，循环的总次数就是：
$$\frac n2+\frac n3+\frac n4+···+\frac nn$$
等价于：
$$n \times (\frac 12+\frac13+\frac 14+\cdots+\frac 1n)$$
根据调和级数：
$$\lim_{n \to \infty}(1+\frac12 + \frac13 +···+\frac1n) = \ln n + c$$
那么结果是：
$$n×(\ln n + c- 1)$$

==调和级数部分和==：其中 $c$ 是欧拉常数 $\approx 0.577\cdots$
那么循环次数就是$n \times (\ln n+c - 1) < n \times \ln n < n \times \log_2n$
所以时间复杂度：$\mathcal O(n \log n)$

埃氏筛

• 埃氏筛

埃氏筛是朴素筛的优化
不难发现，并不需要把2 ~ n的所有倍数删掉，只需要把其中的质数的倍数删掉即可

证明：
根据算术基本定理：每一个大于1的正整数都能分解成有限个质数的幂的乘积，且由于是从小到大枚举，在枚举到某个合数之前，一定先会枚举到它的质因数，所以说所有的合数都会被筛掉

void get_primes(int n)
{
    for(int i = 2; i <= n ; i ++)
    {
        if(!st[i])
        {
            primes[cnt ++] = i;
            for(int j = i + i ; j <= n ; j += i) st[j] = true; // 循环直接放到判断里
        }
    }
}

时间复杂度分析：
粗略估算：

质数定理：对于一个足够大的整数 $N$，不超过 $N$ 的质数大约有$\dfrac {n}{\ln n}$ 个，即每 $\ln N$ 个数中大约有1个质数

$$n \times \ln n \times \frac 1{\ln n} = n$$

真实时间复杂度：$\mathcal O(n \log \log n)$ ( 已经非常接近 $\mathcal O(n)$ )
相当于调和级数中只算了分母为质数的部分
$$\lim_{n \to \infty}(\frac 12 + \frac 13 + \frac 15 + \frac 17 + \cdots ) = \log \log n$$

欧拉筛 ( 线性筛 )

• 欧拉筛(线性筛)

顾名思义：线性筛的时间复杂度是 $\mathcal O(n)$
欧拉筛保证了每个数都由其最小质因子筛掉

void get_primes(int n)
{
    for(int i = 2; i <= n ; i ++)
    {
        if(!st[i]) primes[cnt ++ ] = i;
        for(int j = 0; primes[j] <= n / i ; j ++)
        {
            st[primes[j] * i] = true;  // 每次都是筛掉 当前枚举的质数primes[j] 和 i 的乘积
            if(i % primes[j] == 0) break; // 这句话成立的时候 pirmes[j] 一定是 i 的最小质因子
            // 这句话无论成不成立 primes[j] 一定都是 primes[j] * i 的最小质因子 
        }
    }
}

• 1.线性筛是如何保证每一个合数只会被其最小质因子筛掉
  (1) 当i % pj == 0的时候，pj是i的最小质因子( 因为 pj是从小到大枚举的所有质数，且此前没有发生过i % pj == 0，所以，当第一次出现i % pj == 0的时候，pj 就是i的最小质因子 ) 那么 pj 就是pj * i的最小质因子
  (2) 当i % pj != 0的时候 ，因为pj是从小到大枚举primes中的所有质数，并且此前没有发生过i % pj == 0 ( 即还没有枚举到i的任何一个质因子 )，所以pj 一定小于i的所有质因子，所以pj 仍然是 pj * i的最小质因子

总结思路：如果质数n <= m的最小质因数，那么质数n就是n * m 的最小质因数

所以上一步就把pj * i 筛掉 且下一步立马break( 防止重复筛：因为下一个pj一定比当前的pj要大,但是i的最小质因子是当前的pj，那么即便再往后枚举pj，pj再也不可能成为pj * i的最小质因子了，可见，再枚举也是多余。且此时如果i是质数，pj枚举到== i的时候 ( 此时刚好j == cnt ) 如果没有break，j继续++ ，此时primes数组就越界了 )

• 2.每一个合数x都一定能被筛掉
  ( 首先已经保证了pj是pj * i的最小质因子 )
  对于任意一个合数x，一定存在一个最小质因子，假设pj 是 x的最小质因子，当i枚举到x之前一定会枚举到 x / pj ，此时x就能被筛掉
  又因为每个合数都只有一个最小质因子，所以每个数只会被筛一次，所以线性筛是线性的

• 3.为什么不用写 j < cnt
  ==注意==：primes[] 当中存有所有<= i 的所有质数，且如果当前i是质数的话，primes[]中最后一个质数就是i
  (1) 当i是合数的时候 当pj枚举到i的最小质因子的时候break ( i的最小质因子一定 < i本身，且一定已经存在primes[]里了 ) ( 唯一分解定理 ) , 此时j不会越界。
  (2) 当i是质数的时候，primes中的最后一个质数就是当前的i( i已经加到primes里了 )，当pj枚举到 == i的时候 break ，j此时刚好== cnt - 1，也刚好不会越界。
  ( i如果是合数的话 pj是i的最小质因子 当i是质数的话 pj == i的时候 break pj仍然是i的最小质因子 )

线性筛的思想很重要，在线性筛的代码模板中额外维护一些参数就可以求出很多东西，比如求欧拉函数 ( 后面有讲解 )

线性筛法的常数比较大，一般数据范围比较庞大的时候，才会使用线性筛

当数据范围达到 $10^7$ 时，线性筛的效率比埃氏筛快一倍，$< 10^6$ 两种筛法时间效率差不多

Lanqiao Cup 例题：最小质因数

题目简述：定义F[i]表示整数i的最小质因子，给定一个整数n，求 $\sum\limits_2^n F(i)$

数据范围：$1 \le T \le 10^6,\ 2 \le N \le 3 \times 10^6$

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1000010;

typedef long long LL;

int primes[N], cnt, n;
bool st[N];

LL init(int n)
{
    LL sum = 0;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            sum += i;
            // cout << i << ' ' << endl; // 质数的最小质因子就是本身
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            sum += primes[j];
            // cout << primes[j] << ' ' << primes[j] * i << endl; // primes[j] 就是 primes[j] * i 的最小质因子
            if (i % primes[j] == 0) break;
        }
    }
    return sum;
}

int main()
{
    cin >> n;
    LL t = init(n);
    printf("%lld\n", t);
    return 0;
}

时间复杂度：
$$10^5 \times 3 \times 10^6 = 3 \times 10^{11}$$
但是官方给的此题的知识点是埃氏筛 ？

此题应该可以优化到：
$$3 \times 10^6$$
即只需要先读入所有数据，当计算到某个读入数据的时候输出即可，枚举的n的上界就是读入数据中最大的一个

约数

试除法求约数

vector<int> get_divisors(int n)
{
    vector<int> res;
    for(int i = 1; i <= n / i ; i ++) // 只枚举较小的约数 较大的约数直接计算 ( 注意从 1 开始枚举 )
        if(n % i == 0)
        {
            res.push_back(i);
            if(i != n / i) res.push_back(n / i); // 特判 i 的平方 == n 的情况 ( 此时只能加一个 i )
        }
    sort(res.begin(), res.end());
    return res;
}

==注意==： 1 是任意正整数的约数
时间复杂度分析：
1 ~ n中所有约数的个数：$n+ \dfrac n2+\dfrac n3+\cdots +\dfrac nn = n(\ln n + c) \approx n \ln n \approx n \log _2 n$ ( $1 \sim n$ 当中约数的个数 $=$ $1\sim n$ 当中倍数的个数 )
所以每个数的约数个数平均是： $\dfrac {n \log _2 n}{n} = \log _2 n$
所以：sort的时间复杂度：$\log n \log \log n \approx \log n$，for循环的时间复杂度：$\sqrt n$
由于 $\log n < \sqrt n$
所以时间复杂度：$\mathcal O(\sqrt n)$

int范围内：约数最多的数其约数有 $1536$ 个

约数个数

时间复杂度： $\mathcal O(n \sqrt n)$

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7; // 取模防止结果太大溢出
int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes; //存每一个质因数和它对应的指数 ( 次数 ) 
    while(n --)
    {
        int a;
        cin >> a;
        for(int i = 2; i <= a / i; i ++)
            while(a % i == 0)
            {
                a /= i;
                primes[i]++;
            }
        if(a > 1) primes[a]++;
    }
    LL res = 1; // res 当基数
    for(auto t : primes) res = res * (t.second + 1) % mod;
    cout << res << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>

using namespace std;

const int mod = 1e9 + 7;

typedef pair<int, int> PII;

int n;

int main()
{
    cin >> n;
    unordered_map<int, int> primes;
    while (n -- )
    {
        int a;
        cin >> a;
        for (int i = 2; i <= a / i; i ++ )
            while (a % i == 0)
            {
                a /= i;
                primes[i] ++;
            }
        if (a > 1) primes[a] ++;
    }

    int res = 1;
    for (PII t : primes) res = 1ll * res * (t.second + 1) % mod;  // hash表 ：键值对本质就是 pair

    printf("%d\n", res);
    return 0;
}

求约数个数和约数之和基于算术基本定理，在算术基本定理中，若正整数 $N$ 被唯一分解为 $N = p_1^{c_1}p_2^{c_2}···p_m^{c_m}$ 其中 $c_i$ 都是正整数，$p_i$ 都是质数
那么N的正约数的个数为：
$$(c_1 + 1) \times (c_2 + 1)\times \cdots \times(c_m + 1) = \prod_{i=1}^m(c_i + 1)$$
N的正约数的和为：
$$(1 + p_1+p_1^2+ \cdots +p_1^{c_1})\times \cdots \times (1 + p_m + p_m^2 + \cdots +p_m^{c_m}) = \prod_{i=1}^m \left( \sum_{j=0}^{c_i}(p_i)^j \right)$$
证明：

• 约数个数
  分解完质因数之后，对于N的正约数集合 $\begin{Bmatrix} P_{1-m}^{C_{1-m}}\end{Bmatrix}$ 的每一个 $P$ 其次方的 $0 - C_i$ 的选法 ( 共$C_i + 1$种 ) 都对应一个约数，对于每一个 $P_i$ 都有 $C_i + 1$ 种选法，根据乘法原理共有 $(c_1 + 1) \times (c_2 + 1)\times \cdots\times(c_n + 1)$ 种
• 约数之和
  将 $(1 + p_1+p_1^2+···+p_1^{c_1})\times \cdots \times(1 + p_m + p_m^2 + \cdots +p_m^{c_m})$ 展开，等价于在每个括号中选一个数累乘，每个累乘的结果都是N的因数，总项数就等于总因数个数，那么结果就是所有因数的和，即约数之和

百度证明：

约数个数定理
约数和定理

约数之和

时间复杂度： $\mathcal O(n \sqrt n)$

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int mod = 1e9 + 7; 
typedef long long LL;
int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while(n --)
    {
        int a;
        cin >> a;
        for(int i = 2 ; i <= a / i ; i ++)
        while(a % i == 0)
        {
            a /= i;
            primes[i]++;
        }
        if(a > 1)   primes[a]++;
    }
    LL res = 1; // res 当基数
    for(auto prime : primes)
    {
        int p = prime.first , a = prime.second;
        LL t = 1;
        while (a -- ) t = (t * p + 1) % mod; // 求等比数列的和 时间复杂度：O(n)
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

• 小知识点：分治法求等比数列的和
  时间复杂度可以优化到 $\mathcal O(\log n)$

但是代码比较复杂，如果不是算法瓶颈一般不优化

最大公约数

最大公约数定义：即是a的约数也是b的约数且最大

欧几里得算法

欧几里得算法也叫辗转相除法

• 核心原理： $$\forall a,b \in N, b \neq 0, \quad {\rm gcd}(a, b) = {\rm gcd}(b, a \bmod b)$$

理论基础：如果 $d \mid a$ 且 $d \mid b$ (d能整除a和b)，那么 $d \mid (a + b)$ 且 $d \mid (x\times a +y\times b)$ ( 显而易见的，这里不再证明 )
- 证明：$a \bmod b = a - \lfloor \dfrac ab \rfloor · b = a - c·b$
即证：${\rm gcd}(a, \ b) = {\rm gcd}(b, \ a - c\times b)$
对于任意a，b的公因数d, $d \mid a$, 且 $d \mid b,$ 同时 $d \mid (a - c·b)$，因此 $d$ 也是 $b$ 和 $a - c·b$ 的公因数，反之，如果$d\mid b$ ,且 $d\ mid (a - c·b)$ 那么 $d$ 也能整除 $(a - c·b + c·b)$ 即 $d \mid a$，故 $a,b$ 的公因数集合与 $b, a \bmod b$ 的公因数集合相同，于是他们的 最大公因数 也相同

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a ; // b == 0 返回 a ( 0 能整除任何数 )   b != 0  返回 gcd(b, a % b)
}

int gcd(int a, int b) // 一行代码展开
{
    if(!b) return a;
    return gcd(b, a % b);
}

int gcd(int a, int b)  // 迭代写法
{
    while(b)
    {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

互质与欧拉函数

互质：$\forall a,b \in N$, 若 ${\rm gcd}(a, b) = 1$，则称 $a,b$ 互质

欧拉函数：$1\backsim N$ 中与 $N$ 互质的数的个数，记作 $\phi(N)$
若在算术基本定理中：$N = p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$ 则：
$$\phi(N) = N \times \dfrac {p_1 - 1}{p_1}\times \dfrac {p_2 - 1}{p_2}\times \cdots \times\dfrac {p_m - 1}{p_m} = N \times \prod_\limits{质数p \mid N}(1 - \dfrac 1p)$$
欧拉函数的结果与质因子的次数 ($c_i$ ) 无关

证明： 对于 $N$ 的某个质因子 $p_i$，它的所有倍数都与 $N$ 不互质( 都至少有 $p_i$ 这个因子 )，因此只要去掉 $1\backsim N$ 当中所有 $N$ 的质因子的倍数，剩下的数就是与 $N$ 互质的数

那么如何去掉$1\backsim N$当中所有$N$的质数的倍数？
容斥原理： 若 $p$ 是 $N$ 的质因子，则 $1\backsim N$ 当中 $p$ 的倍数有:
$$p,2p,3p ,···, \lfloor \frac Np \rfloor × p，共\lfloor \frac Np \rfloor 个$$
同理，若 $q$ 也是 $N$ 的质因子，则 $1\backsim N$ 中 $q$ 的倍数有 $\lfloor \frac Nq \rfloor$ 个，都去掉的话，那么 $p \times q$ 的倍数就被排除了两次，需要加回来一次，因此 $1\backsim N$ 中不与 $N$ 含有共同质因子 $p$ 或 $q$ 的数的个数为：
$$N - \dfrac Np - \dfrac Nq + \dfrac N{pq} = N \times (1 - \dfrac 1p - \dfrac 1q + \dfrac 1{pq}) = N(1 - \dfrac 1p)(1- \dfrac 1q)$$
同理，如果去掉 $N$ 的所有质因数的倍数，也就是 $1\backsim N$ 中剩下的数都是不与 $N$ 含有 $N$ 的所有共同质因子的数，那么剩下的数就是与 $N$ 互质的数

定义式求欧拉函数

时间复杂度： $\mathcal O(\sqrt n)$
根据欧拉函数的计算式，在分解质因数的同时就可以顺便求出欧拉函数：

int phi(int n)  // 返回某个数的欧拉函数
{
    int res = n;
    for(int i = 2; i <= n / i ; i ++)
        if(n % i == 0)
        {
            res = res / i * (i - 1); // 先除 防止爆范围
            while(n % i == 0) n /= i;
        }
    if(n > 1) res = res / n * (n - 1);
    return res;
}

线性筛法求欧拉函数

有时候需要求出 $1\backsim n$ 当中每一个数的欧拉函数，如果用定义法求，时间复杂度：$\mathcal O(n \sqrt n)$，借助线性筛法可以在 $\mathcal O(n)$ 的时间复杂度之内顺便求出欧拉函数

• 线性筛法求 $1\backsim n$ 中每个数欧拉函数

LL get_eulers(int n) // 返回1 - n 中的所有数的欧拉函数的和
{
    phi[1] = 1;
    for(int i = 2; i <= n ; i ++)
    {
        if(!st[i])
        {  
             primes[cnt ++] = i;
             phi[i] = i - 1;  // 质数 i 的欧拉函数：i - 1
        }
        for(int j = 0 ; primes[j] <= n / i ; j ++)
        {
            st[primes[j] * i] = true; 
            if(i % primes[j] == 0)
            {
                phi[primes[j] * i] = primes[j] * phi[i]; // pj 是 i 的质因子
                break;
            }
            phi[primes[j] * i] = (primes[j] - 1) * phi[i];// pj 不是 i 的质因子  ( 注意这句与上一句代码的顺序！！ )
        }
    }
    LL ret = 0;
    for(int i = 1; i <= n ; i ++) ret += phi[i]; // 累加 1 ~ n 的每个数的欧拉函数
    return ret;
}

其中：

$$\phi(primes[j] ×i)= \begin{cases} \phi(i)\times primes[j] & {(i\ \% \ primes[j] == 0)} \\ \\ \phi(i)\times primes[j]\times(1 - \frac {1}{primes[j]}) = \phi(i)\times(primes[j] - 1) & {(i \ \% \ primes[j]\; != 0)} \end{cases}$$

此题与Lanqiao Cup：最小质因数那题比较像，都需要推公式，找规律

注意线性筛的细节：

1. primes[j]是每一个被筛除的数的最小质因子 ( 题目有有可能针对primes[j]出题 )
2. 以及注意 $2 \sim n$ 中的数具体在哪里出现以及出现的次数 ( 都是1次 )

同余

定义：若$a \bmod m = b \bmod m$，则称a, b模m同余，记作：
$$a \equiv b \ (\bmod m)$$

欧拉定理

欧拉定理： 若正整数 $a,n$ 互质，则有 $$a^{\phi (n)} \equiv 1(\bmod n)$$
其中 $\phi (n)$ 为欧拉函数

证明： 假设 $1\backsim n$ 中所有与 $n$ 互质的数的集合为：$\lbrace a_1, a_2,···,a_{\phi (n)}\rbrace$ $(a_{1\backsim\phi (n)})$两两不相同
由于$a,n$互质，$\lbrace aa_1, aa_2,···,aa_{\phi n}\rbrace$也都是与 $n$ 互质的，且两两不同 ( 反证法：若$aa_i \equiv aa_j(\bmod n)$，则$a(a_i-a_j) \equiv0$，则$a_i \equiv a_j$，矛盾 ) ( 若 $a$ 和 $n$ 互质，$b$ 也和 $n$ 互质，则 $ab$ 与 $n$ 也互质 ) ( 且 $a_1a_2···a_{\phi (n)}$ 的结果也与 $n$ 互质 )，则有：
$$(aa_1)(aa_2)···(aa_{\phi (n)}) \equiv a^{\phi (n)} a_1a_2···a_{\phi(n)} \equiv a_1a_2···a_{\phi (n)} (\bmod n) \\ \\ \Longrightarrow a^{\phi (n)} \equiv 1(\bmod n)\\ $$

若 $n$ 为质数$\Longrightarrow \phi (n) = n - 1 \Longrightarrow a^{n - 1} \equiv1(\bmod n)$ ( 费马小定理 )

欧拉定理

欧拉定理推论

快速幂：快速求 $a^k \bmod p$

应用：在 $\mathcal O(\log k)$ 的时间复杂度内求出 $a^k \bmod p$ 的结果
其中$1 \leq a,p,k \leq 10^9$

• 朴素做法：时间复杂度：$\mathcal O(k)$

int res = 1;
for(int i = 1; i <= k ; i ++)
    res = (LL)res * a % p;

• 快速幂

  原理：反复平方法：
  预处理出：$a^{2^0} \bmod p$ ，$a^{2^1} \bmod p$，$a^{2^2} \bmod p$，···，$a^{2^{\log _2k}} \bmod p$，共 $\log k$ 个数，将 $a^k$ 拆成若干个$a^{2^{0 \sim \log _2k}}$的乘积的形式，其中 $2^{0\backsim\log _2k}$ 对应k的二进制表达式，也就是说，将k的二进制表达式对应是1的位数的权重累加起来即可
  其中 $a^{2^{\log _2 k}} = (a^{2^{\log _2 k -1}})^2 \qquad (a^{2^{\log _2 k - 1} \times 2}$)

int qmi(int a, int k, int p) // 返回a^k % p 的结果
{
    int ret = 1; // 基数
    while(k)
    {
        if(k & 1) ret = (LL)ret * a % p;
        k >>= 1;
        a = (LL)a * a % p; // 平方
    }
    return ret;
}

int qmi(int a, int k, int p)
{
    int res = 1;
    for (; k; k >>= 1)
    {
        if (k & 1) res = 1ll * res * a % p;
        a = 1ll * a * a % p;
    }
    return res;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100010;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = 1ll * res * a % p;
        k >>= 1;
        a = 1ll * a * a % p;
    }
    return res;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        cout << qmi(a, k, p) << endl;
    }
    return 0;
}

快速幂也叫龟速乘：乘法计算乘方

同时还有龟速加：加法计算乘法

快速幂求逆元：费马小定理

乘法逆元： 若整数 $b,m$ 互质，并且$b\mid a$，则存在一个整数 $x$，使得：$\dfrac ab \equiv a \times x (\bmod m)$( 将除法转化为乘法 )，称 $x$ 是 $b$ 的模 $m$ 乘法逆元，记作 $b^{-1}(\bmod m)$

性质：
$$\frac ab \equiv a \times b^{-1}\Longrightarrow \frac ab \times b \equiv a \times b^{-1}\times b (\bmod m) \Longrightarrow b \times b^{-1} \equiv 1(\bmod m) \quad (其中b,m互质)$$
所以对于任意整数 $b$，若 $x$ 满足 $b \times x \equiv 1(\bmod m)$，那么 $x$ 就是 $b$ 的逆元
其中：若 $m$ 为质数，根据费马小定理 $b^{m - 1} \equiv1(\bmod m) \Longrightarrow b \times b^{m-2} \equiv1(\bmod m)$ ，则 $b^{p -2}$ 就是 $b$ 的逆元，若 $b$ 是 $m$ 的倍数 ( $b,m$ 不互质 )，则 $b \bmod m = 0$ ，无解，反之，如果 $b$ 不是 $m$ 的倍数，因为 $m$ 是质数，所以 $b,m$ 一定互质，那么，根据费马小定理，一定存在 $b$ 的逆元

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
    int ret = 1;
    while(k)
    {
        if(k & 1) ret = (LL)ret * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return ret;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n --)
    {
        int a, p;
        scanf("%d%d",&a, &p);
        //int res = qmi(a, p - 2, p);
        //判断条件不能直接写 if(ret)/ // 因为 p = 2 时 需要特判  p - 2  == 0  相当于 a ^ 0   == 1   (p == 2 ： p 此时也是质数 )
        if(a % p) printf("%d\n",qmi(a, p - 2 , p)); 
        else printf("impossible\n");
    }
    return 0;
}

拓展欧几里得算法：求解：$\frac ab \equiv a \times x (\bmod m)$：$m$ 非质数一般形式

裴蜀定理

裴蜀定理： 对于任意正整数 $a,b$，那么一定存在非零整数 $x,y$，满足$ax+by = {\rm gcd}(a, b)$，拓展欧几里得算法就是一种构造出系数 $x,y$ 的算法，在欧几里得算法递归的过程中，顺便求出系数$x,y$

若存在 $ax + by = d$，那么 $d$ 一定是 ${\rm gcd}(a, b)$的倍数 ( $a$是 ${\rm gcd}$ 的倍数，$b$ 也是 ${\rm gcd}$ 的倍数，那么各自乘一个系数相加也一定是 ${\rm gcd}$ 的倍数)，那么 ${\rm gcd}(a, b)$ 就是 $a,b$ 能凑出来的最小的整数

证明： 对欧几里得算法的递归过程应用数学归纳法：
当 $b = 0$ 时：
$ax + by ={\rm gcd}(a, b)$ ，易得$x = 1, y = 0$作为一组特解，$({\rm gcd}(a, 0) = a)$
当 $b > 0$ 时：
由于：
$$ax + by = {\rm gcd}(a, b) = {\rm gcd}(b, a \bmod b)$$
而
$$bx’ + (a \bmod b)y’ = {\rm gcd}(b, a \bmod b)$$
即：
$$bx’ + (a - \lfloor \frac ab \rfloor b)y’ = {\rm gcd}(a, b)$$
即：
$$ay’ + b(x’ - \lfloor \frac ab \rfloor y’) = ax + by$$
将 $x’$ 和 $y’$ 系数互换
$$ax’ + b(y’ - \lfloor \frac ab \rfloor x’) = ax + by$$
所以递归回溯的时候可知，
$$x = x’, y = y’ - \lfloor \frac ab \rfloor x’$$
所以可以在递归回溯的过程中翻转系数 $x,y$

y总证明的时候其实先翻转了 $x’$ 和 $y’$
即：
$$by’ + (a \bmod b)x’ = {\rm gcd}(b, a \bmod b)$$
即：
$$by’ + (a - \lfloor \frac ab \rfloor b)x’ = {\rm gcd}(a, b) = ax + by$$
即：
$$ax’ + b(y’ - \lfloor \frac ab \rfloor x’) = ax + by$$
由此可得：
$$x = x’, y = y’ - \lfloor \frac ab \rfloor x’$$

#include<iostream>
using namespace std;

int exgcd(int a, int b, int &x, int &y)  // 引用传参x, y  
{
    if(!b)
    {
        x = 1, y = 0; 
        return a;
    }
    int d = exgcd(b , a % b , y , x);   // 翻转 x, y

    y -= a / b * x; // 递归回溯的时候 系数的变化
    return d;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n --)
    {
        int a,b,x,y;
        scanf("%d%d", &a, &b);

        exgcd(a, b, x, y); 

        printf("%d %d\n", x, y);
    }
    return 0;
}

线性同余方程

• 拓展欧几里得算法的应用

拓展欧几里得算法的解：
对于更一般的方程$ax + by = c$，它有解当且仅当$d|c$($c$是$d$的倍数)，所以就可以先求出$ax + by = d$的一组特解$x_0,y_0$,即$ax_0 + by_0 = d$，然后方程两边同时乘上$\dfrac cd$，就得到了$ax + by = c$的一组特解$\dfrac cd x_0, \dfrac cd y_0$

$ax + by = c$的通解的求法:
构造：
$$ax + by = d \Longrightarrow a(x - \frac bd) + b(y + \frac ad) = d$$
所以说只要能求出 $ax + by = d$ 的一组特解，那么就可以求出通解
$$\begin{cases} x = x_0 - \dfrac bd \times k \\ \\ y = y_0 + \dfrac ad \times k \\ \end{cases}$$
其中 $k$ 取遍整数集合，且 $x$ 和 $y$ 可以对调一下 ( $x,y$ 地位等价)

if(b % d) puts("impossible");   // 只有 gcd(a, b) | b的时候 才有解  否则无解
else printf("%d\n", (LL)x * b / d % m);  // 求的都是 最后结果 == gcd 对应的系数  需要扩大到对应的倍数

中国剩余定理：求解线性同余方程组

设 $m_1, m_2, ···, m_k$ 是两两互质的整数，设 $m = \prod\limits_{i = 1}^k m_i$，$M_i = \dfrac m{m_i}$，由于所有的 $m_i$ 之间两两互质，即 $M_i$ 与 $m_i$ 互质，所以 $M_i$ 模 $m_i$ 的逆元是存在的 ( 只要互质就存在 ) ，用 $M_i^{-1}$ 表示 $M_i$ 的模 $m_i$ 逆元
那么：对于任意的n个整数 $a_1, a_2, ···,a_n$ ，方程组
$$\begin{cases} x \equiv a_1(\bmod m_1) \\ \\ x \equiv a_2(\bmod m_2) \\ \\ ··· \\ \\ x \equiv a_n(\bmod m_n) \\ \end{cases}$$
有整数解，解为 $x = \sum\limits_{i = 1}^n a_iM_iM_i^{-1}$
其中求解 $M_i^{-1}$ 就是求解线性同余方程 $M_ix \equiv 1(\bmod m_i)$ 的一个解，由于 $m_i$ 不一定是质数，所以无法使用快速幂求逆元的方法求解，只能使用拓展欧几里得算法

证明：
对于方程组的解：
$$x = \sum_{i = 1}^n a_iM_iM_i^{-1} = a_1M_1M_1^{-1} + a_2M_2M_2^{-1} +···+a_nM_nM_n^{-1}$$
其中：
$a_1M_1M_1^{-1} \equiv a_1 (\bmod m_1)$，后面的每一项 $\sum\limits_{i = 2}^n a_iM_iM_i^{-1}$，$M_i$ 中都包含了因子 $m_1$，所以$\sum\limits_{i = 2}^n a_iM_iM_i^{-1} \equiv 0(\bmod m_1)$，所以 $x \equiv a_1(\bmod m_1)$，同理可得对于每一项 $x$ 都满足 $x \equiv a_i(\bmod m_i)$

中国剩余定理证明

拓展中国剩余定理

模板题

给定 $n$ 组正整数 $a_i, m_i$,满足 $x \equiv m_i(\bmod a_i)$ ，求最小正整数解 $x$
$$\begin{cases} x \equiv m_1(\bmod a_1) \\ \\ x \equiv m_2(\bmod a_2) \\ \\ ··· \\ \\ x \equiv m_n(\bmod a_n) \\ \end{cases}$$
本题中$m_i$不一定两两互质，中国剩余定理不再适用，考虑使用数学归纳法
对于前两个方程：
$$\begin {cases} x \bmod a_1 = m_1 \\ \\ x \bmod a_2 = m_2 \\ \end {cases}$$
等价于：
$$\begin {cases} x = k_1a_1 + m_1 \\ \\ x = k_2a_2 + m_2 \\ \end {cases}$$
其中 $k_1$ 和 $k_2$ 是任意整数
即：
$$k_1a_1 + m_1 = k_2a_2 + m_2 \Longrightarrow k_1a_1 - k_2a_2 = m_2 - m_1$$
对于给定 $a_1,a_2,m_2,m_1$ 的式子，$k_1a_1 - k_2a_2 = m_2 - m_1$，求系数 $k_1,k_2$ 即可利用拓展欧几里得算法
根据拓展欧几里得算法：$k_1a_1 - k_2a_2 = m_2 - m_1$ 有解，等价于 ${\rm gcd}(a_1, a_2) \mid (m_2 - m_1)$ ( $m_2 - m_1$ 是 $a_1$ 和 $a_2$ 的最大公因数的倍数 )，假设有解，并且已经求出一组特解 $k_{1_0}, k_{2_0}$，那么 $k_1, k_2$ 的通解：
$$\begin{cases} k_1 = k_{1_0} + k\dfrac {a_2}d \\ \\ k_2 = k_{2_0} + k\dfrac {a_1}d \\ \end{cases}$$

其中 $k$ 是任意整数，注意都是加，注意符号： $k_1a_1 - k_2a_2 = m_2 - m_1$
那么 $x$ 的通解就是：
$$k_1 = (k_{1_0} + k\frac {a_2}d)a_1 + m_1$$

即：
$$x = a_1k_1 + m_1 + k\frac {a_1a_2}d$$

其中$\dfrac {a_1a_2}d = lcm[a, b]$ ( $a$ 和 $b$ 的最小公倍数 )，记作一个新的常数 $a$，$a_1k_1 + m_1$ 是固定不变的，记为 $x_0$
即，$x$ 通解的形式：
$$x = x_0 + ka$$

同理，可以整理出 $x$ 关于 $k_2$ 的通解：
$$x = x_0’ + ka$$

其中 $x_0’ = a_2k_2 + m_2$

可以发现两个式子的形式相同，那么就可以将两个式子合并 $x = x_0 + ka$，其中 $x_0$ 和 $a$ 都是固定的，$k$ 是变化的

同理： 一共有 $n$ 个方程，每次把两个式子合并，就可以把 $n$ 个方程合并为一个方程

合并成一个式子 $x = x_0 + ka$ 之后，即可很方便的求出 $x$ 的最小正整数解，即求 $x \bmod a$ 的最小余数

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)  // 注意开 LL  ( 题目说保证了解一定在 LL 范围内 ) // 每次都把一个新的方程合并到现有的方程中
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int n;
    cin >> n;

    bool has_answer = true; // 存储当前是否已经无解了
    LL a1, m1;
    cin >> a1 >> m1;

    for(int i = 0; i < n - 1; i ++ )  // n 个 方程 合并 n - 1 次
    {
        LL a2, m2;
        cin >> a2 >> m2;

        LL k1, k2;  //先求出当前合并的两个式子对应的k1和k2
        LL d = exgcd(a1, a2, k1, k2);
        if((m2 - m1) % d) // 只有当 m2 - m1 是 a1和a2的最小公因数的倍数的时候 才有解  否则无解
        {
            has_answer = false;
            break;   // 只要其中一组方程无解 那么 x 就无解  直接 break
        }
        k1 *= (m2 - m1) / d;  // 拓展欧几里得算法求出的其实是 gcd 对应的 k1  要翻倍一下
        LL t = a2 / d; // 通过特解 求出最小正整数解 k1
        k1 = (k1 % t + t) % t; // 把 k1 变成最小的正整数解    防止溢出  让每次求出的 k1 都是最小的正整数解 ：此题数据范围比较极限 每次都必须取比较小的 k

        m1 = a1 * k1 + m1;   // m1 变成 a1 * k1 + m1
        a1 = abs(a1 / d * a2); // a变成a1和a2的最小公倍数  要取绝对值 最小公倍数一定是正的
    }

    if(has_answer)
    {
        cout << (m1 % a1 + a1) % a1 << endl;   // 输出最小正整数解：C++特性
    }
    else puts("-1");

    return 0;
}

C++取余常用技巧：

(r % p + p) % p  ： 正数
(p - r % p) % p  ： 负数

数论很少有题目可以直接套用模板，一般都是将题目封装到复杂的题目中，需要我们从题目中抽象出具体的模板

Reference：

1. 《算法竞赛进阶指南》
2. 《算法导论》