扩展中国剩余定理(EXCRT)

题意：给定 $n$ 组非负整数 $a _i, p _i$ ，求解关于 $x$ 的方程组的最小非负整数解。

$$\begin{cases} x \equiv b_1\pmod {a _1} \\\\ x \equiv b_2\pmod {a _2} \\\\ …… \\\\ x \equiv b_n\pmod {a _n} \end{cases}$$

扩展中国剩余定理。

由于不保证 $a _i$ 和 $p _i$ 互质，所以我们可以采用连续 $n$ 次扩展欧几里得来求解。

首先我们令 $m=p _1,ans=a _1$，求出满足第一个方程 $x \equiv a _1\ ({\rm mod}\ p _1)$ 的特解。

然后关于后面的方程，假如我们已经求出了前 $i-1$ 个方程构成的方程组的解 $ans$，其中 $m=$ $\operatorname{lcm}(p _1,p _2,···,p _{i-1})$，那么前 $i-1$ 个方程的通解是 $ans+t\times m(t\in \mathbb{Z})$。

在第 $i$ 个方程中，求出整数 $t$，满足 $ans+t\times m \equiv a_k\pmod {p _k}$，这是一个线性同余方程，可以用扩展欧几里得解出，如果有解，那么 $ans'=ans+t\times m$ 就是前 $k$ 个方程的解。

然后就可以愉快的解题了，注意有几个要点：

1. $m$ 需要每次更新，求 $\operatorname{lcm}$；
2. 注意取模问题，在解方程前先将 $(a _k-ans)$ 给 $p _k$ 取模，在 $m$ 更新后 $ans$ 也要给 $m$ 取模，在求出 $t$ 后，算它的通解时要给 $\dfrac{p _k}{num}$ 取模，其中 $num$ 是 $m,p _k$ 的最大公约数。
3. 快速乘，在算 $t$ 时。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n;
long long a[101010],p[101010];
long long m,ans,num,x,y;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	long long num=exgcd(b,a%b,x,y);
	long long z=x;
	x=y;
	y=z-(a/b)*y;
	return num;
}
long long multi(long long a,long long b,long long p)
{
	long long ans=0;
	for(;b;b>>=1)
	{
		if(b&1)
			ans=(ans+a)%p;
		a=(a+a)%p;
	}
	return ans;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&p[i],&a[i]);
	m=p[1];
	ans=a[1];
	for(int i=2;i<=n;i++)
	{
		num=exgcd(m,p[i],x,y);
		long long c=(a[i]-ans%p[i]+p[i])%p[i];
		long long mod=p[i]/num;
		if(c%num!=0)
		{
			printf("-1");
			return 0;
		}
		x=multi(x,c/num,mod);
		ans=ans+x*m;
		m=m*mod;
		ans=(ans%m+m)%m;
	}
	printf("%lld",ans);
	return 0;
}