扩展中国剩余定理求问

P4774 [NOI2018] 屠龙勇士

也就是先得到第 $i$ 个的同余方程的解: $$x\equiv q_i\pmod {p_i}$$ 满足: $$b_ix\equiv a_i\pmod {p_i}$$ 因为楼主太困了所以先去睡觉了,明天早上看到会一一感谢的~
by __gcd @ 2021-03-19 23:42:10


此贴结了
by __gcd @ 2021-03-20 11:01:05


@[__gcd](/user/149192) 能问一下为什么会导致漏解吗?![kl](https://cdn.luogu.com.cn/upload/pic/62226.png)
by GBLoi @ 2021-04-07 13:00:00


@[GBLoi](/user/234913) 因为 $b_ix\equiv a_i\pmod {p_i}$ 是等价于 $x\equiv s\pmod {\dfrac{p_i}{\gcd(b_i,p_i)}}$ 的,其中 $s$ 是同余方程的最小非负整数解。 漏解是因为把上面等价同余方程的模数搞成了 $p_i$。
by __gcd @ 2021-04-07 13:14:24


@[__gcd](/user/149192) 谢谢!
by GBLoi @ 2021-04-07 13:34:33


|