exgcd 合并同余方程组

\begin{cases} x\equiv a_1\ \left( \text{mod\ }p_1 \right) \\ x\equiv a_2\ \left( \text{mod\ }p_2 \right) \\ x\equiv a_3\ \left( \text{mod\ }p_3 \right) \end{cases}

以前做 CRT 一直是用那个构造性的暴力式子 ( q_{ji} 表示 p_jp_i 下的逆元 ):

x \equiv \sum_{i=1}^{n}{( a_i \cdot \prod_{j \ne i}{(p_j \cdot q_{ji})} )} \mod {(\prod_{i=1}^{n}{p_i})}  

(不过这个式子无比好记&&好用)

现在我们来考虑用 exgcd 去合并 CRT 方程。

直接先考虑俩方程

x \equiv a_1 \mod p_1

x \equiv a_2 \mod p_2

搞成某种加法形式

x + y_1p_1 = a_1

x + y_2p_2 = a_2

减一下

y_1p_1-y_2p_2=a_1-a_2

我习惯把减号改成加号

y_1p_1+y_2p_2=a_1-a_2

 

直接暴力 exgcd 这个方程,无解的条件是当且仅当 \gcd(p_1,p_2) \nmid (a_1-a_2)

求出解后记得 \mod p_2 ,这相当于合并方程了(注意 CRT 方程组最后的解的模数是 \prod_{i=1}^{n}{p_i} 。)

然后回代出第一个方程的特解 x_1 

x_1 = a_1-y_1p_1

(代码上的一个小技巧:因为这特解和 a_1相等同余的并且我们还要合并其他方程,所以直接更新 a_1

然后我们考虑通解是这玩意 : 

x \equiv x_1 \mod \mathrm{lcm}(a_1,a_2)

所以记得变一下模数。(可以维持那个特解不用变,因为在 \mathrm{lcm} 下是同余的)

大概的(伪)代码:

 

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据