（一）数论

（一）数论

1.质数

1. 对所有的大于1的自然数字，定义了【质数/合数】这一概念。对于所有小于等于1的自然数，没有这个概念，它们既不是质数也不是合数。
2. 质数的定义：对于大于1的自然数，如果这个数的约数只包含1和它本身，则这个数被称为质数，或者素数

（1）试除法判定质数

试除法：对于一个数n，从2枚举到n-1，若有数能够整除n，则说明除了1和n本身，n还有其他约数，则n不是质数；否则，n是质数

优化：由于一个数的约数都是成对出现的。比如12的一组约数是3，4，另一组约数是2，6。则我们只需要枚举较小的那一个约数即可

我们用d|n来表示d整除n，只要满足d|n，则一定有{n/d}|n，比如3∣12，则{12/3} | 12，因为约数总是成对出现的，我们只需要枚举小的那部分数即可，令d ≤ n/d，即，d ≤ sqrt{n}，因此对于n，只枚举2到sqrt{n}即可。

注意：for循环的结束条件，推荐写成i <= n / i。有的人可能会写成i <= sqrt(n)，这样每次循环都会执行一次sqrt函数，而这个函数是有一定时间复杂度的。而有的人可能会写成i * i <= n，这样当i很大的时候（比如i比较接近int的最大值时），i * i可能会溢出，从而导致结果错误。

AcWing 866. 试除法判定质数

#include <iostream>
#include <algorithm>
using namespace std;
 
bool is_prime(int x){
    if(x<=1) return false;
    for(int i=2;i<=n/i;i++){
        if(x/i==0) return false;
    }
    return true;
}
 
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        if(is_prime(x)) puts("Yes");
        else puts("No");
    }
    return 0;
 

（2）质因数分解-试除法

对于一个整数 N 总能写成如下形式：

$$N=P_1^{{\alpha }_1}\times P_2^{{\alpha }_2}\times P_3^{{\alpha }_3}\cdots \times P_n^{{\alpha }_n}$$

其中Pi都是质数，αi为大于0的正整数，即一个整数可以表示为多个不同质数的次方的乘积

对于一个数求解质因数的过程：从2到n，枚举所有数，依次判断是否能够整除 n 即可（朴素法，时间复杂度O(n))。

优化：n中只包含一个大于sqrt{n}的质因子，很好证明，如果中包含两个大于sqrt{n}的质因子，那么乘起来就大于n了。因此，在枚举的时候可以先把2到sqrt{n}的质因子枚举出来，如果最后处理完n > 1,那么这个数就是那个大于\sqrt{n}的质因子，单独处理一下就可以。时间复杂度降为O(sqrt(n))

求质因数分解，为什么枚举所有数，而不是枚举所有质数，万一枚举到合数怎么办？解释：枚举数时，对于每个能整除 n 的数 i，先把这个数除干净了（就是把这个质数的次方剔除了，表现在上式中就是逐步去除Pi^αi），再继续枚举后面的数，这样能保证，后续再遇到能整除的数，一定是质数而不是合数。

例如：求180的质因数分解

1. i = 2 n = 180 / 2 = 90 / 2 = 45
2. i = 3 n = 45 / 3 = 15 / 3 = 5
3. i = 4 当i是合数时，i 一定不能整除 n 。如果 4 能整除 n 那么 2 一定还能整除 n，就是在 i = 2的时候没有除干净，而我们对于每个除数都是除干净的，因此产生矛盾。
4. i = 5 n = 5 / 5 = 1

AcWing 867. 分解质因数

#include <iostream>
using namespace std;
 
void divide(int x){
    for(int i=2;i<=n/i;i++){
        if(x%i==0){//找到一个质因数
            int s=0;//记录质因数的指数
            while(x%i==0){//除干净
                x/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
    }
    if(x>1) printf("%d %d\n",x,1);//除到最后x还大于1 那x也为质因数 指数为1
    puts(" ");
}
 
 
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        divide(x);
    }
}

（3）筛质数—朴素法

