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

niiick · 2018-07-27 11:55:40 · 题解

博客原文食用更佳

问题

求解同余方程组

其中m_1,m_2,m_3...m_k为不一定两两互质的整数， 求x的最小非负整数解

求解

假设已经求出前k-1个方程组成的同余方程组的一个解为x

且有M=\prod_{i-1}^{k-1}m_i

（补充：代码实现中用的就是M=LCM_{i-1}^{k-1}m_i，显然易证这样是对的，还更能防止溢出，上述是为了先方便理解，评论区就别问那么多次了=_=）

则前k-1个方程的方程组通解为x+i*M(i\in Z)

那么对于加入第k个方程后的方程组

我们就是要求一个正整数t，使得

转化一下上述式子得

对于这个式子我们已经可以通过扩展欧几里得求解t

若该同余式无解，则整个方程组无解， 若有，则前k个同余式组成的方程组的一个解解为x_k=x+t*M

所以整个算法的思路就是求解k次扩展欧几里得

另外，蒟蒻平常写题喜欢把后面一项看做b，所以输入和题目是反过来的

输入和题目是反过来的，输入和题目是反过来的，输入和题目是反过来的

//niiick
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long lt;

lt read()
{
    lt f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=100010;
int n;
lt ai[maxn],bi[maxn];

lt mul(lt a,lt b,lt mod)
{
    lt res=0;
    while(b>0)
    {
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}

lt exgcd(lt a,lt b,lt &x,lt &y)
{
    if(b==0){x=1;y=0;return a;}
    lt gcd=exgcd(b,a%b,x,y);
    lt tp=x;
    x=y; y=tp-a/b*y;
    return gcd;
}

lt excrt()
{
    lt x,y,k;
    lt M=bi[1],ans=ai[1];//第一个方程的解特判
    for(int i=2;i<=n;i++)
    {
        lt a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;//ax≡c(mod b)
        lt gcd=exgcd(a,b,x,y),bg=b/gcd;
        if(c%gcd!=0) return -1; //判断是否无解，然而这题其实不用

        x=mul(x,c/gcd,bg);
        ans+=x*M;//更新前k个方程组的答案
        M*=bg;//M为前k个m的lcm
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}

int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    bi[i]=read(),ai[i]=read();
    printf("%lld",excrt());
    return 0;
}

update

OI退役以后就不怎么上洛谷了，评论区似乎对代码部分疑问有点多，所以就更新一下细节，当年喜欢压行确实是个很不好的习惯

针对一些对代码的疑问做点解答

Q：c=(ai[i]-ans%b+b)%b是什么意思

我们推导出t*M \equiv a_k-x(\mod m_k)

其中a_k-x对应ax≡c(\mod b)中的c，这句代码里ans对应x，b对应m_k

所以这句话就是把a_k-x先对m_k取模

Q：为啥不加个括号变成c=((ai[i]-ans)%b+b)%b

ans%b的范围是[0,b-1)，a[i]-ans%b+b一定不会小于0的，当然加了也没问题

Q：为什么M*=bg而不是M*=b

这里bg=b/gcd(a,b)对应到推到部分公式里的就是bg=m_k/gcd(m_k,LCM_{i=1}^{k-1}m_i)