##[$AcWing$ $876$. 快速幂求逆元](https://www.acwing.com/problem/content/description/878/)

### 一、题目描述
给定 $n$ 组 $a_i,p_i$，其中 $p_i$ 是质数，求 $a_i$ 模 $p_i$ 的乘法逆元，若逆元不存在则输出 `impossible`。

注意：请返回在 $0∼p−1$ 之间的逆元。

**乘法逆元的定义**
![](http://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/2023/03/1c94090fb5c689ef8633819a16042420.png)

**输入格式**
第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个数组 $a_i,p_i$，数据保证 $p_i$ 是质数。

**输出格式**
输出共 $n$ 行，每组数据输出一个结果，每个结果占一行。

若 $a_i$ 模 $p_i$ 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 `impossible`。

**数据范围**
$1≤n≤10^5,1≤a_i,p_i≤2∗10^9$

**输入样例：**
```cpp {.line-numbers}
3
4 3
8 5
6 3
```
**输出样例：**
```cpp {.line-numbers}
1
2
impossible
```

### 二、逆元概念
<!-- 让表格居中显示的风格 -->
<style>
.center 
{
  width: auto;
  display: table;
  margin-left: auto;
  margin-right: auto;
}
</style>

<div class="center">

| 序号 | 取模概念下的加减乘除               | 正确性                                        |
| ---- | ---------------------------------- | --------------------------------------------- |
| 1    | $(a + b)\% p = (a\%p + b\%p) \%p$  | <font color='green' size=4><b>正确</b></font> |
| 2    | $(a - b) \% p = (a\%p - b\%p) \%p$ | <font color='green' size=4><b>正确</b></font> |
| 3    | $(a * b) \% p = (a\%p * b\%p) \%p$ | <font color='green' size=4><b>正确</b></font> |
| 4    | $(a / b) \% p = (a\%p / b\%p) \%p$ | <font color='red' size=4><b> 错误 </b></font> |

</div>

#### $Q1$:为什么除法错的?

证明是对的难，证伪的只要举一个反例:

$(100/50)\%20 = 2  ≠  (100\%20) / (50\%20) \%20 = 0$

对于一些题目，我们必须在中间过程中进行求余，否则数字太大，电脑存不下，那如果这个算式中出现除法，会损失精度，导致答案错误。

因为除法在取模运算时没有性质  $( a/b )\% c = (a\%c /b\%c) \%c$,这个是不成立的，没法计算了，这时数学家提出了个 **逆元** 的概念：

比如 $3 /5 \ mod \ 7$  ,因为$5$在乘法模$7$的世界里的逆元是$3$，所以转化为 $3 * 3 \ mod\ 7$,就可转化为乘法的性质了，就方便计算了，就是答案$2$。

**逆元可以代替除法，除以这个数就等于乘以这个数的逆元。**

#### $Q2$:怎么理解逆元的含义？
想像你在一个加法的世界里，以$0$为世界的中心。有一天，你从世界的中心位置，进行了$+3$，突然，你想回到世界的中心，而你只能使用加法，所以你需要找一个数，让你加上这个数后，可以回到$0$这个世界的中心，这个数就是你在加法世界里$3$的逆元，也就是$-3$。

想像你在一个乘法取模$7$的世界里，以$1$为世界的中心，有一天，你从世界的中心位置，进行了$*3 \ mod\ 7$的操作，突然，你想回到世界的中心，而你只能使用乘法取模的，所以你需要找到一个数，让你乘上它再模$7$后，回到世界的中心，那么这个数就称为你在乘法模$7$世界的逆元。

举个栗子， $3 * 5\ mod\ 7 =1$  那么$3$和$5$就在乘法$mod7$世界里互为逆元，就像是加法世界里的$3$和$-3$一样。

在这个乘法模$7$的世界里，逆元不是唯一的，比如 $3 * 5\  mod\  7 =1$  而 $3*12\ mod\  7 =1$。我们所说的**求逆元一般是指逆元当中最小的那个**。


### 三、费马小定理

**内容:**
**当$p$为质数时 $\large a^{p-1} \equiv 1 (mod\ p) $**

**证明：略**

**举个栗子**：
今天是周一，再过 $3^{2008}$ 次方天，是周几呢？

解：因为一周$7$天，其实是在求$3^{2008}\%7$。
此时$p=7$,是质数，可以用费马小定理计算同余结果:

计算$2008$与$p-1$的关系，$2008=6*334+4$

所以$3^{2008} \equiv 3^{4} (mod \quad 7) $  就是 $81\%7=4$

今天是周一，再过四天就是周五了。


### 四、怎样求逆元？

* 当$p$为质数时，可以用费马小定理+快速幂求逆元：

  $\because$$a^{p-1}≡1 (mod\quad p)$

  $\therefore$$a \times a^{p-2}≡1 (mod\quad p)$

  $\therefore$ $a^{p-2}$就是$a$的逆元。

* **当$p$不是质数时，可以用扩展欧几里得算法求逆元：** (学习到这里时先不用理会这个内容)
  $a$有逆元的充要条件是$a$与$p$互质，所以$gcd(a, p) = 1$
  假设$a$的逆元为$x$，那么有$a * x ≡ 1 (mod\ p)$
  等价：$ax + py = 1$
  $exgcd(a, p, x, y)$

### 五、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
#define int long long

// 快速幂 (a^k)%p
int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

signed main() {
    int n;
    cin >> n;
    while (n--) {
        int a, p;
        cin >> a >> p;
        if (a % p == 0)
            puts("impossible"); // 不互质
        else
            printf("%lld\n", qmi(a, p - 2, p));
    }
}
```
### 六、费马小定理练习

#### $Q1$: $p=7$ 求$2^{32}\ \%p$

这个幂指数很大，我们不会傻傻的真的去计算出$2^{32}$，而是利用费马小定理对指数进行缩减：

因为$p=7$是质数，所以使用费马小降幂，$p-1=6$
$2^6\%p=1$
在$32$里面，把所有$6$的倍数去掉，就是$2^{32-6*5}=2^2=4$
也就是说，我们可以把原来的$32$降为$4$,最终的答案是一样的结果。



#### $Q2:$一个多位数有$2020$位，它左边三位为$123$。当这个数最大时，它被$29$除所得的余数是_______。

在小学奥数中，经常会用到费马小定理解决余数问题。

* 先举一个简单的例子：

  比如计算$18^{111}$ 除以$23$的余数是多少。

  在这里，$a=18$， $p=23$是素数，根据所以使用费马小定理，我们知道$18^{(23-1)}$除以$23$余$1$，即：

  $18^{111} \equiv 18^{22 \times 5 +1} \equiv 18^{22 \times 5 } \times 18 \equiv 18 (mod 23)$

  所以答案就是：$18$。

* 回到这个问题:
  这个$2020$位数最大时即为$123$后面是$2017$个$9$。
  我们设这个数是$a$，  则$a= 124 \times 10^{2017}-1$。
  这个问题就转变为$124 \times 10^{2017}-1$除以$29$的余数是多少？
  <br>我们用同余运算和费马小定理有：
  $124 \times 10^{2017} -1$
  $\equiv 8 \times 10^{72\times 28+1}-1$  这里因为$124$去除$29$，商是$4$,余数是$8$。商不会影响同余运算，舍去，保留余数$8$
  $\equiv 8 \times 10^1 -1$
  $\equiv 80-1$
  $\equiv 21 (mod \ 29)$
  答案就是：$21$
  怎么样，超简单吧？

  那么，如果$p$不是素数时，这种问题又该怎么处理呢？
  这时候欧拉定理和欧拉函数就要大显身手啦。


#### $Q3$:
<center><img src='https://img2018.cnblogs.com/blog/1454456/201903/1454456-20190321213031984-364307702.png'></center>

**解题思路**

因为模数是$101$，比较小，而幂$n$是$2019^{2019}$，很大！所以使用费马小降幂$n\%(p-1)$，这里$p$就是$101-1 = 100$；
```c++
  int n = 1, ans = 0;
    for (int i = 1; i <= 2019; i++)  n = n * 2019 % 100;
```

也就是说，在不断的循环计算$n$的过程中，我们利用费马小定理，找到了一个$n'$,使得$n'$与原数$n$对于结果的贡献是一样的，但$n'$明显小于$n$,方便计算出来结果。 

**实现代码**
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 1, ans = 0;
    for (int i = 1; i <= 2019; i++) n = n * 2019 % 100; //计算出n'
    // 1~11的n次方
    for (int i = 1; i <= 11; i++) {
        int x = 1;
        for (int j = 1; j <= n; j++) x = x * i % 101; //降幂后可以正常按要求计算
        //收集答案
        ans += x;
    }
    //最终也要模一下101
    printf("%d\n", ans % 101);
    return 0;
}
```


#### $Q5$:
<center><img src='https://img2018.cnblogs.com/blog/1454456/201903/1454456-20190321213416622-1991394410.png'></center>

**解题思路**
项数比$mod$大很多，$2019$比$10086$小，所以不用费马小定理，用**循环周期+快速幂**做

<center><img src='https://img2018.cnblogs.com/blog/1454456/201903/1454456-20190321213519548-140956041.png'></center>

**实现代码**
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 10086;

LL pow_mod(LL x, LL p) {
    LL res = 1;
    while (p) {
        if (p & 1) res = res * x % mod;
        p >>= 1;
        x = x * x % mod;
    }
    return res;
}

LL ans;
LL n = 1e12;

int main() {
    for (int i = 1; i <= mod; i++) ans = (ans + pow_mod(i, 2019)) % mod; //求到10086 一个循环周期的长度
    ans = ans * (n / mod) % mod;                                         //乘上倍数
    n %= mod;                                                            //再加上余数
    for (int i = 1; i <= n; i++) ans = (ans + pow_mod(i, 2019)) % mod;

    printf("%lld\n", ans);
    return 0;
}
```