快速幂用到的地方很多，接下来我们来看一个例子。

快速幂求逆元：

什么叫逆元呢？

若整数 $b，m$ 互质，并且对于任意的整数 $a$，如果满足 $b|a$，则存在一个整数 $x$，使得 $\frac{a}{b}≡a×x(\mod m)$ ，则称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b^{−1}(\mod m)$。

这个很绕啊，我们来给大家形象的解释一下。

如果说 $\frac{a}{b}$ 是一个整数的话，不是小数，我们希望不做除法，因为取余数的话除法是一个很麻烦的事，我们希望把除法变成一个乘法，我们希望找到一个数使得 $\frac{a}{b}≡a×x(\mod m)$，即求 $a\mod b$，转换成 $a×x(\mod m)$，我们就把 x 叫做 $b$ 的模 $m$ 的逆元，记作 $b^{−1}$，也就是说 $\frac{a}{b}≡a×b^{−1}$，注意 $b^{−1}$ 是一个标记，它不是 $b$ 的负一次方，它是一个整数，也就是说我们可以把所有除 $b$ 的情况，转换成所有乘 $b$ 的逆元的情况，因为数论里面有除法的话它不一定是个整数，变成乘法就很好了。两个整数相乘还是整数，两个整数相除不一定是整数。

P3811 【模板】模意义下的乘法逆元

这个题就是让我们求一下逆元：

性质：

虽然我们这个定理看着很麻烦，但求逆元是干什么的呢？通俗一点来说就是给我们一个 $b$，让我们找到一个 $x$ 使得 $b*x≡1(\mod m)$ 就可以了。

这里的限制是模数一定是质数 $p$，即$b*x≡1(\mod p)$，那是质数的话我们就可以联想到费马小定理，若果说 $b$ 与 $p$ 互质，那么 $b^{p-1}≡1(\mod p)$，那么 $b*b^{p-2}≡1(\mod p)$，所以如果 $p$ 是质数的话，那么 $b$ 的逆元就很好求了，就直接求 $b^{p-2}$ 就可以了，$b^{p-2}$ 就是 $b$ 的模 $p$ 的逆元。

因为 $p$ 是质数，所以 $p≥2$，所以 $p-2≥0$ 它一定是合法的。

其实就是求一下 $a^{p-2}(\mod p)$，本质上就是一个快速幂。然后我们把快速幂的代码 $copy$ 过来。

举例：$b=3$，$p=5$，$b*x≡1(\mod p)$，即求一下 $3$ 乘哪个数模 $5$ 的余数是 $1$？随便想一个 $x=2$，即 $3$ 模 $5$ 的逆元是 $2$，也可以用费马小定理来求，那就是 $3^{5-2}=27(\mod 5)=2$ 也可以求出来 $3$ 的逆元就是 $2$。

$Lucas$ 定理我们下节数学课会讲。组合数大家有兴趣可以先试一下。

然后我们先把快速幂的代码 $copy$ 过来：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

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


int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%lld\n", qmi(a, b, p));
    }

    return 0;
}

然后我们这个题输入的是一个 $a$ 和 $p$，求的是 $a^{p-2}(\mod p)$

#include <bits/stdc++.h>
using namespace std;

// a^k % p
int qmi(int a, int k, int p)
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p; // 当前k的末位是1 
        k >>= 1; // 把 k 的末位删掉 
		a = (LL)a * a % p; // 再把a变成下一个，平方一下 
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b, p;
        scanf("%d%d", &a, &p);
        printf("%d\n", qmi(a, p - 2, p));
    }

    return 0;
}

但注意这里可能是无解的，什么时候会无解呢？当 $b$ 是 $p$ 的倍数的时候，即 $b$ 与 $p$ 不互质的时候就无解了。因为 $b$ 是 $p$ 的倍数，那么 $b*x$ 也一定是 $p$ 的倍数，那么模 $p$ 一定得 $0$，不可能余 $1$，只有在这种情况下才是无解的。

如果说 $b$ 不是 $p$ 的倍数，由于 $p$ 是质数，那么 $b$ 和 $p$ 一定互质，那么由费马小定理 $b^{p-1}≡1(\mod p)$ 我们一定能构造出一组解，所以它一定存在逆元。

所以大家做数论题的话，一定要用一个很严谨的思维来考虑，

所以这个题要特判一下，但 $p=2$ 时比较特殊。逆元是 $b^0$，$0$ 次方一定返回 $1$，所以这里一定要特判一下。

#include <bits/stdc++.h>
using namespace std;

// a^k % p
int qmi(int a, int k, int p)
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p; // 当前k的末位是1 
        k >>= 1; // 把 k 的末位删掉 
		a = (LL)a * a % p; // 再把a变成下一个，平方一下 
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }

    return 0;
}

