题目链接

题目大意

中国剩余定理"裸题"

这就当是我对(扩展)中国剩余定理的总结吧,还有好多细节的方面的归纳.

中国剩余定理(CRT)

用途就是解出这类问题
我们可以先考虑模数两两互质的情况下的做法.
我们想构造出一个合式使得 x= r_1+r_2+r_3+\cdots +r_n 其中 m_i 可以整除除了第i项的其他项

于是我们可以通过一下做法达到我们的目的:
我们先开一个变量lcm来存它们的最小公倍数(如果两两互质,结果显然是它们的乘积)
然后开一个数组 M_i=\frac{lcm}{m_i} 就是把每项的模数给剔除出来
设 t_i 是 M_it_i\equiv1\ (mod\ m_i)的一个解.

于是答案就是 ans=\displaystyle\sum_{i=1}^na_iM_it_i
通解就是 ans+klcm 其中k是整数

扩展中国剩余定理(exCRT)

这才是大多数题目真正会用到的算法,因为它不必要求模数两两互质,我们还是可以通过刚刚的想法来做
假设前 k-1 个方程的解是 x , 前 k-1 的lcm还是用 lcm 表示
则前 k-1 个方程的通解是 x+im 其中i是整数

现在求第 k 个方程,我们需要一个整数t,满足 x+tm\equiv a_k\ (mod\ m_k)
等价于 tm\equiv a_k-x\ (mod\ m_k)

答案更新为 x=x+tm

回到这道题上来

不难发现,这道题其实就是要求如下的线性同余方程组
\begin{cases}x\equiv a_1\times ATK_1^{-1}\ (mod\ p_1)\x\equiv a_2\times ATK_2^{-2}\ (mod\ p_2)\ \cdots\ x\equiv a_n\times ATK_n^{-n}\ (mod\ p_n) \end{cases}

至于每一项的ATK,可以用multiset处理出来(想快一点手写平衡树)

但是我们发现,如果ATK不与模数互质的话,它的逆元是不好求的

同余的消去律:
如果 ab\equiv ac\ (mod\ n),而 d=gcd(a,n) ,那么a可以在同余式两边消去
b\equiv c\ (mod\ \frac{n}{d})
特别是当a和n互质,ab\equiv ac\ (mod\ n) 可推到 b \equiv c\ (mod\ n)

根据模运算的消去律,我们可以去掉最大公因数 gcd(ATK_i*lcm,p_i) 如果左式无法整除,则无解

代码