洛谷模板EXCRT
发布时间
阅读量：
阅读量
1、 中国剩余定理（适用于n个同余方程，其前提条件为m[1]至m[n]之间两两互质）
x=r[1](mod m[1])
x=r[1](mod m[2])
…
x=r[n](mod m[n])
2、 扩展中国剩余定理（适用于n个同余方程，其中m[1]至m[n]之间不强制要求两两互质）
x=r[1](mod m[1])
x=r[1](mod m[2])
…
x=r[n](mod m[n])
考虑签名两条方程， x=r[1](mod m[1])， x=r[1](mod m[2])
转化为不定方程 x = m[1] * p + r[1] = m[2] * q + r2
那么 m[1] * p - m[2] * q = r[2] - r[1]
gcd(m[1], m[2]) 整除 r[2] - r[1] 说明有解，否则无解
由扩展欧几里得算法求出方程 m[1] * p - m[2] * q = r[2] - r[1] 一组特解，
再得到通解，最后这两条方程等价合并为一个新的方程式
x = r(mod m), 再用这新的方程 去和第 3条方程联解，以此类推，
n个同余方程，合并 n - 1
全部评论 (0)
还没有任何评论哟~