欧几里得与扩展中国剩余定理ExCrt

欧几里得算法

为什么要放欧几里得算法，因为这个玩意是扩展欧几里得的铺垫，为什么要将扩展欧几里得，因为这个玩意是中国剩余定理的铺垫。
很简单，就是要我们求$gcd(i,j)$。由于证明过程十分繁琐并且没有什么很大的意义，所以便不多管闲事地证明了，结论也很简单：$gcd(i,j) = gcd(j, i \% j)$。于是可以不断递归，直到j变成0，然后返回i就可以了，很常见的方法，直接放代码了。

inline int Gcd(int X, int Y) {
	if (Y == 0) return X ;
	return Gcd(Y, X % Y) ;
}

裴蜀定理

裴蜀定理是扩展欧几里得算法的第二个铺垫，也是一个关于最大公约数的定理。
假设有一个线性方程$ax + by = c$，问这个方程有没有整数解，那么根据裴蜀定理我们就知道当$gcd(a,b) | c$的时候线性方程才可能有整数解。简单的证明就是$gcd(a,b)$显然$|(ax+by)$。对于$gcd(a,b)|c$的情况有没有整数解我们便需要用到扩展欧几里得。

扩展欧几里得

对于

$$ax + by = gcd(a,b)$$

当$a < 0$的时候，式子就可以变成

$$|a| (-x) + by = gcd(|a|, b)$$

可以知道这个式子必然是有整数解的。我们可以对于$(a,b)$进行欧几里得算法，得到最大公约数，然后保存辗转相除法中的式子倒推便可以得到$ax + by = gcd(a,b)$的整数解。那么也就是证明了裴蜀定理，同时也给出了计算线性方程的整数解的方法。
关于推导呢？
$xa + yb = d$且有$x’b + y’(a \% b) = d$
则$x’b + y’(a = \lfloor \frac ab \rfloor b) = d$
$y’a + (x’ - y’ \lfloor \frac a b \rfloor) b = d$
可得$x = y’, y = x’ - y \lfloor \frac ab \rfloor$
推导完毕。。。

inline int Exgcd(int a, int b, int & X, int & Y) {
	if (b == 0) {X = 1, Y = 0 ; return a ;}
	int R = Exgcd(b, a % b, X, Y) ;
	int E = X ; X = Y ; Y = E - a / b * Y ;
	return R ;
}

中国剩余定理

此算法称为扩展中国剩余定理，而中国剩余定理满足$m_i$之间两两互质，我们先从中国剩余定理说起。
还是使用上面的式子，假设方程组有解。那么我们设$M = \prod_{i = 1}^nm_i$，（当然也可以设$M = Lct({m_i})$，效果是一样的）且有n个$M_i = M / m_i$，也就是除了第i个以外其他n-1个$m_i$的乘积。以及$t_i = M_i^{-1}$，则我们知道

$$t_iM_i \equiv 1 (mod ~ m_i)$$

于是有结论：方程组的通解形式为

$$\sum _{i = 1}^n a_it_iM_i + kM$$

以上是通解形式，而通解有无数个，对于每一个解加上$kM$依然是方程组的解，其中$k \in Z$。

证明

关于证明，因为我们知道$t_iM_i \equiv 1 (mod ~ 1)$
所以有

$$a_it_iM_i \equiv a_i (mod ~ m_i)$$

而因为所有的$m_i$之间两两互质，因此对于除了$m_i$之外的所有的$m_j$都有

$$a_it_iM_i \equiv 0 (mod ~ m_j)$$

因此

$$x = \sum _{i = 1}^ n a_it_iM_i$$

满足

$$x = a_i t_i M_i + \sum _{j ≠ i}a_j t_j+M j \equiv a_i + \sum_{j ≠ i} 0 \equiv a_i (mod ~ m_i)$$

因此，$x \equiv a_i (mod ~ m_i)$，所以$x$就是方程的一个特殊解。而至于为什么加上若干个$M$都是解我想就不用我再证明了吧。

long long a[MAXN], m[MAXN], n ;
inline long long Crt() { 
	long long M = 1 ;
	for (int i = 1 ; i <= n ; i ++) M *= m[i] ;
	long long X = 0 ;
	for (int i = 1 ; i <= N ; i ++) {
		long long x, y ;
		long long M_i = M / m[i] ;
		Exgcd(M_i, m[i], x, y) ;
		X = (X + M_i * x * a[i]) % M ;
	}	return (X + M) % M ;
}

扩展中国剩余定理

然后关于扩展中国剩余定理，相较之就是取消掉了$m_i$两两互质这个条件。
我们依然假设$M = \sum_{i = 1}^{k - 1} m_i$，那么假设我们已经知道了前$k-1$个式子的方程通解为
$x + i \times M$，那么在加入第$i$个方程后的通解，只消求出一个满足

$$x + t * M \equiv a_k (mod~m_k)$$

的$t$就可以。

$$t \times M \equiv a_k - x~(mod ~ m_k)$$

直接欧几里得求解$t$即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std ;

typedef long long LL ;
const int MAXN = 100010 ;
const int MAXM = 100010 ;

int N ;
long long A[MAXN], B[MAXN] ;

inline long long Read() {
	long long X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

inline long long Exgcd(LL a, LL b, LL & X, LL & Y) {
	if (b == 0) {
		X = 1 ; Y = 0 ; 
		return a ;
	}	
	LL R = Exgcd(b, a % b, X, Y), E = X ; 	
	X = Y ; Y = E - a / b * Y ;return R ;
}

inline long long Quick_Mul(LL X, LL Y, LL Mod) {
	long long Ans = 0 ;	while (Y) {
		if (Y & 1) Ans = (Ans + X) % Mod ;
		X = (X + X) % Mod ; Y >>= 1  ;
	}	return Ans ;
}

inline long long Excrt() {
	long long X, Y, M = B[1], Ans = A[1] ;
	for (int i = 2 ; i <= N ; i ++) {
		LL a = M, b = B[i], C = (A[i] - Ans % b + b) % b ;
		LL R = Exgcd(a, b, X, Y), E = b / R ;
		if (C % R != 0) return - 1 ;
		X = Quick_Mul(X, C / R, E) ; Ans += X * M ;
		M = M * E ; Ans = (Ans % M + M) % M ;
	}	return (Ans % M + M) % M ;
}

int main() {
	N = Read() ;
	for (int i = 1 ; i <= N ; i ++) 
 		B[i] = Read(), A[i] = Read() ;
	printf("%lld", Excrt()) ; 
	return 0 ;
}

后记

培训的时候听$zhx$神仙讲了大骗分法：大数翻倍法。
很简单，就是对于最大的$a_i$不断地把它加上$p_i$，然后合法检查就可以了。
时间复杂度大概在$O(\sum_i p_i)$到$O(max(p))0$之间，据说是可以用来做题的，但是唯一不能适用的情况就是两组方程，其中$p \in 10^9$。
嗯，骗分大法好。