现在的位置: 首页 > 综合 > 正文

数论/中国剩余定理

2018年10月25日 ⁄ 综合 ⁄ 共 518字 ⁄ 字号 评论关闭

中国剩余定理:

设总数为n,模ax,模by,模cz,若已知xyz,让求出最小的n

n=(x*a1+y*b1+z*c1)%d;

其中a1=y*z中的倍数中模a等于1的最小的数;

b1=x*z中的倍数中模b等于1的最小的数;

c1=x*y中的倍数中模c等于1的最小的数;

d=a,b,c的最小公倍数。

中国剩余定理原版之韩信点兵版:

传说韩信点兵时发明的算法。设士兵总数为n,模3得x,模5得y,模7得z,若已知x,y,z,让求出最小的n。

则n=(x*70+y*21+z*15)%105;

可以用下面的小诗帮助记忆。

三人成行七十稀;70为35(5×7)的倍数中模3等于1的最小的数;

五树梅花廿一枝;21为21(3×7)的倍数中模5等于1的最小的数;

七子团圆月正半;15为15(3×5)的倍数中模7等于1的最小的数;

除百零五便得之。105为3,5,7的最小公倍数。

 

如果不是3,5,7用同样的方法求解。

题目poj 1006

设第n天同时出现3个巅峰,有

n=(p*5544+e*14421+i*1288)%21252;

题目要求n-d,这里只需要注意可能d>n,因为他们3个同时出现的一个周期是21252,所以当d>n,那么n-d+21252就是所求。

 

【上篇】
【下篇】

抱歉!评论已关闭.