首页 > 代码库 > 中国剩余定理(自己)

中国剩余定理(自己)

    数论的题目中会涉及一些中国剩余定理的问题,会给你一些互质的数,比如a, b, c. 

然后呢,有一个n,说这个n对a取余为dd,  n对b取余为ff,  n对c取余为gg.   现在让你来

计算这个n的最小数值。

      解法如下:

      x = (a 与 b 的某个公倍数) % c = = 1;

      y = (b 与 c 的某个公倍数) % a = = 1;

      z = (a 与 c 的某个公倍数) % b = = 1;

  n =  (   x*gg  +  y*dd  + z*ff  ) % (  x*Y*z ) ;

为了避免特殊数据( 比如出现 负值 ),可以改写成这样:

 n =  (  x*gg + y*dd + z*ff  +x*Y*Z ) % ( x*y*z );