#P1052. 乘法逆元

发布时间 2023-12-19 14:36:56作者: yufan1102

image
image

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p;
int gcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int d=gcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
int inv(int a,int m){
	int x,y;
	gcd(a,m,x,y);
	return (x%m+m)%m;
}
void solve(){
	cin>>n>>p;
	for(int i=1;i<=n;i++){
		int ans=inv(i,p);
		cout<<ans<<"\n";
	}
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	//cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
}