解一组同余方程

$$
\left{\begin{array}{c}x\equiv a_1(\mod m_1)\x\equiv a_2(\mod m_2)\\cdots\x\equiv a_k(\mod m_k)\\end{array}\right.
$$

Type1

设 $m_1,m_2,m_3\quad\cdots\quad m_k$ 两两互质，

那我们考虑对他们一一解决

前置小提示：由于所有的模数两两互质，所以最终式的模数即可为$\prod_{i=1}^{k}{m_i}$

对于任意一个式子 $j$ 我们想让他在其他式子不受影响的同时被满足，那便需要累计的答案加上的数是其他式子模数的倍数，同时还要使得此式变得成立，

那这个加数必然含有一个因子为 $\cfrac{\prod_{i=1}^{k}{m_i}} {m_j}$ ,用 $exgcd$ 求其在模 $m_j$ 下的逆元，再把他们和 $a_j$ 相乘，便可得到这个加数。

最小正整数解即为累计的答案（若要其他解可以不断加 $\prod_{i=1}^{k}{m_i}$ 来得到）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#define ll long long 

ll a[K],m[K],k,ans,M=1,x,y;

for(int i=1;i<=k;i++){

    M*=m[i];

}

for(int i=1;i<=k;i++){

    ans=(ans+(M/m[i]*a[i]/exgcd(M/m[i],m[i])*x)%M)%M;

}

时间复杂度 $\Theta(n\log n)$

Type2

我们现在来看一下更平凡的情况：

模数不一定两两互质，在这种情况下方程组不一定有解

我们可以把式子两两合并，

设最终的解为$x$,我们可以把式子转化为

$$
x=a_i+m_ix_i
$$

的形式

每次取出其中的两个合并，便等价于求解

$$
m_ix_i+m_jx_j=a_j-a_i
$$

此时用 $exgcd$ 求逆元的同时可以判断有无解

把得到的解代回原式 $(x=a_i+m_ix_i)$ 得到的 $x$ 即为新方程的余数，下面记作 $x’$

新方程的模数为 $lcm(m_i,m_j)$

得到的式子即为

$$
x\equiv x’\pmod {lcm(m_i,m_j)}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#define ll long long 

ll a[K],m[K],k,ans,x,y,nowm,nowa;

nowm=m[1],nowa=a[1];

for(int i=2;i<=k;i++){

    if((a[i]-nowa)%exgcd(nowm,m[i],x,y)){

        cout<<-1<<endl;

        return 0;

    }

    nowa+=nowm*x;

    nowm=lcm(nowm,m[i]);

}

cout<<nowa<<endl;

时间复杂度 $\Theta(n\log n)$

番外：南外讲座的大佬说这个貌似模意义下的拉格朗日插值

$QwQ$