数论/中国剩余定理

2019-04-13 12:49发布

站内文章 / 模拟电子
15242 0 1601
中国剩余定理: 设总数为n，模a得x，模b得y，模c得z，若已知x，y，z，让求出最小的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就是所求。  

热门文章