P3811 【模板】乘法逆元

给定n,p求1~n中所有整数在模p意义下的乘法逆元。

T两个点的费马小定理求法：

code：

#include <iostream>

#include <cstdio>

using namespace std;

#define int long long

int n,mod;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int ksm(int a,int b){

	int re=1;

	while(b){

		if(b&1)re=re*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return re;

}

signed main(){

	n=read(); mod=read();

	for(int i=1;i<=n;i++){

		printf("%lld\n",ksm(i,mod-2));

	}

}

线性求逆元式子：

inv[i]=(mod-mod/i)*inv[mod％i]％mod

code:

#include <iostream>

#include <cstdio>

using namespace std;

#define int long long

int n,mod;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int inv[3000017];

signed main(){

	n=read(); mod=read();inv[1]=1;puts("1");

	for(int i=2;i<=n;i++){

		printf("%lld\n",inv[i]=(mod-mod/i)*inv[mod%i]%mod);

	}

}