这题真的是送温暖啊qwq,而且最重要的是yyb巨佬在Day2前几天正好学了crt,还写了博客 然而我都没仔细看,结果我就同步赛打铁了QAQ
我们可以先根据题意,使用set维护,求出每次的攻击力
然后对于一条龙,要使得砍到生命值能加到0,那么 攻击力(a_i) * 次数(x) 要和 血量(b_i) 在膜 回复量(p_i) 意义下同余,也就是(a_ixequiv b_imod p_i)
然后就是n个这样的方程,求最小的x
首先对于每个方程,考虑转化成(xequiv amod b)的形式,原方程等价于$$a_ix+p_iy=b_i$$
首先用(exgcd)求出(a_ix+p_iy=gcd(a_i,p_i))的一组解((x,y)),然后如果(b_i e 0mod gcd(a_i,p_i)),那么无解,否则等式两边可以除掉gcd然后乘上(b_i),即$$a_ifrac{b_ix}{gcd(a_i,p_i)}+p_ifrac{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个形如(xequiv {a'}_imod {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
",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
",o?a1:-1ll);
}
return 0;
}
md做这道题的时候一万个地方没开longlong,而且exgcd不知道为什么被我删掉了一个(*x) qwq