将2到n全部数放在一个集合中，遍历2到n，每次删除当前遍历的数在集合中的倍数。最后集合中剩下的数就是质数。

解释：如果一个数p没有被删掉，那么说明在2到p-1之间的所有数，p都不是其倍数，即2到p-1之间，不存在p的约数。故p一定是质数。

时间复杂度：

$$\frac{n}{2}+\frac{n}{3}+\cdots +\frac{n}{n}=n{\ln }_{}n<n{\log }_{2}n$$

故，朴素思路筛选质数的时间复杂度大约为O(nlogn)

AcWing 868. 筛质数

#include <iostream>
using namespace std;
const int N=1e6+10;
int primes[N];//存储质数
int n,cnt;//cnt存储结果个数
bool st[N];//表示当前数是否已经筛过(标记是否为质数) 
 
void get_prime(int x){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;//i是质数
        for(int j=2*i;j<=x;j+=i) st[j]=true;//不管i是不是质数，i的倍数一定不是质数
    }
}
 
int mian(){
    cin>>n;
    get_prime(n);
    cout<<cnt;
    return 0;
}

（4）筛质数—埃氏筛法

在上面朴素筛法的基础上，

其实不需要把全部数的倍数删掉，而只需要删除质数的倍数即可。

对于一个数p，判断其是否是质数，其实不需要把2到p-1全部数的倍数删一遍，只要删掉2到p-1之间的质数的倍数即可。因为，若p不是个质数，则其在2到p-1之间，一定有质因数，只需要删除其质因数的倍数，则p就能够被删掉。埃氏筛法筛选质数的时间复杂度大约为O{nlog(logn)}

AcWing 868. 筛质数

#include <iostream>
using namespace std;
const int N=1e6+10;
int primes[N];//存储质数
int n,cnt;//cnt存储结果个数
bool st[N];//表示当前数是否已经筛过(标记是否为质数) 
 
void get_prime(int x){
    for(int i=2;i<=n;i++){
        if(!st[i]) {
            primes[cnt++]=i;//i是质数
            for(int j=2*i;j<=x;j+=i) st[j]=true;//只筛质数i的倍数
        }
        
    }
}
 
int mian(){
    cin>>n;
    get_prime(n);
    cout<<cnt;
    return 0;
}

（5）筛质数—线性筛法

大体思路和埃氏筛法一样，将合数用他的某个因数筛掉，其性能要优于埃氏筛法（在$10^6$下两个算法差不多，在10^7下线性筛法大概快一倍）核心思路是：对于某一个合数n，其只会被自己的最小质因子给筛掉

设置一个primes数组，存储质数（以下叙述用pj来表示primes[j]），从2到n进行循环遍历，用数组st[]标记是否为质数。每次循环都对当前质数数组进行遍历，用其最小质因子筛除合数

• 当i % pj == 0时：pj 一定是 i 的最小质因子，因为我们是从小到大枚举质数的，首先遇到的满足i % p j == 0的，pj 一定是 i 的最小质因子，并且pj 一定是pj * i的最小质因子。比如，15 = 3 *5，15的最小质因子是3，则15的倍数中最小的数，其最小质因子同样是3的，15乘以最小质因子3，即45。

  此时跳出循环，因为此时pj是i的最小质因子，要利用大于i的数的最小质因数筛除那些大于i的数就必须保证p[j]*i中p[j]为最小质因子，但是由于继续进行的话p[j]大于i的最小质因子，因此p[j]*i的最小质因子不在是p[j]，所以要跳出循环

• 当i % pj != 0时：pj 一定不是 i 的质因子,并且由于是从小到大枚举质数的，那么 pj 一定小于 i 的全部质因子。那么 pj 就一定是 pj * i 的最小质因子。

因此，则无论哪种情况，pj都一定是 pj * i 的最小质因子，pj * i 必为合数，标记筛除

线性筛法保证了，每个合数，都是被其最小质因子给删掉的，且只会被删一次

AcWing 868. 筛质数

