luogu P4774 [NOI2018]屠龙勇士

时间：2023-12-31 19:27:26

传送门

这题真的是送温暖啊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

相关文章