inverse.cpp

孙子定理及求模求逆算法

#include<iostream.h>
int MOD(int x, int n){//求模运算，在Zn范围内
	int result=x%n;
	if (result<0)
		result=result+n;
	return result;
}
int Inverse(int a,int n){//求逆运算，存在则返回，不存在则返回0
	int r_2=a,r_1=n,r=1;
	int q,w;
	int u_2=1,u_1=0,u,v_2=0,v_1=1,v;
	while(r)
	{
		
		q=r_2/r_1;r=r_2-q*r_1;
		if(r)
		{u=u_2-q*u_1;v=v_2-q*v_1;r_2=r_1;r_1=r;
		u_2=u_1;u_1=u;v_2=v_1;v_1=v;}
	}
    w=r_1;
	if(w==1)return MOD(u,n);
	else return 0;
}
int sunzi(int* a,int* m,int n){//孙子定理
	int x=1,result=0,i;
	int* M=new int[n];
	int* G=new int[n];
	for(i=0;i<n;i++)
		x=x*m[i];
	for(i=0;i<n;i++){
		M[i]=x/m[i];
		G[i]=Inverse(M[i],m[i]);
	}
    for(i=0;i<n;i++)
		result+=M[i]*G[i]*a[i];
	result=MOD(result,x);
	delete []M;
	delete []G;
	return result;
}
void main(){//主函数
	int a[3]={2,3,2};
	int m[3]={3,5,7};
	cout<<sunzi(a,m,3)<<endl;
}