#include <iostream>
using namespace std;
const int N=1e6+10;
int primes[N];//存储质数
int n,cnt;//cnt存储结果个数
bool st[N];//表示当前数是否已经筛过(标记是否为质数) 
 
void get_prime(int x){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;//i是质数
        for(int j=0;primes[j]<=x/i;j++){
            st[primes[j]*i]=true;//筛除以primes[j]为最小质因数的合数
            if(i%primes[j]==0) break;//跳出这层循环
        }
    }
}
 
int mian(){
    cin>>n;
    get_prime(n);
    cout<<cnt;
    return 0;
}

2.约数

（1）试除法：求一个数的所有约数

利用试除法求一个数的所有约数，思路和判断和求质数的判定类似

一个数N有一个约数d，那么N/d也必然是其约数

约数都是成对出现的，只需要枚举1到sqrt{n}即可，注意不要让一个约数加入两次

AcWing 869. 试除法求约数

实现思路：这里使用vector存储最终结果，便于进行最后的排序输出

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
 
vector<int> get_divisors(int x){
    vector<int> res;
    for(int i=1;i<=x/i;i++){
        if(x%i==0){//找到一个约数 实际上就获得两个约数了
            res.push_back(i);
            if(i!=x/i) res.push_back(x/i);
        }
    }
    sort(res.begin(),res.end());
    return res;
}
 
 
int main() {
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        vector<int> res=get_divisors(x);
        for(auto t:res) cout<<t<<" ";
        puts("");
    }
 
    return 0;
}
 

（2）求约数个数

$$将一个数N分解质因数为N=P_1^{{\alpha }_1}\times P_2^{{\alpha }_2}\times P_3^{{\alpha }_3}\cdots \times P_n^{{\alpha }_n}$$ $$定理1：约数的个数为({\alpha }_1+1)\times ({\alpha }_2+1)\times \cdots \times ({\alpha }_n+1)$$

对于定理1：N可以分解为以上n个质数的αi次方的乘积，又因为N的每一个约数d都相当于在这n个pi中每个pi分别取0~αi次，每一种选法的各个质因子相乘就是N的一个约数

eg：

$$12=2^2\ast 3^1$$

• 取0 个 2 和 0 个 3 ， 得 约 数 1
• 取1 个 2 和 0 个 3 ， 得 约 数 2
• 取2 个 2 和 0 个 3 ， 得 约 数 4
• 取0 个 2 和 1 个 3 ， 得 约 数 3
• 取1 个 2 和 1 个 3 ， 得 约 数 6
• 取2 个 2 和 1 个 3 ， 得 约 数 12

(2+1)*(1+1)=6种取法，则12有6个约数，即1，2，3，4，6，12

（3）求约数之和

再在上面的基础上

$$对于12=2^2\ast 3^1来说，其约数之和为2^0\ast 3^0+2^1\ast 3^0+2^2\ast 3^0+2^0\ast 3^1+2^1\ast 3^1+2^2\ast 3^1=(2^0+2^1+2^2)\ast (3^0+3^1)$$

得到定理2：约数之和

$$定理2：所有约数之和为(P_1^0+P_1^1+\cdots +P_1^{{\alpha }_1})\times (P_2^0+P_2^1+\cdots +P_2^{{\alpha }_2})\times \cdots \times (P_n^0+P_n^1+\cdots +P_n^{{\alpha }_n})$$

AcWing 870. 约数个数

**实现思路：**对每次输入的整数ai都分解得到其质因数，并得到对应质因数的指数

• 使用一个哈希表来存储对应质因数与其指数的对应关系
  • unordered_map<int,int> primes：使用map实现哈希表，i对应质因数，primes[i]对应其指数

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
 
int main(){
    int n;
    cin>>n;
    unordered_map<int,int> primes;//哈希表
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<n/i;i++){
            while(x%i==0){//得到质因数
                x/=i;
                primes[i]++;//记录质因数i 及其指数
            }
        }
        if(x>1) primes[x]++;
    }
    LL res=1;
    for(auto prime:primes){//遍历哈希表 根据定理 求约数个数
        res*=(prime.second+1)%mod;//题目要求取模
    }
    cout<<res;
}
 

