本文共 1821 字，大约阅读时间需要 6 分钟。

【题解】

法一：上板子  ，注意运算过程中会有爆long long的情况，可以用__int128辅助实现。

法二：构造满足前i个同余方程的最小自然数解。假设前i-1个方程的最小自然数解为f(i-1)，lcm(p1,p2,…,pi-1)=y，则求解f(i)时，令f(i)=f(i-1)，然后让f(i)每次加上y，直到满足第i个方程为止。可以证明，在保证有解的情况下，加法运算不会超过pi次。 实现比较简单，不会有爆long long的问题，但是该方法仅限于求解pi比较小的同余方程组。

【法一】

#include
   
    using namespace std;typedef __int128 LL;LL a[105],r[105];int n;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,y,x);    y-=a/b*x;    return d;}LL china(){    LL a1,r1,a2,r2,x,y;    a1=a[1],r1=r[1];    for(int i=2;i<=n;i++){        a2=a[i];r2=r[i];        LL c=r2-r1;        LL d=exgcd(a1,a2,x,y);        if(c%d) return -1;        LL x0=c/d*x;        LL t=a2/d;        x0=(x0%t+t)%t;        r1=r1+a1*x0;        a1=a1/d*a2;    }    return r1;}int main(){    long long m;    scanf("%d%lld",&n,&m);    for(int i=1;i<=n;i++)        scanf("%lld%lld",&a[i],&r[i]);    LL ans=china();    if(ans<0) printf("he was definitely lying\n");    else if(ans>m) printf("he was probably lying\n");    else printf("%lld\n",ans);    return 0;}
   

【法二】

#include
   
    using namespace std;typedef long long ll;ll a[105],r[105],f[105];ll lcm(ll a,ll b){    return a/__gcd(a,b)*b;}int main(){    int n; ll m; scanf("%d%lld",&n,&m);    for(int i=1;i<=n;i++)        scanf("%lld%lld",&a[i],&r[i]);    for(int i=1;i<=n;i++){        for(int j=i+1;j<=n;j++){             ll d=__gcd(a[i],a[j]);            if(r[i]%d!=r[j]%d){                puts("he was definitely lying");                return 0;            }        }    }    f[1]=r[1];    ll y=a[1];    for(int i=2;i<=n;i++){        f[i]=f[i-1];        while(f[i]%a[i]!=r[i]){            f[i]+=y;            if(f[i]>m){                puts("he was probably lying");                return 0;            }        }        y=lcm(y,a[i]);    }    printf("%lld\n",f[n]);    return 0;}
   

转载地址：http://khfen.baihongyu.com/