sun.cpp

一个能解中国古代算数定理（即孙子定理）的小程序

#include<iostream>
using namespace std;

long int limod(long int a,long int b,long int m)
{
	long int result;
	for(result=0;result<=m-1;result++)
		if((a*result)%m==b)
			return result;
	return -1;
}

long int leave(long int *p,long int *m,long int n,long int &pum)
{
	long int i,j;
	long int result;
	long int temp;
	result=0;
	pum=1;
	for(i=1;i<=n;i++)
	{
		temp=1;
		for(j=1;j<=n;j++)
			if(j!=i)
				temp*=m[j];
		result+=temp*limod(temp,p[i],m[i]);
		pum=pum*m[i];
	}
	result=result%pum;
	return result;

}

void main()
{
	long int *p,*m;
	long int n,pum;
	char ch;
	long int result;
	cout<<"请输入同余方程组个数:";
	cin>>n;
	m=new long int[n+1];
	p=new long int[n+1];
	for(long int k=1;k<=n;k++)
	{
		cout<<"请输入第"<<k<<"对除数与余数:";
		cin>>m[k]>>p[k];
	}
	cout<<"所求问题是:"<<endl;
	for(k=1;k<=n;k++)
	{
		cout<<"x="<<p[k]<<" mod("<<m[k]<<")"<<endl;
	}
	result=leave(p,m,n,pum);
	cout<<"所求解为:x="<<result<<"mod("<<pum<<")"<<endl;
	cin>>ch;
}