modulus CRT

(吐槽)额..CRT本来就是modulus的么..

CRT是可以每次加一个条件的(当然要保证coprime)

那么我们考虑

• x=a (mod p1)
• x=b (mod p2)

这样的话我们知道

• x=a+p1y (mod p1p2)

我们只需要知道这里y的值,那么我们并不需要知道p1完整的值,只需要知道p1模p2意义下的值就可以了因为两边模p2

• b=a+p1*y (mod p2)
• b-a=p1*y (mod p2)
• y=(b-a)*inv(p1) (mod p2)

然后注意到这里y<p2,a<p1,那么x<p1*p2,那么也就是最小正整数解不需要加减和取模就能通过这些y算出来,那么也就可以把这些y拿去在模其它数意义下算一遍.

然后就可以(n/lg n)^2地做掉PE552.