[编程笔记]-Chinese_Remainder_Theorem中国剩余定理

前言

刚打完cf，当前时间1:04。

链接就不放了，照着标签去找吧，总能找到的。

解决

方案一

互质

若m₁, m₂, m₃, …, m_k两两互质

满足如下条件：

x≡a₁(mod m₁)
x≡a₂(mod m₂)
x≡a₃(mod m₃)
…
x≡a_k(mod m_k)

设M=m₁m₂m₃…m_k

M_i=M/m_i，就是除了m_i外所有m的乘积。

因为所有m两两互质，所以M_i与m_i互质。

所以，我们就可以求出M_i^-1(mod m_i)，因为互质，所以存在。由于m_i不一定是质数，这里使用拓展欧几里得算法。

这里我们先给出x，然后再解释：
x=a₁M₁M₁^-1+a₂M₂M₂^-1+a₃M₃M₃^-1+…+a_kM_kM_k^-1

为什么呢？根据乘法逆元的定义，可以得到：M_iM_i^-1≡1(mod m_i)

然后，除了第i项之外，其它项内都含有m_i这个因数，模m_i都为0。

所以最后模的结果就是a_i%m_i。

满足条件。

不互质

M是所有m_i的最小公倍数。

然后都一样。

方案二

代码

明天再补，我真不想变成国家一级保护废物。

两点睡，七点起，笑死根本睡不醒。

暂停数论更新，给自己放个假，去动态规划了~

完结撒花o(￣︶￣)o