python/TangDou/Topic/【扩展】欧几里得算法.md

扩展中国剩余定理

一、[题目描述]

给定 k 组非负整数 m_i, a_i ，求解关于 x 的方程组的最小非负整数解。

\begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \\ x\equiv a_2\ ({\rm mod}\ m_2) \\ ... \\ x \equiv a_k\ ({\rm mod}\ m_k)\end{cases}

二、推导过程

首先，我们假定已经找到了前$k-1$个方程组的解：ans+iM,其中\displaystyle M=\prod_{i=1}^{k-1} m_i

那么我们现在需要找到一个非负整数，满足$ans+tM \equiv a_k (mod \ m_k)$，移项得 tM \equiv a_k-ans(mod \ m_k)

我们发现，这个形式与扩展欧几里得(exgcd)的变形$ax \equiv c(mod \ b)$ 相同，于是令

\large \left\{\begin{matrix}
A = M & \\ 
B = m_k & \\
C=|a_k-ans| & \\ 
X=t
\end{matrix}  
 \right.

那么问题就转化为我们就要求不定方程$AX \equiv C(mod \ B)$ 的解。

而$exgcd(A,B,X,Y)$可以得到满足$AX+BY=gcd(A,B)$ 的一组解，将此式放在模B 的意义下，就是AX \equiv gcd(mod \ B).

所以若使得原同余方程组有解，必须有：$C$ 是$gcd(a,b)$的倍数。

那么我们要找的$t$就等于X \cdot \frac{C}{gcd} 那么满足前$k$个同余方程的解就是$ans=ans+t\cdot M$。

接下来更新M=M\cdot m_k,而在这里实际上$M$只需要求所有模数的最小公倍数即可，所以可以直接将其乘上\frac{m_k}{gcd(m_k,M)},即$\frac{m_k}{gcd}$即可。

Code

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const ll MAXN = 1e5 + 50;
void read(ll &x){/*Fast input, omit here*/}
ll n,a[MAXN],m[MAXN];
ll ans,M;
ll mult(ll a,ll b,ll p){
	ll ans = 0;
	while(b){
		if(b & 1) ans = (ans + a) % p;
		a = (a + a) % p;
		b >>= 1;
	}
	return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b == 0){
      x = 1; y = 0;
      return a;
    }
	ll gcd = exgcd(b, a%b, y, x);
	y -= (a / b) * x;
	return gcd;
}
ll solve(){
	ans = a[1],M = m[1];
	for(ll i = 2;i <= n;++i){
		ll A = M, B = m[i], C =((a[i] - ans) % B + B) % B, x, y;
		ll gcd = exgcd(A, B, x, y);
        //耐心看………………ovo
		if(C % gcd != 0) return -1;
		x = mult(x, C / gcd, B);
		ans += M * x;
		M *= m[i] / gcd;
		ans = (ans % M + M) % M;
	}
	return ans = (ans % M + M) % M;
}
int main(){
	read(n);
	for(ll i = 1;i <= n;++i){
		read(m[i]), read(a[i]);
	}
	printf("%lld\n", solve());
	return 0;
}