AcWing 871. 约数之和

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
 
int main(){
    int n;
    cin>>n;
    unordered_map<int,int> primes;//哈希表
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<n/i;i++){
            while(x%i==0){//得到质因数
                x/=i;
                primes[i]++;//记录质因数i 及其指数
            }
        }
        if(x>1) primes[x]++;
    }
    LL res=1;
    for(auto prime:primes){//遍历哈希表 根据定理 求约数之和
        int p=prime.first,a=prime.second;//得到各个质因数及其指数
        LL t=1;
        while(a--) t=(p*t+1)%mod;
        res*=t%mod;
    }
    cout<<res;
}
 

（4）最大公约数(GCD Greatest Common Divisor)

根据一个显然的性质：若d能整除b，d能整除a，即d是a和b的公约数，则d能整除a*x+b*y

求a和b的最大公约数-----欧几里得算法（辗转相除法）：gcd(a,b) == gcd(b, a % b)

即a和b的最大公约数=b和a%b的最大公约数，时间复杂度O(logn)

**理解：**可知a mod b= a - [a/b]*b （[a/b]表示取整），这里简便表示，写为 a mod b= a - c*b

• 左到右：设a和b的最大公约数是k。由以上显然的性质可得k能整除a，k能整除b，则k能整除（a-c*b）
• 右到左：设b和a%b的最大公约数是k。因为k能整除b，k能整除a-c*b，则k能整除(a-c*b+c*b)即a

AcWing 872. 最大公约数

**实现思路：**当b不为0时求b和a%b的最大公约数 ;当b为0时，即a和0的最大公约数，为0，因为0能整除任何数

#include <iostream>
using namespace std;
 
int gcd(int a,int b){
    return b? gcd(b,a%b):a;
}
 
int mian(){
    int n;
    cin>>n;
    while(n--){
        int x,y;
        cin>>x>>y;
        cout<<gcd(x,y)<<endl;
    }
    return 0;
}

3.欧拉函数

欧拉函数phi(n)：得到1~n中与n互质的数的个数

例如：phi(6) = 2，1 - 6 中与 6 互质的数为 1、5

a，b互质就是gcd(a,b) = 1

如何求解欧拉函数？

对于一个数N，可以分解质因数为

$$N=P_1^{k_1}\times P_2^{k_2}\times \cdots \times P_n^{k_n}，则phi(N)=N\times (1-\frac{1}{P_1})\times (1-\frac{1}{P_2})\times \cdots \times (1-\frac{1}{P_n})$$

比如 6=2×3，则phi(6) = 6 * (1 - 1/2) * (1-1/3) = 2，即1~6中有两个与6互质的数

证明：利用容斥原理

$$\begin{gathered} ①从1-N中去除其全部质因子P_1\dots P_n的所有倍数，那么还剩下S_1=N-\frac{N}{P_1}-\frac{N}{P_2}-\cdots -\frac{N}{P_n}个数 \\ ②有的数既是P_i的倍数又是P_j的倍数，因此被减了两遍，需要加一次回来，S_2=S_1+\frac{N}{P_1\times P_2}+\frac{N}{P_1\times P_3}+\cdots +\frac{N}{P_1\times P_n}+\frac{N}{P_2\times P_3}+\cdots +\frac{N}{P_2\times P_n}+\cdots +\frac{N}{P_{n-1}\times P_n} \\ ③有的数是P_i、P_j、P_k的倍数，在第一步减了三次，在第二步加了三次，相当于没加也没减，因此需要减掉一次，因此S_3=S_2-\frac{N}{P_i\times P_j\times P_k}，[i,j,k]是1-n的一组排列 \end{gathered}$$

以此类推到第n步，化简就是上边的公式phi(N)的求解公式

欧拉函数的应用：

欧拉定理：

$$若a与n互质，那么有a^{\varphi (n)}modn=1$$

