线性同余方程组的合并

类似于

\(\)

$$a_ix\equiv b_i\mod m_i$$

的方程组就是线性同余方程组
根据同余的可加性,可令

$$x\equiv B \mod lcm(m_i) $$

所以答案就转化为了求B和lcm

$$a_1x \equiv b_1 \mod m1$$

$$x\equiv (b_1/\gcd(a_1,m_1))*(a_1^{-1}/gcd(a_1,m_1)) \mod (m_1/gcd(a_1,m_1))$$

$$x \equiv B_1 \mod m1$$

$$x=B_1+m_1*t $$此时的m1*t是未知的

带入第二个方程,并整理

$$a(B_1+m_1t) \equiv b_2 \mod m_2$$

$$am_1t \equiv b_2-aB_1 \mod m_2$$

解出t

$$t \equiv (b_2-aB_1)/gcd(am_1,m_2) * (am_1)^{-1}/gcd(am_1,m_2) \mod (m_2)/gcd(am_1,m_2)$$

把t带入

$$x=B_1+m_1*t $$

\(此时的x在\mod m1和\mod m2的意义下都是成立的。B1_+m_1*t变成了新的B_2\)

$$x\equiv B_2 \mod lcm(m_1,m_2) $$

$$x=B_2+lcm*t$$

再带入第三个方程即可向下合并

//返回一个b,m对 
pair<int, int> inner_congruence(const vector<int> &A,const vector<int> &B,const vector<int> &M)
{
	int x=0,m=1;
	for(int i-9;i<A.size();i++)
	{
		int a=A[i]*m,b=B[i]-A[i]*x,d=gcd(a,M[i]);
		if(b%d!=0) return make_pair(0,-1); //无解
		int t=b/d*mod_reverse(a/d,M[i]/d)%(M[i]/d);
		x+=m*t;
		m*=M[i]/d; 
	}
	return make_pair(x%m,m);
}

 

发表评论