扩展中国剩余定理学习笔记+模板（洛谷P4777）

题目链接：

洛谷

题目大意：求同余方程组

$x\equiv b_i(mod\ a_i)$

的最小正整数解。

$1\leq n\leq 10^5,1\leq a_i\leq 10^{12},0\leq b_i\leq 10^{12},b_i<a_i$，保证有解，答案不超过 $10^{18}$。

（其实我没打成方程组形式是因为我 $latex$ 太差）

既然是模板就直接讲方法。假设不一定有解。

方法：每次将前 $i-1$ 个方程合并后的方程与第 $i$ 个方程合并，直到 $n$ 个方程全部合并完。

（合并之后的方程也是 $x\equiv B(mod\ A)$ 的形式）

来看看假设前 $i-1$ 个方程合并后是 $x\equiv B(mod\ A)$，第 $i$ 个方程是 $x\equiv b_i(mod\ a_i)$。

那么合并后的新方程模数肯定是 $\operatorname{lcm}(A,a_i)$。

发现 $x$ 可以表示成 $kA+B$ 的形式，我们就是要找到一个 $k'$ 使得 $k'A+B\equiv b_i(mod\ a_i)$，也就是 $k'A\equiv b_i-B(mod\ a_i)$。

其中 $A,b_i-B,a_i$ 都是已知的，这不就 $EXGCD$ 的模板了吗！

好的。求出 $k'$ 合并之后就是 $x\equiv k'A+B(mod\ \operatorname{lcm}(A,a_i))$。如果方程无解（即没有符合条件的 $k'$）那么整个方程组无解。

一路滚下去，最后滚出的 $B$ 就是答案。

时间复杂度：$n$ 次合并，每次一个 $EXGCD$，复杂度 $O(n\log(\max\{a_i\}))$。

代码：（附带判断）

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int n;

 ll a[],b[];

 ll qmul(ll a,ll b,ll mod){    //模数是long long范围，要写慢速乘

     ll ans=;

     for(;b;b>>=,a=(a<<)%mod) if(b&) ans=(ans+a)%mod;

     return ans;

 }

 ll exgcd(ll a,ll b,ll &x,ll &y){    //模板（返回gcd(a,b)）

     if(!b){x=;y=;return a;}

     ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;

 }

 ll excrt(){    //模板

     ll clcm=a[],ans=b[];    //前一个方程合并就是第一个方程（clcm是A，ans是B）

     for(int i=;i<=n;i++){

         ll x,y,d=exgcd(clcm,a[i],x,y),r=((b[i]-ans)%a[i]+a[i])%a[i],tmp=clcm/d*a[i];    //x,y,d是EXGCD中的，r是bi-B,tmp是lcm(A,ai)

         if(r%d) return -;    //裴蜀定理，不整除gcd则无解

         x=(qmul(x,r/d,a[i])+a[i])%a[i];    //真正的k'

         ans=(ans+qmul(x,clcm,tmp))%tmp;    //新的B

         clcm=tmp;    //新的A

     }

     return ans;    //滚出来的B

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%lld%lld",a+i,b+i);

     printf("%lld\n",excrt());

 }

EXCRT

其实我学这个是为了做出这题：

洛谷P4774 BZOJ5418 LOJ2721 [NOI2018]屠龙勇士题解

巴特西

扩展中国剩余定理学习笔记+模板（洛谷P4777）

最新文章

热门文章