费马定理：

$$若a与p互质，p是质数，那么有a^{\varphi (p)}modp=a^{p-1}modp=1$$

定义求欧拉函数

AcWing 873. 欧拉函数

实现思路：得到质因数，然后按公式相乘

注意：每次得到质因数i，应按照公式乘以（1-1/i)，但为避免小数，先除再乘，即(1-1/i)=/i*(i-1)

#include<iostream>
using namespace std;
int mian(){
    int n;
    cin>>n;
    while(n--){
        int a;
        cin>>a;
        int res=a;
        for(int i=2;i<n/i;i++){
            if(a%i==0){//得到质因数
                res=res/i*(i-1);
                while(a%i==0) a/=i;//将a除净
            }
        }
        if(a>1) res=res/a*(a-1);//如果a还大于1 a为一个质因数
        cout>>res>>endl;
        return 0;
    }
}

筛法求欧拉函数

利用质数的线性筛法求1-n的欧拉函数

由于在线性筛法的执行过程中，对于质数会保留，对于合数会用其最小质因子筛掉。所以线性筛法是会访问到所有数的。而根据上面的推导，在遇到每种情况时，我们都能求出欧拉函数

• 当i是质数：phi(i)=i-1，因为i为质数，那么前i-1个都与其互质

• 当i是合数：

  某个合数一定是被pj * i 给筛掉的，我们就在筛他的时候求他的欧拉函数值

  1. 如果 i % pj == 0 ,那么pj就是i的某个质因数，那么pj*i和i的质因数组合完全相同，根据欧拉函数公式，所以phi(pj *i) = pj * phi(i)
  2. 如果i % pj != 0，pj不是i的质因数，那么pj*i的质因数组合就是在i的质因数组合基础上加了一个质数pj，根据欧拉函数公式，所以phi(pj * i) = pj * phi(i) *(1 - 1/pj) = (pj - 1) * phi(i)

AcWing 874. 筛法求欧拉函数

在质数线筛法的基础上修改

#include <iostream>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int primes[N],phi[N],cnt;//phi[N]存储欧拉函数结果
bool st[N];
 
LL get_euler(int n){
    phi[1]=1;//1只有其本身与其互质
    LL res=0;
    for(int i=2;i<=n;i++){
        if(!st[i]) {//i为质因数
            primes[cnt++]=i;
            phi[i]==i-1;//前面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];
                break;
            }
            phi[primes[j]*i]=phi[i]*(primes[j]-1);
        }
    }
    for(int i=1;i<=n;i++)
        res+=phi[i];
    return res;
}
 
 
int main(){
    int n;
    cin>>n;
    cout<<get_euler;
}
 

4.快速幂

作用：可以快速的求出a^{k} mod 𝑝 的值，时间复杂度是O(logk)

核心思路：反复平方法

$$\begin{gathered} ①预处理出：a^{2^0}modp、a^{2^1}modp、a^{2^2}modp、\dots 、a^{2^{{\log }_{2}k}}modp一共lo{g}_{2}k个数 \\ 对于这预处理出的数，观察可以发现：a^{2^1}=(a^{2^0}{)}^2、a^{2^2}=(a^{2^1}{)}^2、a^{2^3}=(a^{2^2}{)}^2、\dots 、a^{2^{lo{g}_{2}k}}=(a^{2^{lo{g}_{2}k-1}}{)}^2. \\ 即每个数是前面一个数的平方 \\ ②对于a^k，可将a^k拆成a^k=a^{2^{x_1}}\times a^{2^{x_2}}\times \cdots \times a^{2^{x_t}}=a^{2^{x_1}+2^{x_2}+\cdots +2^{x_t}} \\ 可得到k=2^{x_1}+2^{x_2}+\cdots +2^{x_t}，即k为lo{g}_{2}k个数之和 \\ 那么a^{k}modp=(a^{2^{x_1}}modd)\ast (a^{2^{x_2}}modd)...(a^{2^{x_t}}modd) \\ 再由①中得到的每个数是前一个数的平方，故a^{k}modp=(a^{2^{x_1}}modd)\ast [(a^{2^{x_1}}modd){]}^{2}modd\ast ...\ast \\ (前一个结果的平方modd) \\ ③对于怎么得到a^k=a^{2^{x_1}+2^{x_2}+\cdots +2^{x_t}}，简单，直接取k的二进制数。 \\ 如求4^{5}mod10，则k=(101{)}_2，那么4^5=4^{(101{)}_2}=4^{2^0}\times 4^{2^2} \\ 而4^{2^0}mod10=4，4^{2^1}mod10=4^{2}mod10=6，4^{2^2}mod10=6^{2}mod10=6， \\ (这里就体现了后面的结果为前一个结果的平方再取模) \\ 得到最终结果即为4^{5}mod10=4\ast 6mod10=4 \end{gathered}$$

