中国剩余定理

给出条件:
一:m1,m2...mk两两互质
二:


....

求x


(与mi互质)(用exgcd求mi的逆)
所以可求 Mi模mi的逆(用exgcd求Mi*infMi=1(mod p))
证明上式:题意有 x=a1(mod m1)
按上式:x=a1*M1*infM1=a1 (mod m1) (其余的含m1被约掉)
全部评论

相关推荐

在写周报的打工人很独...:这个笔试昨天晚上做了一下,真难啊,前后端,ai全有
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务