P3811 【模板】乘法逆元

Aimee

模板题也

关于递推式的证明

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int n,m;
int inv[3000005];
signed main(){
	scanf("%lld%lld",&n,&m);
	inv[1]=1;
	cout<<1<<endl;
	for(int i=2;i<=n;++i){
		inv[i]=(int)m-(m/i)*inv[m%i]%m;
		printf("%lld
",inv[i]);
	}
	return 0;
}