因为此算法基于构造法，下面给出构造流程
推导思路
1.首先从最简单的部分入手，只考虑两个方程的情况，并将其变形为右式
2.联立方程并移项
由不定方程可知，此方程有解充要条件为：$gcd(m_1,m_2)|(c_2-c_1)$
3.对 2 中方程进行变换，通过同余的性质消去 $k_2$
4.上式同时除以 $\frac{m_1}{gcd(m_1,m_2)}$，得到下式
5.将 4 中求得式子，代回 1 中
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
