牛客多校第十场 D Han Xin and His Troops 中国剩余定理

题意：

韩信有若干个兵，给定你若干个模数和余数，再给你一个1e18以内的范围限制，求解同余方程组，如果无解，输出“他一定在撒谎”，如果最小解超出范围限制，输出“他可能在撒谎”，否则输出最小解

注意：不保证模数互质，也不保证“他可能在撒谎”的情况答案不爆long long

题解：

因为不保证模数互质，需要用excrt求解。

假算法：把excrt的板子翻译成python，然后一脸自闭地调程序

n=0

m=0

bi=[]

ai=[]

def ggcd(_m,_n):

    if _n == 0:

        _x = 1

        _y = 0

        return _m,_x

    _a1 = _b = 1

    _a = _b1 = 0

    _c = _m

    _d = _n

    _q = int(_c//_d)

    _r = _c%_d

    while _r:

        _c = _d

        _d = _r

        _t = _a1

        _a1 = _a

        _a = _t-_q*_a

        _t = _b1

        _b1 = _b

        _b = _t-_q*_b

        _q = int(_c//_d)

        _r = _c%_d

    _x = _a

    _y = _b

    return _d,_x

def excrt():

    x=0

    y=0

    k=0

    gcd=0

    M=bi[1]

    ans=ai[1]

    #print(ai[1],bi[1])

    i=2

    while(i<=n):

        a=M

        b=bi[i]

        c=(ai[i]-ans%b+b)%b

        gcd,x=ggcd(a,b)

        bg=b//gcd

        if(c%gcd!=0):

            return -1

        x=(x*c//gcd)%bg

        ans=ans+(x*M)

        M=M*bg

        ans=(ans+M)%M

        #print(M,ans,a,b,c,gcd,bg,x)

        i=i+1

    return (ans%M+M)%M

#xx=0

#yy=0

#print(exgcd(3,6,xx,yy))

n,m = map(int,input().split())

i=1

ai.append(0)

bi.append(0)

while(i<=n):

    u,v=map(int,input().split())

    bi.append(u)

    ai.append(v)

    i=i+1

anss=excrt()

if(anss<0):

    print("he was definitely lying")

elif(anss>m):

    print("he was probably lying")

else:

    print(anss)

#不要吐槽我的空格tab混用了

正解：先暴力枚举，计算两两模数的gcd，判断同余方程组是否有解，在保证有解的情况下，将excrt中的模乘过程改成暴力加（龟龟速乘？），一旦超出范围立刻停止运算。

此方法仅适用于同余方程数量和数值都较小的情况。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll ans,n,a[],p[],base,M;

const char *definitely_lie = "he was definitely lying";

const char *probably_lie = "he was probably lying";

int main(){

    cin >> n >> M;

    for (int i=;i<n;i++) cin >> p[i] >> a[i];

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

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

        ll d=__gcd(p[i],p[j]);

        if (d!=){

            if (a[i]%d!=a[j]%d){

                puts(definitely_lie);

                return ;

            }

        }

    }

    ans=; base=;

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

        while (ans%p[i]!=a[i]) {

            ans+=base;

            if (ans>M){

                puts(probably_lie);

                return ;

            }

        }

        ll gg=p[i]/__gcd(base,p[i]);

        if (M/base>=gg) base*=gg;

        else {

            for (int j=i+;j<n;j++) if (ans%p[j]!=a[j]){

                puts(probably_lie);

                return ;

            }

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

            return ;

        }

    }

    for (int i=; i<n; i++) assert(ans % p[i] == a[i]);

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

    return ;

}