最后三个点WA了,呜呜呜
查看原帖
最后三个点WA了,呜呜呜
536191
__Shao__楼主2022/8/16 12:32

难道是longlong的问题吗?蒟蒻不解

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
int n;
LL m[100005],c[100005];
LL gcd(LL a,LL b)
{
    return !b?a:gcd(b,a%b);
}
LL exgcd(LL a, LL b, LL &x, LL &y){
	if(b==0){
		x = 1, y = 0;
		return a;
	}
	LL x1,y1,gcd;
	gcd = exgcd(b, a%b, x1, y1);
	x = y1, y = x1 - a/b*y1;
	return gcd; 
}

LL getInv(LL a,LL mod)
{
    LL x,y;
    LL d=exgcd(a,mod,x,y);
    return d==1?(x+mod)%mod:-1;
}
LL exCRT(int n)
{
    LL m1,m2,c1,c2,d;
    for(int i=2;i<=n;i++)
    {
        m1=m[i-1],m2=m[i],c1=c[i-1],c2=c[i];
        d=gcd(m1,m2);
        if((c2-c1)%d)
        {
            printf("%lld\n",c2-c1);
            return -1;
        }
        m[i] = m[i-1] * m[i] / d;
        c[i] = (c2-c1)/d * getInv(m1/d,m2/d) % ( m2 / d ) * m1 + c1;
        c[i] = ( c[i] % m[i] + m[i] ) % m[i];
    }
    return c[n];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&m[i],&c[i]);
    printf("%lld",exCRT(n));
    return 0;
}

???求助???

2022/8/16 12:32
加载中...