[NOI2018]屠龙勇士

题目链接

题目大意

中国剩余定理"裸题"

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

中国剩余定理(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)$ 如果左式无法整除,则无解

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注