数论的话就是举个例子秒懂，所以这个题就是用我们的快速幂来求逆元，有个限制就是 $p$ 一定是质数，不然就不满足我们的费马小定理了。

3、扩展欧几里得算法

这也是一个比较有意思的定理，说的是给我们一个正整数 $a$ 和 $b$，讲这个之前我们先讲一个叫裴蜀定理。

P4549 【模板】裴蜀定理

裴蜀定理：包含两个方面，但有些地方说的可能不太全。

有任意正整数 $a$，$b$，那么一定存在非零整数 $x$，$y$ 使得 $ax+by=gcd(a,b)$，并且 $gcd(a,b)$ 就是 $a$ 和 $b$ 能凑出来的最小的正整数，这是一个很有趣的性质。

这是为什么呢？大家可以想一下。

（1）一方面：假设存在 $ax+by=d$，显然 $d$ 一定是 $a$ 和 $b$ 最大公约数的倍数，所以说 $a$ 和 $b$ 能凑出来的最小的就是它们的最大公约数。因为我凑出来的所有数都是我最大公约数的倍数，所以最小最小只能是一倍，即最大公约数。

（2）另一方面：如何证明对于任意的正整数 $a$，$b$，一定存在非零整数 $x$，$y$ 使得 $ax+by=gcd(a,b)$? 当我们想要证明一个存在性的东西的时候，我们可以用构造法，只要能构造出来一种方式，使得对于任意的正整数 $a$，$b$，都可以求出来 $x$，$y$，使得它们的和等于它们的最大公约数，那么就证明出来了。

构造的方法就是扩展欧几里得算法，也就是扩展欧几里得给了我们一个算法使得我们可以对于任意的正整数 $a$，$b$，都可以求出来 $x$，$y$。

接下来我们就来讲一下扩展欧几里得算法是如何求它们的系数的。

题目：给定 $n$ 对正整数 $a_i,b_i$，对于每对数，求出一组 $x_i,y_i$，使其满足 $a_i×x_i+b_i×y_i=gcd(a_i,b_i)$。本题答案不唯一，输出任意满足条件的 $x_i,y_i$ 均可。$1≤n≤10^5,1≤a_i,b_i≤2×10^9$。

首先我们回忆一下欧几里得算法：

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

现在我们把它用 if 展开，写详细一点：

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    if (!b)
    {
        return a;
    }
    
    return gcd(b, a % b);
}

int main()
{
    int n;
    scanf("%d", &n);

    return 0;
}

那么我们来回忆一下欧几里得算法的原理是什么？$(a,b)=(b,a\mod b)$，那么我们如何用欧几里得算法顺便求出来 $a$ 和 $b$ 的系数呢？这里我们用引用来传 $x,y$。

#include <bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        return a;
    }
    
    return gcd(b, a % b);
}

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

    return 0;
}

那么接下来要做的就是 $(a,0)=a$，我们要搞两个系数使得 $a*x+0*y=a$，那么显然 $x=1,y=0$ 就是一组解。

#include <bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
    	x = 1, y = 0;
        return a;
    }
    
    int d = gcd(b, a % b); // 把最大公约数记下来 
}

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

    return 0;
}

然后我们在递归的时候来求一下，首先边界的时候我们已经有了 $x=1,y=0$ 一定是成立的，那么递归求的时候我们把 $x,y$ 反转：

#include <bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
    	x = 1, y = 0;
        return a;
    }
    
    int d = exgcd(b, a % b, y, x); // 把最大公约数记下来 
}

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

    return 0;
}

即 $by+(a\mod b)x=(a,b)$，我们把 $(a,b)$ 记作 $d$，那么我们把它展开，看一下 $a$ 和 $b$ 的系数多少？

首先 $a\mod b=a-\lfloor \frac{a}{b} \rfloor*b$，代入就会有 $by+(a-\lfloor \frac{a}{b} \rfloor*b)x=d$，然后我们把 $a$ 的系数整理到一快，$b$ 的系数整理到一块，$ax+b(y-\lfloor \frac{a}{b} \rfloor*x)=d$，那么 $a$ 的系数 $x$ 不变，y -= a / b * x;

#include <bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
    	x = 1, y = 0;
        return a;
    }
    
    int d = exgcd(b, a % b, y, x); // 把最大公约数记下来 
    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;
}

这里 $x$ 和 $y$ 是不唯一的，举个例子 $ax+by=d$，我们把 $a(x-\frac{b}{d})+b(y+\frac{a}{d})=d$，因为 $d|b,d|a$，所以 $\frac{b}{d},\frac{a}{d}$ 都能整除，那么展开之后就抵消了。

