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

Bob_Wang · 2019-03-13 17:00:53 · 题解

什么是拓展中国剩余定理

相信大家都听说过中国剩余定理 （其实没有听说过也没关系，因为拓展中国剩余定理与中国剩余定理其实没有什么关系） 。拓展中国剩余定理的大意是这样的：

给定n组非负整数a~i~,b~i~,求解关于x的方程组： x ≡ b~1~(mod a~1~) x ≡ b~2~(mod a~2~) …… x ≡ b~n~(mod a~n~) 的最小非负整数解

拓展中国剩余定理的基本思路

假设已有答案 ans，满足前k-1项条件。

设 M 为 a~1~ —a~(k-1)~ 的最小公倍数，则 ans + x M 一定满足ans + x M ≡ b~1~—b~(k-1)~ 。

假设 *ans + x M ≡ b~k~(mod a~k~)，那么问题转化为求 n M + m a~k~ = b~k~ - ans** 的最小正整数解。

但必须保证 b~k~ - ans 为正数。

代码

#include<cstdio>
#define ll long long
using namespace std;
ll n,a,b,tot,M;
ll ans,x,y,r;
ll flag=1,mul;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll t=y;
    y=x-(a/b)*y;
    x=t;
    return d;
}//求解同余方程
ll quick_mul(ll nw,ll aim,ll mod)
{
    ll res=0;
    while(aim>0)
    {
        if(aim&1)res=(res+nw)%mod;
        nw=(nw+nw)%mod;
        aim>>=1;
    }
    return res;
}//龟速乘QAQ（模板）
int main()
{
    scanf("%I64d",&n);
    while(n--)
    {
        x=0;
        y=0;
        tot++;//tot计数
        scanf("%I64d%I64d",&a,&b);
        if(tot==1)
        {
            ans=b;
            M=a;
            continue;
        }//初始化
        r=exgcd(M,a,x,y);//求最大公因数
        mul=((b-ans)%a+a)%a;
        x=quick_mul(x,mul/r,a);
        if((b-ans)%r!=0)
        {
            flag=0;
            continue;
        }//判断无解
        ans=ans+(x*M);
        M=(M*a)/r;//更新最小公倍数
        ans=(ans%M+M)%M;//保证ans为正值
    }
    if(flag)
    printf("%I64d",ans);
    else
    printf("No");
    return 0;
}

但是我这个代码过不了最后三个点，各位大神如果有更好的思路希望在下面评论哦！orz~~~