拓展中国剩余定理

我们需要求出一个不定方程的一个解：

(egin{cases}x&equiv a_1pmod {n_1}\x&equiv a_2 pmod{n_2}\ &vdots\x&equiv a_kpmod{n_k}\end{cases})

其中x为我们需要求解的

第一个不定方程通解为 (x = a_1 + tn_1)

我们设前 (i-1) 个不定方程的通解为 (x+t ext{lcm})

带入第 (i) 个方程，得到 (x + t ext{lcm} equiv a_i pmod{n_i})

即为 (t ext{lcm} + y n_i = a_i - x)

使用 ( ext{exgcd}) 求出 (t) 的一个解

得到： (x' = x + t ext{lcm})

通解为： (x' + t' ext{lcm'})

继续求解即可

参考代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

int q;
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b) {
		x = 1,y = 0;
		return;
	}
	exgcd(b,a%b,y,x);
	y -= (a/b)*x;
}
ll gcd(ll a,ll b)
{
	if(!b) return a;
	return gcd(b,a%b);
}
const int N=18;
int n[N],a[N];
int main()
{
	
	scanf("%d",&q);
	for(int i = 1;i <= q;i ++){
		scanf("%d %d",&n[i],&a[i]);
	}
	ll ans = a[1],lcm=n[1];
	for(int i = 2;i <= q;i ++){
		ll x,y;
		exgcd(lcm,n[i],x,y);
		
		x = x*(a[i]-ans)/gcd(lcm,n[i]);
		ans = ans+x*lcm;
		lcm = lcm*n[i]/gcd(lcm,n[i]);
	}
	printf("%lld",(ans%lcm+lcm)%lcm);
	return 0;
}