扩展中国剩余定理

扩展中国剩余定理可以用于解同余方程组：

$$\begin{cases}x\equiv r_1\pmod{a_1}\\x\equiv r_2\pmod{a_2}\\\cdots\\x\equiv r_n\pmod{a_n}\\\end{cases}$$

其中$a_i$不一定两两互质

它是怎么做的？

我们暂时先只考虑两个方程组：

$$\begin{cases}x\equiv r_1\pmod{a_1}\\x\equiv r_2\pmod{a_2}\end{cases}$$

因为

$$x=k_1a_1+r_1=k_2a_2+r_2$$

所以有

$$k_1a_1-k_2a_2=r_1-r_2$$

这是一个不定方程，我们可以通过exgcd来求解

根据裴蜀定理，设$g=gcd(a_1,a_2)$，该方程有解当且仅当$(r_1-r_2)|g$

如果有解，那么我们可以通过求出$k_1$或者$k_2$来求得$x$，设其为$x_0$

那么这个方程组的通解为

$$x=x_0+k\times lcm(a_1,a_2)$$

这样求出的$x$既满足第一个方程，又满足第二个方程

而上式又可以转化成

$$x\equiv x_0\pmod{lcm(a_1,a_2)}$$

所以原方程组等价于上面这一个方程

---

对于一般的情况，我们可以对所有同余方程逐个合并为一个同余方程，这样我们就可以获得原同余方程组的通解

例题

「poj2891」Strange Way to Express Integers

这是一个板题，直接上代码了

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;

template <typename T> void read(T &t)
{
	t=0;int f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

const int maxn=100000+5;
int n;
ll a[maxn],r[maxn];

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	ll xx,yy,re=exgcd(b,a%b,xx,yy);
	x=yy;
	y=xx-a/b*yy;
	return re;
}

//取模运算不需要保证在非负整数下进行，因为C++的负数取模运算仍然满足以下式子
//余数 = 被除数 - 商 * 除数
ll excrt()
{
	ll M=a[1],R=r[1];
	for(register int i=2;i<=n;++i)
	{
		ll k1,k2,g=exgcd(M,a[i],k1,k2);
		if((r[i]-R)%g)return -1;
		k1=(r[i]-R)/g*k1%a[i];
		R+=k1*M;
		M=M/g*a[i];
		R%=M;
	}
	return (R+M)%M;
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(register int i=1;i<=n;++i)
			read(a[i]),read(r[i]);
		printf("%lld\n",excrt());
	}
	return 0;
}