题解 P4777 【【模板】扩展中国剩余定理（EXCRT）】

· · 题解

注意一下：：

题目是

x≡b_i\pmod {a_i}

我总是习惯性的把a和b交换位置，调了好久没调出来，qwq。

本题解是按照

x≡a_i\pmod {b_i}

讲述的，请注意

本题m_i不一定两两互质，所以中国剩余定理在本题不再适用。

说是扩展中国剩余定理，其实好像和中国剩余定理关系不大。

使用数学归纳法，如果我们已经知道了前k-1个方程组构成的一个解，记作x，记m=\Pi_{i=1}^{k-1}b_i，则x+i*m(i∈Z)是前k-1个方程的通解，如果这个不懂，就得去好好学学同余了。考虑对于第k个方程，求出一个t，使得

x+t*m≡a_i \pmod {b_i}

然后

x'=x+t*m

综上，循环n次即可。

讲一下如何用扩展欧几里德解线性同余方程。

大家都知道(假设大家都知道)，exgcd可以求出方程

ax+by=gcd(a,b)

的一组整数解。 我们要解的线性同余方程是这样的:

ax≡b\pmod m

可以写成这个形式：

ax+my=b

若方程有解，则

gcd(a,m)|b

一定成立。题目保证有解，无需特判。

于是我们用扩欧求出

ax+my=gcd(a,m)

的一组解，然后等式两边同时除以gcd再乘以b，得

a(x/gcd(a,m)*b)+m(y/gcd(a,m)*b)=b

得解。

还有个细节，就是乘的时候会爆long long，而__int128这个东西比赛时是不可用的，所以还是老老实实打快(gui)速乘吧。 其实和快速幂差不多的。

ll Slow_Mul(ll n, ll k, ll mod){
    ll ans = 0;
    while(k){
      if(k & 1) ans = (ans + n) % mod;
      k >>= 1;
      n = (n + n) % mod;
    }
    return ans;
}

完整AC代码：

#include <cstdio>
const int MAXN = 100010;
typedef long long ll;
int n;
ll a[MAXN], b[MAXN], ans, M, x, y;
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){ x = 1; y = 0; return a; }
    ll d = exgcd(b, a % b, x, y);
    ll z = x; x = y; y = z - (a / b) * y;
    return d;
}
ll Slow_Mul(ll n, ll k, ll mod){
    ll ans = 0;
    while(k){
      if(k & 1) ans = (ans + n) % mod;
      k >>= 1;
      n = (n + n) % mod;
    }
    return ans;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
       scanf("%lld%lld", &b[i], &a[i]);
    ans = a[1];
    M = b[1];
    for(int i = 2; i <= n; ++i){
       ll B = ((a[i] - ans) % b[i] + b[i]) % b[i];
       ll GCD = exgcd(M, b[i], x, y);
       x = Slow_Mul(x, B / GCD, b[i]);
       ans += M * x;
       M *= b[i] / GCD;
       ans = (ans + M) % M;
    }
    printf("%lld\n", ans);
    return 0;
}