AcWing 875. 快速幂

#include <iostream>
using namespace std;
typedef long long LL;//a可能超出int
 
//a^k % p
LL qmi(LL a,int k,int p){
    int res=1;//记结果
    while(k){//循环得到k的每个二进制位 
        if(k & 1) res=(LL)res * a % p;//当前二进制位为1时
        k=k>>1;//k右移一位 找下一个二进制位
        a=(LL)a*a % p;//平方一下 再mod p
    }
    return res;
}
 
int main(){
    int n;
    cin>>a;
    while(n--){
        int a,k,p;
        cin>>a>>k>>p;
        cout<<qmi(a,k,p)<<endl;
    }
    
    return 0;
}

AcWing 876. 快速幂求逆元

实现思路：

• 由(a/b)mod m恒等a*x mod m=⇒(b*x) mod m = 1 ，x为b的逆元
• 结合费马定理(欧拉函数的应用)：b与m互质，且m为质数，则b^(m-1) mod m=1
• 上面两式结合：得b的逆元b^(m-2)，则模m乘法逆元x=b^(m-2)%m，本质上就是求快速幂，但多了一个要求：b和m互质
• 注意：当b和m不互质时，无解；否则必存在逆元

#include <iostream>
using namespace std;
typedef long long LL;
 
//求快速幂
LL qmi(LL a,int k,int p){
    LL res=1;
    while(k){//对每个二进制位处理
        if(k & 1) res=(LL)res*a%p;
        k=k>>1;
        a=(LL)a*a%p;
    }
    return res;
}
 
int mian(){
    int n;
    cin>>n;
    while(n--){
        int a,p;
        cin>>a>>p;
        int res=qmi(a,p-2,p);//根据推理得到的公式
        if(a%p) cout<<res<<endl;//如果a和p互质
        else puts("impossible");
    }
    
    
}

5.扩展欧几里得算法

回忆：求最大公约数中学过欧几里得算法（辗转相除法）：gcd(a,b) == gcd(b, a % b)

裴蜀定理：对于任意正整数a，b，那么一定存在非零整数x，y，使得ax+by=gcd(a,b)

证明：令 gcd(a,b) = c ，则a一定是c的倍数，b也一定是c的倍数，那么ax+by也一定是c的倍数，那么可以凑出最小的倍数就是1倍，即ax+by=gcd(a,b)

扩展欧几里得算法：就是求解上面裴蜀定理中a和b的系数x,y

具体怎么求解x，y？ax+by=gcd(a,b)

• 首先若有一个数为0，假设b=0，那么显然gcd(a,0)=a，则可得x=1，y=0
• 若a，b不为0，结合欧几里得算法gcd(a,b) == gcd(b, a % b)，那么ax+by=gcd(a,b)=⇒b*x+(a%b)*y=gcd(a,b)，但在递归的过程中a的系数由x变为y，b的系数由y变为x，所以在递归过程的传入参数时因调换x和y的位置，变为b*y+(a%b)*x=gcd(a,b)，下面的代码会体现
• 设gcd(a,b)=d，那么继续推理得到

​

即可求出系数

