扩展中国剩余定理 学习笔记

$EXCRT$:

求同余方程余数无限制的通解。

设前$k-1$个方程解为$x$，令$m=\prod^{k-1}_{i=1}b_i$

我们有$x+i*m(i\in Z)$为前$k-1$个方程的通解

对于第$ k $个方程，求$t\in Z,x+t*m \equiv a_k(\mod m_k)$

$t*m\equiv a_k-x(\mod m_k)$

由裴蜀定理，得若方程有解，则$gcd(m,a*t)|a_k-x$

通过exgcd，我们可以求得$a*t*m+ b*m_k=gcd(m,a*t)$的一组通解

两边同乘$\frac{a_k-x}{gcd(m,a*t)}$,得

$a*t*m*(a_k-x)/gcd(m,a*t)+b*m_k*(a_k-x)/gcd(m,a*t)=a_k-x$

由数学归纳法，循环n次即可

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N=1e5+9;
ll n,m,ans,x,y,mul;
int a[N],b[N];

inline ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b) {x=1,y=0;return a;}
	ll ret=exgcd(b,a%b,x,y);
	ll z=x;x=y;y=z-(a/b)*y;
	return ret;
}

int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&b[i],&a[i]);
	ans=a[1];mul=b[1];
	for(int i=2;i<=n;i++)
	{
		ll tem=((a[i]-ans)%b[i]+b[i])%b[i];
		ll G=exgcd(mul,b[i],x,y);
		x=x*(tem/G)%b[i];
		ans=ans+mul*x;
		mul*=b[i]/G;
		ans=(ans+mul)%mul;
	}
	printf("%lld\n",(long long)ans);
	return 0;
}