测试数据 求逆元

71 32

线性求

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
const int maxn=3e6+10;
long long inv[maxn];
int n,p;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9' || ch<'0'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}return x*f;
}
int main(){
	n=read(),p=read();inv[1]=1;
	for(int i=2;i<=n;++i){
		inv[i]=(p-p/i)*inv[p%i]%p;
	}printf("%lld",inv[n]); 
	return 0;
}

输出：0

扩展欧几里德

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
const int maxn=3e6+10;
long long inv[maxn];
int n,p;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9' || ch<'0'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}return x*f;
}
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int temp=x;
	x=y;
	y=temp-(a/b)*y;return d;
}
int main(){
	n=read(),p=read();
	int x,y;
	int d=exgcd(n,p,x,y);
	cout<<(x+p)%p<<endl;
	return 0;
}

输出：23

我知道扩欧算出来是对的，那么为什么线性推是错的