• 注意x和y可能是不唯一的

AcWing 877. 扩展欧几里得算法

实现思路：就是在欧几里得算法的基础上修改，增加两个传入参数x，y

#include <iostream>
using namespace std;
 
//这里返回的是最大公约数
int exgcd(int a,int b,int &x,int &y){//这里x和y使用引用，后续直接输出答案
    if(!b){//b=0
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);//注意y和x位置
    y-=a/b*x;
    return d;
    
}
 
 
int main() {
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}
 

AcWing 878. 线性同余方程

扩展欧几里得的应用：求解线性同余方程

**实现思路：**对于(a*x) mod m=b，求解x。

• 恒等变形可以得a*x=m*y'+b=⇒a*x-m*y'=b=⇒a*x+m*y=b，此时就形似扩展欧几里得算法，则由裴蜀定理可知a*x+m*y=gcd(a,m)必然有解，假如b是gcd(a,m)的倍数，即必然存在这样的x和y，使所求等式有解，只需等式两边扩大相应的倍数即可。此时**x=x*(b/gcd(a,m))**
• 这里最后**x*(b/gcd(a,m))%m**是为了得到最小的解，因为x的通解有无数个，防止超出int范围，就取一个最小的
• 假如题目要求x的最小正整数解，则**[x%(b/gcd)+b/gcd]%(b/gcd)**
• 其他理解：AcWing 878. 线性同余方程关于最后结果处理的证明 - AcWing

#include <iostream>
using namespace std;
typedef long long LL;
 
