【模板】模意义下的乘法逆元 - 洛谷

费马太典了。

ax + py = 1 (mod p)

所求 x 即逆元 exgcd.

递推:

转自zjp_shadow

由整除性得 -p/i = p-p/i;

故有代码（只用了递推

#include<bits/stdc++.h>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y){//	求解 ax + by = gcd(a,b)if(!b){x = 1,y = 0;return a;}int g = exgcd(b,a%b,x,y);int temp = x;x = y;y = temp-a/b*y;return g;
}
int niyuan(int a,int p){//求 a 在 mod p 意义下的逆元int xx = 0,yy = 0;int g = exgcd(a,p,xx,yy);return (xx+p)%p;
}
bool liEu(int a,int b,int &x,int &y,int c){//求解ax + by = cint g = exgcd(a,b,x,y);if(c % g != 0)return 0;//无解int k = c/g;x*=k;y*=k;return 1;
}
int inv[3000100];
signed main(){ios::sync_with_stdio(0);int n,p;cin>>n>>p;inv[1] = 1;cout<<1<<endl;for(int i = 2;i <= n;i++){inv[i] = (p-p/i)*(inv[p%i]);inv[i]%=p;cout<<inv[i]<<'\n';}return 0;
}