解一组同余方程

{x≡a1(mod  m1)x≡a2(mod  m2)⋯x≡ak(mod  mk)\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

设 m1,m2,m3⋯mkm_1,m_2,m_3\quad\cdots\quad m_k 两两互质，

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

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

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

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

最小正整数解即为累计的答案（若要其他解可以不断加 ∏i=1kmi\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;

}

时间复杂度 Θ(nlog⁡n)\Theta(n\log n)

Type2

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

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

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

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

x=ai+mixix=a_i+m_ix_i

的形式

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

mixi+mjxj=aj−aim_ix_i+m_jx_j=a_j-a_i

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

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

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

得到的式子即为

x≡x′(modlcm(mi,mj))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;

时间复杂度 Θ(nlog⁡n)\Theta(n\log n)

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

QwQQwQ