//扩展欧几里得 返回最大公约数
int exgcd(int a,int b,int &x,int &y){
    if(!b){//b=0
        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;
    cin>>n;
    while(n--){
        int a,b,m,x,y;
        cin>>a>>b>>m;
        int d=exgcd(a,m,x,y);
        if(b%d==0) cout<<(LL)x*(b/d)%m<<endl;//取得最小的解
        else puts("impossible");
    }
    return 0;
}

6.中国剩余定理

$$\begin{gathered} 有k个两两互质的数m_1、m_2、\dots 、m_k \\ 给定线性同余方程组x\equiv a_1(mod{m}_1)、x\equiv a_2(mod{m}_2)、\dots 、x\equiv a_k(mod{m}_k) \\ 求x解法： \\ 令M=m_1\times m_2\times \cdots \times m_k，M_i=\frac{M}{m_i}，用M_i^{-1}表示M_i模的逆 \\ (求M_i^{-1}：M_i\times M_i^{-1}\equiv 1(mod{m}_i)，实质就是用扩展欧几里得求一个特殊的线性同余方程:a\times x\equiv 1(modm)) \\ 则x=a_1\times M_1\times M_1^{-1}+a_2\times M_2\times M_2^{-1}+\cdots +a_k\times M_k\times M_k^{-1} \\ 可以验证x为该线性同余方程组的解（略） \end{gathered}$$

AcWing 204. 表达整数的奇怪方式

实现思路：

求解推导

$$\begin{gathered} 1.对于两个式子，考虑将其合并： \\ x\equiv m_1(\%a_1) \\ x\equiv m_2(\%a_2) \\ 则有：x=k_1\ast a_1+m_1,x=k_2\ast a_2+m_2, \\ 进一步联立上面两式：k_1\ast a_1+m_1=k_2\ast a_2+m_2==>{\mathbf{k}}_1\ast {\mathbf{a}}_1+{\mathbf{k}}_2\ast (-{\mathbf{a}}_2)={\mathbf{m}}_2-{\mathbf{m}}_1...① \\ 也就是我们要找到一个最小的k_1,k_2，使得等式成立(因为要求x最小，而a和m都是正数) \\ 2.对a_1和a_2使用扩展欧几里得得到最小公约数d=gcd(a_1,-a_2) \\ 即{\mathbf{k}}_1\ast {\mathbf{a}}_1+{\mathbf{k}}_2\ast {\mathbf{a}}_2=\mathbf{d}=\mathbf{gcd}({\mathbf{a}}_1,-{\mathbf{a}}_2)...② \\ 此时对于①和②式就出现了之前求线性同余方程的情况，即m_2-m_1是d的倍数时(d|m_2-m_1)方程有解 \\ ②式两边乘\frac{m_2-m_1}{d}就转化为①式 \\ 即{\mathbf{k}}_1\ast {\mathbf{a}}_1\ast \frac{{\mathbf{m}}_2-{\mathbf{m}}_1}{\mathbf{d}}+{\mathbf{k}}_2\ast {\mathbf{a}}_2\ast \frac{{\mathbf{m}}_2-{\mathbf{m}}_1}{\mathbf{d}}={\mathbf{m}}_2-{\mathbf{m}}_1 \\ 3.有解的情况下得到一组解: \\ {\mathbf{k}}_1={\mathbf{k}}_1\ast \frac{{\mathbf{m}}_2-{\mathbf{m}}_1}{\mathbf{d}},{\mathbf{k}}_2={\mathbf{k}}_2\ast \frac{{\mathbf{m}}_2-{\mathbf{m}}_1}{\mathbf{d}},注意这里k就表示特解 \\ 4.找最小正整数解：模尽倍数后，剩下的余数就是最小正整数解 \\ {k}_1=k_1\%abs(\frac{a_2}{d}),k_2=k_2\%abs(\frac{a_1}{d}) \\ 5.找满足方程的所有解 \\ 将一组方程的解带回方程：k_1\ast a_1+k_2\ast a_2=c \\ 等式左边加减\frac{a_1\ast a_2}{d},方程右边不变，可得： \\ {k}_1\ast a_1+k_2\ast a_2+a_1\ast \frac{a_2}{d}-a_2\ast \frac{a_1}{d}=(k_1+\frac{a_2}{d})\ast a_1+(k_2-\frac{a_1}{d})\ast a_2=c \\ 于是得到所有解集：{\mathbf{k}}_1={\mathbf{k}}_1+\frac{{\mathbf{a}}_2}{\mathbf{d}}\ast \mathbf{k},{\mathbf{k}}_2={\mathbf{k}}_2-\frac{{\mathbf{a}}_1}{\mathbf{d}}\ast \mathbf{k} \\ 6.再代入k_1,k_2得新的x为：x=(k_1+\frac{a_2}{d}\ast k)\ast a_1+m_1 \\ =k_1\ast a_1+m_1+\frac{a_1\ast a_2}{d}\ast k \\ 令新的a_1^{{}^{\prime }}=\frac{a_1\ast a_2}{d},新的m_1^{{}^{\prime }}=k_1\ast a_1+m_1 \\ 那么x=a_1^{{}^{\prime }}\ast k+m_1^{{}^{\prime }},这时就又回到了第一步，至此完成两个式子的合并, \\ 后续再来一个a_3,m_3同理继续合并，n个式子进行n-1次合并得到最终式 \end{gathered}$$

其他理解：AcWing 204. 表达整数的奇怪方式 - AcWing

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
int n;
 
//扩展欧几里得求系数 返回最大公约数d
LL exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    LL d=exgcd(b,a%b,y,x);//记得调换x和y的位置
    y-=a/b*x;
    return d;
}
 
//求a%b=a的最小正整数解
LL inline mod(LL a,LL b){
    return (a%b+b)%b;
}
 
int main(){
    cin>>n;
    LL a1,m1;
    cin>>a1>>m1;
    for(int i=1;i<n;i++){//n-1次合并
        LL a2,m2,k1,k2;
        cin>>a2>>m2;
        LL d=exgcd(a1,-a2,k1,k2);
        //如果m2-m1不能整除d 则无解结束
        if((m2-m1)%d) {puts("-1");return 0;}
        //否则有解
        k1=mod(k1*(m2-m1)/d,abs(a2/d)); //模尽得到最小正整数解
        //更新m1,a1 继续下轮合并
        m1=k1*a1+m1;
        a1=abs(a1/d * a2)
    }
}