首页 > 代码库 > 中国剩余定理(自己)
中国剩余定理(自己)
数论的题目中会涉及一些中国剩余定理的问题,会给你一些互质的数,比如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 );
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。