注意一下：：

题目是

\[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}m_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,b)
\]

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

\[a(x/gcd(a,b)*b)+m(y/gcd(a,b)*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;

}

巴特西

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

注意一下：：

本题解是按照

$$x≡a_i\pmod {b_i}$$

讲述的，请注意

最新文章

热门文章

巴特西

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

注意一下：：

本题解是按照

$$x≡a_i\pmod {b_i}$$

讲述的，请注意

最新文章

热门文章

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