【刷题】BZOJ 5418 [Noi2018]屠龙勇士

www.lydsy.com/JudgeOnline/upload/noi2018day2.pdf

Solution

将攻击的式子列出来，\(atk \times x-p \times y=a_i\)

这不就是个扩欧的裸式子嘛，求出 \(x\) 的解的式子 \(x=x_0+r \times dis\)，其中 \(r\) 为任意整数，\(dis\) 为不定方程解的间隔

上面的式子发现又是一个同余方程

对于每一条龙都是一个同余方程，那么就是要解一个同余方程组的最小解

用扩展CRT就好了

#include<bits/stdc++.h>

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

const int MAXN=100000+10;

ll T,n,m,h[MAXN],p[MAXN],rem[MAXN],mod[MAXN],v[MAXN],k[MAXN],lm;

std::multiset<ll> S;

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();

	x=data*w;

}

template<typename T> inline void write(T x,char ch='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(ch!='\0')putchar(ch);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline ll mul(ll a,ll b,ll Mod)

{

	ll res=0;

	if(b<0)a=(a%Mod+Mod)%Mod,b=(b%Mod+Mod)%Mod;

	while(b)

	{

		if(b&1)res=(res+a)%Mod;

		a=(a+a)%Mod;

		b>>=1;

	}

	return res;

}

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

{

	if(b==0)

	{

		x=1;

		y=0;

		return a;

	}

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

	ll t=x;

	x=y;

	y=t-(a/b)*y;

	return r;

}

inline ll exCRT()

{

	ll M=mod[1],A=rem[1],t,d,x,y;

	for(register ll i=2;i<=n;++i)

	{

		d=exgcd(M,mod[i],x,y);

		if((rem[i]-A)%d)return -1;

		t=mod[i]/d;

		x=(mul(x,(rem[i]-A)/d,t)%t+t)%t;

		ll tmp=M;M=M/d*mod[i];

		A=(mul(tmp,x,M)+A)%M;;

	}

	A=(A%M+M)%M;

	while(A<lm)A+=M;

	return A;

}

inline void solve()

{

	lm=0;

	memset(rem,0,sizeof(rem));

	memset(mod,0,sizeof(mod));

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

	{

		if(*S.begin()>=h[i])k[i]=*S.begin(),S.erase(S.begin());

		else

		{

			std::multiset<ll>::iterator it=--S.upper_bound(h[i]);

			k[i]=*it,S.erase(it);

		}

		S.insert(v[i]);

	}

	bool mk=1;

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

	{

		ll x,y,a=k[i],b=p[i],c=h[i],d=exgcd(a,b,x,y);

		if(p[i]==1)chkmax(lm,(h[i]+k[i]-1)/k[i]);

		else mk=0;

		if(c%d)

		{

			puts("-1");

			return ;

		}

		mod[i]=p[i]/d,rem[i]=mul(x,c/d,mod[i]);

		if(!rem[i])chkmax(lm,mod[i]);

	}

	if(mk)write(lm,'\n');

	else write(exCRT(),'\n');

}

int main()

{

	read(T);

	while(T--)

	{

		read(n);read(m);S.clear();

		for(register int i=1;i<=n;++i)read(h[i]);

		for(register int i=1;i<=n;++i)read(p[i]);

		for(register int i=1;i<=n;++i)read(v[i]);

		for(register int i=1,x;i<=m;++i)read(x),S.insert(x);

		solve();

	}

	return 0;

}

巴特西

【刷题】BZOJ 5418 [Noi2018]屠龙勇士

Solution

最新文章

热门文章