《洛谷深入浅出进阶篇》模意义下的乘法逆元+洛谷P3811

什么是乘法逆元？

算数意义上的乘法逆元指的是倒数，即：a*（1/a）=1

所以 1/a 是 a在算数意义下的乘法逆元，或者可以说二者互为逆元。
这有什么用呢？

除以a就等于乘上a的乘法逆元，乘以a等于除以a的乘法逆元。

那么我们回到我们要介绍的新的乘法逆元：模意义上的乘法逆元。(使用条件，当一个正整数做分母的时候）

例如我们要求（x+y）*（x-y）/2 mod p

很显然，对于分子，我们可以直接用模的性质
（x+y）*（x-y）modp = 【（x+y）%p *（x-y)%p】%p

但是，这样的方法只对加减乘有效。

除法的话，由于整除向下取整的原因，我们无法直接使用。这时候就要用到逆元，来代替除法，因为除以一个数取模，等于乘上它在模意义上的逆元，后取模。

ok，那么什么是模意义上的乘法逆元呢？

  给出定义： a*x = 1（mod）p，也就是a*x对p取模为1的时候，x就是a 的逆元，所以，当除以a的时候就相当于是乘上a的逆元x。（注意，模只对整数时有意义的，所以我们的变量都应该是整数）

那么我们知道了模意义上的乘法逆元，应该怎么求它的乘法逆元呢？
就可以用到三种方法：扩展欧几里得算法，费马小定理，线性递推。

扩展欧几里得算法：

a*x=1 （mod）p
这个式子可以展开写成：（扩展欧几里得相关文章连接：《洛谷深入浅出进阶篇》 欧几里得算法，裴蜀定理，拓展欧几里得算法————洛谷P1516 青蛙的约会-CSDN博客https://blog.csdn.net/louisdlee/article/details/134751119?spm=1001.2014.3001.5502）
a*x+p*y=1
也就是求x，y的不定方程。
我们由裴蜀定理可知：这个方程只有gcd（a，p）=1的时候才有解，所以，gcd=1是求逆元的前提条件。

然后我们直接套exgcd（a，p，x，y）即可
虽然求出来的是a的一个逆元，但是我们由拓展欧几里得可以求出通式，x=x1+k*lcm（a，p）/a   （k可以取任意整数）

只要不断+模数p就可以求出最小正整数解

2，费马小定理：如果p是质数，且gcd（a，p）=1，a^(p-2)是a的一个乘法逆元。

那么如何求a^(p-2)?
我们可以用到快速幂的方法，

s=1，t=p-2   y=a
while（t！=0）{
     if（p&1==1）s=s*y
     y*=y；
     t/=2;
}

线性递推求逆元

假如给你1~n个数，让你求所有整数在模p意义下的乘法逆元。你应该怎么办？（n<=1e6)

如果你每次都用exgcd或者费马小定理+快速幂这题是肯定是会超时的，所以我们只能用线性优化了。

只能使用递推的方式来解决这道题

那么我们必须找到递推的式子

假设 inv（i）是i在模意义下的逆元（记住板子即可）

设p=i*q+r，其中q=【p/i】（整除），r=p%i。
第一个式子：p=i*q+r

在模意义下可以得到这样的式子：
 i*q+r == 0 （mod p）

变形为： i ==  -r/q  （mod p）

等价于：i== -r * inv（q）  （mod p）

两边取倒数：（整数的倒数来表示逆元函数）

1/i == -1/r   *   q

inv（i） == -inv（r）*q == -inv（r）*【p/i】；

因为 r=p%i，所以r是一定小于当前的i的，怎么求inv（r）

由于我们是递推求逆元，当求到i时，说明i-1，i-2,......1 都求出来了。

所以我们只要注意边界 inv（1） =1即可

但是还是有一个问题，就是，这样求出来的逆元，有些是负数的，如果我们要求逆元的最小正整数应该怎么办？
那也好办，不断在其后面加上p就可以了，当逆元大于0，退出循环。

上代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;
typedef long long LL;
const int N = 3e6 + 7;
LL inv[N];
int main()
{LL n,p;cin >> n>>p;inv[1] = 1;for (int i = 2; i <= n; i++) {LL q = p / i;LL r = p % i;inv[i] = (-q * inv[r]%p)%p;while(inv[i]<0)inv[i]+=p;}for (int i = 1; i <= n; i++)cout << inv[i] << '\n';
}