【笔记】EXCRT

Author Avatar
Sakits 10月 29, 2018

简介

  解同余方程组。

算法流程

  假设已经知道了前 i1i-1 个同余方程组的答案 xx 和他们模数的最小公倍数 MM ,那么对于 x+kMx+kM 都是满足前 i1i-1 个同余方程组的,于是我们只需要在 x+kMx+kM 中找到最小的满足第 ii 个同余方程组的数即可。
  设第 ii 个同余方程组的模数为 mm ,余数为 yy,则有:

x+k1M=ymodmk1M+k2m=yx\begin{aligned} x+k_1M&=y\mod m\\ k_1M+k_2m&=y-x \end{aligned}

  那么就可以用exgcd解出 k1k_1 了。
  令 xxx+k1Mx+k_1M,令MMM/gcdmM/gcd*m,继续递推即可。

例题

https://www.luogu.org/problemnew/show/P4777

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm>
#define ll long long 
#define MOD(x) ((x)>=mod?((x)-mod):(x))
using namespace std;
const int maxn=500010, inf=1e9;
int n;
ll a[maxn], b[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline ll mul(ll a, ll b, ll mod)
{
	ll ans=0;
	for(;b;b>>=1, a=MOD(a+a))
	if(b&1) ans=MOD(ans+a);
	return ans;
}

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

inline ll excrt()
{
	ll M=a[1], x=b[1];
	for(int i=2;i<=n;i++)
	{
		ll m=a[i], y=b[i];
		ll k1, k2;
		ll d=exgcd(M, m, k1, k2);
		if((y-x)%d) return -1;
		ll tmp=m/d;
		k1=(k1%tmp+tmp)%tmp;
		ll lcm=M/d*m;
		tmp=(y-x%m+m)%m/d;
		k1=mul(k1, tmp, lcm);
		x=(x+mul(M, k1, lcm))%lcm;
		M=lcm;
	}
	return x;
}

int main()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[i]), read(b[i]);
	printf("%lld\n", excrt()); 
}