洛谷P1082题解：https://www.luogu.org/blog/costudy/solution-p1082
知识：
费马小定理：若 p 是质数，则对于任意整数 a ，有 ap = a (mod p)，也就是ap-1=1 (mod p)。
Bézout定理：对于任意整数 a , b ，存在一对整数 x , y ，满足 ax+by=gcd(a,b) 。
Bézout定理计算x，y的方法：拓展欧几里得算法：
代码如下（两种办法，更喜欢2）
inline int exgcd(int a,int b,int &x,int &y){ if(b==0) {x=1,y=0;return a;} int d=exgcd(b,a%b,x,y); int z=x;x=y;y=z-(a/b)*y; return d; } long long x, y; inline void exgcd2(long long a,long long b){ if(b==0){ x=1,y=0; return; } exgcd(b,a%b); long long xx=x; x=y; y=xx-a/b*y; }
证明在开头题解里。
乘法逆元：如果 ax≡1 (mod p), 且 gcd(a,p)=1（a与p互质)，则称a关于模p的乘法逆元为x。
求法：费马小定理，拓展欧几里得，线性递推。
线性递推代码如下（1到n关于mod p的乘法逆元）洛谷p3811：
#include<bits/stdc++.h> using namespace std; const int maxn=3*1e6+10; int inv[maxn],n,p; int main() { scanf("%d%d",&n,&p); inv[1]=1; printf("1\n"); for(int i=2;i<=n;i++){ inv[i]=(long long)(p-p/i)*inv[p%i]%p; printf("%d\n",inv[i]); } return 0; }
原文：https://www.cnblogs.com/ChrisKKK/p/10828850.html