luoguP4774 [NOI2018]屠龙勇士

题意

考虑杀每只龙\(i\)时候用的剑是一定的，我们可以用multiset模拟一遍得到，设为\(b_i\)。

发现我们要求一个\(x\)满足对每个\(i\)有：\(b_i*x\equiv a_i\pmod{p_i}\)

这很像扩展中国剩余定理，但是系数不是1，于是考虑化简。

假设前\(i-1\)个方程的答案为\(res\)，模数的\(lcm\)为\(M\)。

我们要找一个\(t\)满足：\(b_i*(res+t*M)\equiv a_i\pmod{p_i}\)

即：\(b_i*M*t\equiv a_i-b_i*res\pmod{p_i}\)

这时就可以用\(exgcd\)了

注意我们并非求最小整数解，因为有必须把每头龙都打到负血的条件，我们记一个限制，最后找到第一个满足限制的解即可。

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

int T,n,m;

ll a[maxn],b[maxn],P[maxn],sword[maxn];

multiset<ll>::iterator it;

multiset<ll>s;

ll exgcd(ll a,ll b,ll& x,ll& y)

{

	if(!b){x=1,y=0;return a;}

	ll d=exgcd(b,a%b,x,y);

	ll z=x;x=y;y=z-(a/b)*y;

	return d;

}

inline ll mul(ll x,ll y,ll mod)

{

	ll res=0;

	while(y)

	{

		if(y&1)res=(res+x)%mod;

		x=(x+x)%mod;y>>=1;

	}

	return res;

}

inline ll solve()

{

	s.clear();

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);

	for(int i=1;i<=n;i++)scanf("%lld",&P[i]);

	for(int i=1;i<=n;i++)scanf("%lld",&sword[i]);

	for(int i=1;i<=m;i++)

	{

		ll x;scanf("%lld",&x);

		s.insert(x);

	}

	for(int i=1;i<=n;i++)

	{

		it=s.upper_bound(a[i]);

		if(it!=s.begin())it--;

		b[i]=*it;s.erase(it),s.insert(sword[i]);

	}

	ll maxx=0,res=0,M=1;

	for(int i=1;i<=n;i++)

	{

		maxx=max(maxx,(a[i]-1)/b[i]+1);

		ll tmpa=mul(b[i],M,P[i]),tmpb=P[i],tmpc=((a[i]-mul(b[i],res,P[i]))%P[i]+P[i])%P[i];

		ll x,y,d=exgcd(tmpa,tmpb,x,y);

		x=(x%P[i]+P[i])%P[i];

		if(tmpc%d)return -1;

		res+=mul(x,tmpc/d,P[i]/d)*M;M*=P[i]/d;

		res=(res%M+M)%M;

	}

	if(res<maxx)res+=((maxx-res-1)/M+1)*M;

	return res;

}

int main()

{

	scanf("%d",&T);

	while(T--)printf("%lld\n",solve());

	return 0;

}

巴特西

luoguP4774 [NOI2018]屠龙勇士

最新文章

热门文章