传送门

这题真的是送温暖啊qwq,而且最重要的是yyb巨佬在Day2前几天正好学了crt,还写了博客 然而我都没仔细看,结果我就同步赛打铁了QAQ

我们可以先根据题意,使用set维护,求出每次的攻击力

然后对于一条龙,要使得砍到生命值能加到0,那么 攻击力\(a_i\) * 次数\(x\) 要和 血量\(b_i\) 在膜 回复量\(p_i\) 意义下同余,也就是\(a_ix\equiv b_i\mod p_i\)

然后就是n个这样的方程,求最小的x

首先对于每个方程,考虑转化成\(x\equiv a\mod b\)的形式,原方程等价于\[a_ix+p_iy=b_i\]

首先用\(exgcd\)求出\(a_ix+p_iy=gcd(a_i,p_i)\)的一组解\((x,y)\),然后如果\(b_i \ne 0\mod gcd(a_i,p_i)\),那么无解,否则等式两边可以除掉gcd然后乘上\(b_i\),即\[a_i\frac{b_ix}{gcd(a_i,p_i)}+p_i\frac{b_iy}{gcd(a_i,p_i)}=b_i\]

记\({a'}_i=\frac{b_ix}{gcd(a_i,p_i)},{p'}_i=\frac{p_i}{gcd(a_i,p_i)}\)我们得到了n个形如\(x\equiv {a'}_i\mod {p'}_i\)的方程,右转洛谷题解蒯一份\(excrt\)即可

#include<bits/stdc++.h>
#define LL long long
#define ldb long double
#define il inline
#define re register

using namespace std;
const int N=1e5+10;
il LL rd()
{
    LL x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
il LL smul(LL a,LL b,LL mod){return ((a*b-(LL)((ldb)a/mod*b)*mod)%mod+mod)%mod;}
il void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(!b) {d=a,x=1,y=0;return;}
    exgcd(b,a%b,d,y,x),y-=a/b*x;
}
int n,m;
LL a[N],aa[N],b[N],p[N];
multiset<LL> s1,s2;
multiset<LL>::iterator it;

int main()
{
    int T=rd();
    while(T--)
    {
        s1.clear(),s2.clear();
        bool o=1,ff=0;
        n=rd(),m=rd();
        for(int i=1;i<=n;++i) b[i]=rd();
        for(int i=1;i<=n;++i) p[i]=rd(),ff|=p[i]!=1;
        for(int i=1;i<=n;++i) aa[i]=rd();
        while(m--)
        {
            LL x=rd();
            s1.insert(x),s2.insert(-x);
        }
        for(int i=1;i<=n;++i)
        {
            it=s2.lower_bound(-b[i]);
            if(it!=s2.end()) a[i]=-(*it);
            else a[i]=*(s1.begin());
            s1.erase(s1.find(a[i])),s2.erase(s2.find(-a[i]));
            s1.insert(aa[i]),s2.insert(-aa[i]);
        }
        if(!ff)
        {
            LL ans=0;
            for(int i=1;i<=n;++i) ans=max(ans,(b[i]+a[i]-1)/a[i]);
            printf("%lld\n",ans);
            continue;
        }
        for(int i=1;i<=n&&o;++i)
        {
            LL x,y,d;
            exgcd(a[i],p[i],d,x,y),p[i]/=d;
            if(b[i]%d) o=0;
            a[i]=smul((x%p[i]+p[i])%p[i],b[i]/d,p[i]);
        }
        LL a1=a[1],p1=p[1];
        for(int i=2;i<=n&&o;++i)
        {
            LL x,y,d,c=((a[i]-a1)%p[i]+p[i])%p[i];
            exgcd(p1,p[i],d,x,y),p[i]/=d;
            if(c%d) o=0;
            x=(x%p[i]+p[i])%p[i];
            x=smul(x,c/d,p[i]);
            a1+=smul(p1,x,p1*p[i]),p1*=p[i],a1%=p1;
        }
        printf("%lld\n",o?a1:-1ll);
    }
    return 0;
}

md做这道题的时候一万个地方没开longlong,而且exgcd不知道为什么被我删掉了一个\(*x\) qwq