欧几里得与扩展中国剩余定理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)$ 的整数解。那么也就是证明了裴蜀定理，同时也给出了计算线性方程的整数解的方法。

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 * 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 ;
}