〇、前言 ¶
今日,余见困于问 ABC193E 者,甚急,故作此文以记之。
壹、问题描述 ¶
求解同余方程组:
\[\begin{cases} x\equiv r_1\pmod{m_1} \\ x\equiv r_1\pmod{m_1} \\ x\equiv r_1\pmod{m_1} \\ \cdots \\ x\equiv r_n\pmod{m_n} \\ \end{cases} \]保证 \(\forall i\neq j,\gcd(m_i,m_j)=1\),求一个 \(x\) 满足以上要求。
在知乎的这篇中讲得比较详细,思路是转化为子问题。
总结一下他的思路,大致就是将 \(x\) 转化为求解 \(x_1,x_2,...,x_n\),使得
\[x_i\equiv r_i\pmod {m_i}\;\and\; \forall j\neq i\; {\rm{s.t.}}\;m_j|x_i \]然后 \(x=\sum x_i\),但是找到 \(x_i\) 也比较困难,我们就再转化一下,找 \(y_i\) 使得
\[y_i\equiv 1\pmod {m_i}\;\and\; \forall j\neq i\; {\rm{s.t.}}\;m_j|y_i \]而这实际上就是除了 \(m_i\) 以外所有 \(m_j\) 的乘积,乘以它们的乘积的逆元,这就是 \(y_i\).
最后就有
\[x=\sum_{i=1}^n x_i=\sum_{i=1}^n r_iy_i \]若用数学语言表达,那么就是
\[M\overset\Delta=\prod_{i=1}^nm_i \\ x=\sum_{i=1}^nr_i{M\over m_i}\left[\left({M\over m_i}\right)^{-1}\right]_{m_i}\pmod M \]其中 \(\left[x^{-1}\right]_{y}\) 表示 \(x\) 在 \(y\) 意义下的逆元。
代码就不实现了。
贰、拓展中国剩余定理 ¶
考虑条件更苛刻,对于问题
\[\begin{cases} x\equiv r_1\pmod{m_1} \\ x\equiv r_1\pmod{m_1} \\ x\equiv r_1\pmod{m_1} \\ \cdots \\ x\equiv r_n\pmod{m_n} \\ \end{cases} \]不保证 \(\forall i\neq j,\gcd(m_i,m_j)=1\),求一个 \(x\) 满足以上要求。
没有互质条件,无法使用之前的方法求解。
考虑将两个同余方程组进行合并。
如果对于前 \(i-1\) 个方程组,我们得到其解为 \(x\),且前 \(i-1\) 个 \(m\) 的最小公倍数为 \(M\),考虑将第 \(i\) 组合并进去。
首先,对于前 \(i-1\) 组,我们显然有通解 \(x'=x+tM,t\in Z\),现在,我们就相当于解决以下问题:
\[\begin{aligned} &x+tM\equiv r_i\pmod {m_i} \\ \Leftrightarrow\; &tM\equiv r_i-x\pmod{m_i} \\ \Leftrightarrow\; &tM+qm_i=r_i-x \end{aligned} \]使用 \(\rm exgcd\) 可对该不定方程求解。
显然,当 \(\gcd(M,m_i)\nmid (r_i-x)\) 时,该方程无解,若得到 \(t\),注意更新
\[x\leftarrow x+tM \\ M\leftarrow \text{lcm}(M,m_i) \]这样便可得到答案。
至于最开始的解?显然,\(M=m_1,x=r_1\) 即可。
叁、Excrt の 参考代码 ¶
ll exgcd(ll a, ll b, ll& x, ll& y){
if(b==0) return x=1, y=0, a;
ll ret=exgcd(b, a%b, y, x);
y-=(a/b)*x; return ret;
}
/**
* @brief chinese remainder theorem
* @param r remainder
* @param m divisor
* @return the minimum number which qualify all the condition, if not exist, return -1
*/
inline ll crt(vector<int>r, vector<ll>m){
assert(r.size()==m.size());
int n=r.size();
ll lcm=m[0], ans=r[0], x, y, tmp, d;
for(int i=1; i<n; ++i){
tmp=((r[i]-ans)%m[i]+m[i])%m[i];
d=exgcd(lcm, m[i], x, y);
if(tmp%d!=0) return -1;
x=(x*tmp/d)%(m[i]/d);
ans+=x*lcm;
lcm=lcm*m[i]/d;
ans=(ans%lcm+lcm)%lcm;
}
return ans;
}