【模板】扩展中国剩余定理(EXCRT)

题目

洛谷P4777扩展中国剩余定理(EXCRT)

题解

由于mi之间不保证互质,所以Mi和mi也不一定互质,所以不能用exgcd求Mi(mod mi)的逆元。考虑用数学归纳法,假设已经求出了前i个方程构成的方程组的一个解X0,通解为X。

考虑第(i+1)个方程,设前(i+1)个方程构成的方程组的一个解为x’。

要找出一个k,使x’满足所有条件,成为新解。将上式变形,就成了一个以k为未知数的线性同余方程,可以用exgcd判断方程是否有解,并进一步求出解。

求M时,为了防止溢出,可以求所有mi的最小公倍数。

此题数据较大,即使是在模意义下,乘法操作时仍然可能溢出,所以要使用“快(龟)速乘”。类似快速幂的原理,将乘法中的其中一个数二进制分解,然后逐步相乘。

代码

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments