模线性方程组 --- 大数翻倍法
模板题 ： hdu 3579
这是钟神讲的方法。好处是好写，并且模数不互质也同样可以用。
依然是对模线性方程组挨个合并。
x ≡ A1 (mod M1)
x ≡ A2 (mod M2)
不妨令M1 > M2 ， 令 MM=lcm(M1,M2)。
由第一个模方程得 ： x = M1 * k1 + A1
容易证明，k1是小于 M2的。于是我们枚举k1 ， 判断x是否满足第二个模方程即可。
考虑复杂度，我们每次合并的复杂度是O(Mi)，由于一般题目 ∏ Mi 是不超过 10^18 次方的，当方程组个数多于两个时 ， 我们的复杂度就不会超过O(10 ^ 6) ， 可以过。
upt ： 想了一下 感觉貌似复杂度有问题 ？ 明天再去问问钟神
评论(3)