拓展中国剩余定理

因为此算法基于构造法，下面给出构造流程

推导思路

1.首先从最简单的部分入手，只考虑两个方程的情况，并将其变形为右式

$$\begin{matrix} &(S): \left\{ \begin{matrix} x\equiv c_1\ (\ mod\ m_1) \\ x\equiv c_2\ (\ mod\ m_2) \\ \end{matrix} \right.\\ &\Downarrow \\ &\left\{ \begin{matrix} x=c_1+k_1*m_1 \\ x=c_2+k_2*m_2 \\ \end{matrix} \right. &k\in Z \end{matrix}$$

2.联立方程并移项

$$c_1+m_1k_1=c_2+m_2k_2 \\ \Downarrow\\ m_1k_1-m_2k_2=c_2-c_1\\$$

由不定方程可知，此方程有解充要条件为：$gcd(m_1,m_2)|(c_2-c_1)$

3.对 2 中方程进行变换，通过同余的性质消去 $k_2$

$$\frac{m_1k_1}{gcd(m1,m2)}=\frac{c_2-c_1}{gcd(m_1,m_2)}-\frac{m_2k_2}{gcd(m1,m2)} \\ \Downarrow \\ \frac{m_1k_1}{gcd(m1,m2)}\equiv\frac{c_2-c_1}{gcd(m_1,m_2)}(\ mod\ \frac{m_2}{gcd(m1,m2)})$$

4.上式同时除以 $\frac{m_1}{gcd(m_1,m_2)}$，得到下式

$$k_1=inv(\frac{m_1}{gcd(m_1,m_2)},\frac{m_2}{gcd(m_1,m_2)})*\frac{c_2-c_1}{gcd(m_1,m_2)}+\frac{m_2}{gcd(m1,m2)}*y$$

5.将 4 中求得式子，代回 1 中

$$x=c_1+k_1*m_1\\ \Downarrow\\ x=c_1+inv(\frac{m_1}{gcd(m_1,m_2)},\frac{m_2}{gcd(m_1,m_2)})*\frac{c_2-c_1}{gcd(m_1,m_2)}*m_1+\frac{m_1m_2}{gcd(m1,m2)}*y\\ \Downarrow\\ x\equiv c\ (\ mod\ m)\\ c=c_1+inv(\frac{m_1}{gcd(m_1,m_2)},\frac{m_2}{gcd(m_1,m_2)})*\frac{c_2-c_1}{gcd(m_1,m_2)}*m_1\\ m=\frac{m_1m_2}{gcd(m1,m2)}=lcm(m1,m2)$$

6.对这两个式子进行推广，任意两个方程可以通过上式合并为一个方程，通过反复合并

代码实现

#include <iostream>
using namespace std;
typedef  unsigned long long ull;
typedef  __int128 ll;
ull n,m,c,gm;
ll m1,c1,m2,c2;
//ll ExCRT
ll gcd(ll a,ll b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
ll ExGcd(ll a,ll b,ll& x,ll& y)
{
	if (b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ll ans=ExGcd(b,a%b,x,y);	//先计算底层x y
	ll temp=y;
	y=x-(a/b)*y;
	x=temp;
	return ans;
}
ll inv(ll a,ll p)
{
	ll x,y;
	if(ExGcd(a,p,x,y)!=1) return -1;//不符合拓展欧几里得算法
	return (x%p+p)%p;//正数化
}
ll abs(ll x)
{
	return x>0?x:-x;
}
int main()
{
	cin>>n;
	cin>>m>>c;
	m1=m,c1=c;
	for(ll i=2; i<=n; ++i)
	{
		cin>>m>>c;
		m2=m,c2=c;
		if(c1>c2)
		{
			swap(c1,c2),swap(m1,m2);
		}
		gm=gcd(m1,m2);//gcd(m1,m2);
		c1=c1+inv(m1/gm,m2/gm)*(c2-c1)*(m1/gm);
		m1=m1/gm*m2;
		c1%=m1;
	}

	cout<<ull(c1);
	return 0;
}

会被毒瘤数据卡掉

in
5
998244353 469904850
998244389 856550978
998244391 656199240
998244407 51629743
998244431 642142204
out
99999999999000019

特别感谢

扩展中国剩余定理详解