AC » Archive » 大数取余(二) 剩余定理

大数取余(二) 剩余定理

四月 7th, 2011 › 模板 › ben1222 ›

上次的文章中主要说的都是各种运算对应的取余的计算方式
但是没有提到关于模数的优化

计算a%m时,如果m能小一些的话,通常计算起来就会方便很多
比如可以用更小的内存进行预处理,或者找到循环节之类的很好的东西

在做了Project Euler 330后深刻的感受到了这点…
题中要求对77777777取模,可以看到这和平时常用的对某个质数取模不同,这回是个合数
77777777 = 7 * 11 * 73 * 101 * 137
在过去,看到要对合数取模感觉就不太爽,因为有些性质只有质数才能用,比如组合数取模

这题搞了很久没有进展才想起来还有个剩余定理
对于两两互质的一组整数{m₁,m₂,…,m_n}
设m=m₁*m₂*…*m_n, 也就是m是这组数的乘积
设b_i=a%m_i, 也就是b_i是a对m_i取余的余数
已知{b₁,b₂,…,b_n}的话,可以求得a%m
具体做法是找到c_i=(m/m_i)*k使得c_i%m_i==1
因为两两互质,所以k只要枚举1~m_i-1就一定能找到满足条件的c_i
最后a%m=sum{c_i*b_i}%m