也就是说只要我们求出一个 $x_0,y_0$，我们就可以把所有解求出来，$ax+by=d$，$ax_0+by_0=d$，那么：

这个就是 $x,y$ 所有的解，留给大家作课后思考，这个很好证。

这就是我们的扩展欧几里得算法，然后我们来看一下扩展欧几里得算法的一个简单应用。

题目：求解线性同余方程

给定 $n$ 组数据 $a_i,b_i,m_i$，对于每组数求出一个 $x_i$，使其满足 $a_i×x_i≡b_i(\mod m_i)$，如果无解则输出 impossible。结果可能不唯一，输出任意一个满足条件的结果均可。输出答案必须在 int 范围之内。

思路：就是说给定我们很多个 $a,b,m$，我们要借一个方程，这个方程是线性同余方程 $ax≡b(\mod m)$。比如求 $2x≡3(\mod 6)$，这个解有很多个啊？这个有解吗这个？这个无解啊，所以这个无解，所以再看第二个 $4x≡3(\mod 5)$，那么 $x=2$，也可以输出 $x=7$，只要输出任意一个在 int 范围之内的解就可以，

那么这个问题怎么来解呢？其实就是把这个问题转换成一个扩展欧几里得问题就可以了，我们把这个等式做变形，$ax≡b(\mod m)$ 等价于 存在 $y∈z$，使得(st. subject to) $ax=m*y+b$，我们再整理一下就是 $ax-my=b$，由于 $b$ 是一个整数，那么我们可以把这个负号放到 $y$ 里面去，再随便搞一下 $y'=-y$，那么就有 $ax+my'=b$，那么现在问题就变成了，给定我们 $a,m,b$ 让我们求一个系数 $x$ 使得 $ax+my'=b$，这不就是扩展欧几里得算法吗？

所有的都是做等价变形，所以说这个方程式 $ax≡b(\mod m)$ 有解等价于这个等式 $ax+my'=b$ 有解，那么我们前面讲过，这个等式有解的充分必要条件是 $(a,m)|b$，也就是只要 $b$ 是我们 $a$ 和 $m$ 的最大公约数的倍数就可以了，就一定有解，否则就一定无解。那由扩展欧几里得算法 $ax+my'=d$，然后我们只要把系数扩大若干倍，就可以把 $d$ 变成 $b$ 了，$ax+my'=b$，也就是在等式两边同时扩大 $\frac{b}{d}$ 倍。

然后这个题就把我们刚才那个题的代码 $copy$ 过来稍微改一改就可以了。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int gcd(int a, int b, int x, int y)
{
    if (!b)
    {
    	x = 1, y = 0;
        return a;
    }
    
    int d = gcd(b, a % b, y, x); // 把最大公约数记下来 
    y -= a / b * x;
    return d;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n -- )
    {
    	int a, b, m;
    	scanf("%d%d%d", &a, &b, &m);
    	int x, y;
    	int d = exgcd(a, b, x, y);
    	if (b % d) puts("impossible");
    	else printf("%d\n", (LL)x * (b / d) % m);
	}

    return 0;
}

这样我们就用扩展欧几里得算法把我们的线性同余方程讲完了。

4、中国剩余定理

给定我们一堆两两互质的数，$m_1,m_2,···,m_k$ 两两互质，然后我们要解决这样一个线性同余方程组：

乘积的话很好算，乘积就是乘积，然后求逆的话我们可以用扩展欧几里得算法来求逆，这里不能用费马小定理来求逆，因为这里无法保证 $m_i$ 是质数，只是两两互质，所以现在就是求一个特殊的线性同余方程：

只不过这里右边不是 $b$ 了，是 $1$。

所以我们用扩展欧几里得算法来求就可以求出逆了。这里面的每一项都可以很好的求出来，求完之后整个就是一组解，那么为什么它是一组解呢？

我们就来看一下它是不是满足每一个等式，

首先是不是满足第一个式子，$x≡a_1(\mod m_1)$，首先 $a_1*M_1*M_1^{-1}$ 中，这个$M_1^{-1}$ 表示的是 模 $m_1$ 的逆，所以 $M_1*M_1^{-1}=1$，然后后面的每一项 $M_i$ 里面都是乘了一个 $m_1$ 的，所以后面的每一项模 $m_1$ 都是 $0$，所以说 $x≡a_1(\mod m_1)$。同理对于每一个式子都是成立的，所以这一组就被称为我们的公式解，这个就叫中国剩余定理。

然后大家想去练一下的话可以看一下我们这个题：

P4777 【模板】扩展中国剩余定理（EXCRT）

求一个线性方程组的解。