中国剩余定理之c语言实现.txt

来自「c语言的一些常见的算法以及思考和改进的文章,写的很不错,花费了很大的精力从网络了」· 文本 代码 · 共 39 行

中国剩余定理之C语言实现[原创] 
/*
   中国剩余定理：设m1,m2,...mn是两两互素的正整数，
则x≡bi mod mi(i=1,2,...n)在模m1m2m3...mn下有唯一解。
这M=m1m2....mn，Mj=M/mj，且Mjyj≡1 mod mj(j=1,2,...n),
则x=b1M1y1+b2M2y2+...+bnMnyn mod m1m2m3...mn即是符合条件的解。
*/
#define N 3

＃i nclude <conio.h>

long shengyu(int b[],int m[])
{/*正常来讲，应首先判断是否有解，即m[N]中的数是否互素，朋友们可以自己加上*/
  long product=1;
  long x=0;
  int  M[N],y[N],i;
  for(i=0;i<N;i++)
     product*=m[i];
  for(i=0;i<N;i++)
     M[i]=product/m[i];
  for(i=0;i<N;i++)
  {
     int j=1;
     while((M[i]*j)%m[i]!=1)
          j++;
     y[i]=j;
  }
  for(i=0;i<N;i++)
    x+=b[i]*M[i]*y[i];
  return x%product;
}

void main()
{
  int b[N]={1,2,3},m[N]={2,3,5};
  printf("\nThe result is:\n%ld\n",shengyu(b,m));
}