shengyu.cpp

经典的中国剩余定理求解程序

#include<iostream.h>
#include<math.h>
//输入方程组
void input(int b[],int m[],int n)
{for(int i=1;i<=n;i++)
{ cout<<"请输入数b"<<i<<"和"<<"m"<<i<<endl;
  int temp1,temp2;

  cout<<"b"<<i<<"=";
  cin>>temp1; 
  b[i]=temp1;

  cout<<"m"<<i<<"=";
  cin>>temp2; 
  m[i]=temp2;
}

}

void qiujie(int b[],int m[],int n)   //mm[]即是M[]，mmm[]即是M'[]
{ int mm[100];
  int s=1;
  for(int i=1;i<=n;i++)
   s*=m[i];
  cout<<s<<endl;
  for(int j=1;j<=n;j++)
	  mm[j]=s/m[j];

  int mmm[100];
  for(int h=1;h<n+1;h++)
   for(int p=1;p<m[h];p++)
     if((p*mm[h])%m[h]==1)
        mmm[h]=p;

  cout<<"结果为：x=";
  for(int l=1;l<n+1;l++)
  { cout<<mmm[l]<<"*"<<mm[l]<<"*"<<b[l]<<"";
    if(l!=n)
	   cout<<"+";
  }
  cout<<"(mod"<<s<<")"<<endl;
}

void main()
{ int b[100],m[100];
  cout<<"请输入方程组数：\n";
  int n;
  cin>>n;
  input(b,m,n);
  qiujie(b,m,n);
}