【NOI2018】屠龙勇士（数论，exgcd）

题面

题解

考场上半个小时就会做了，一个小时就写完了。。

然后发现没过样例，结果大力调发现中间值爆\(longlong\)了，然后就没管了。。

然后又没切掉。。。我是真的傻逼。。。

首先每次选择的刀一定，直接一个\(multiset\)就算出来了。

然后对于每关都单独解一个方程

\(atk[i]x+p[i]y=a[i]\)，直接\(exgcd\)求解即可。

但是注意题目方程的含义，所以\(x\gt 0,y\le 0\)

所以要解出来之后还需要额外的计算一下（就是这里可能爆\(ll\)...)

那么此时对于每一个方程，我们都得到了一个最小的通解\(X0[i]\)

那么，一个可行解\(X=X0[i]+kd[i]\)，其中\(d[i]=p[i]/gcd(p[i],atk[i])\)，\(k\)是常数。

考虑如何合并两个解，

\(X0[1]+k_1d[1]=X0[2]+k_2d[2]\)

不妨令\(X0[2]\gt X0[1]\)，移项得

\(X0[2]-X0[1]=k_1d[1]+k_2d[2]\)

还是一个\(exgcd\)，同时\(k_1\ge 0,k_2\le 0\)，还是这里额外算一下，中间值可能爆\(ll\)

然后就可以算出这两个方程合并后的最小特解\(X0\)，

那么这两个方程合并后的通解就成了\(X=X0+lcm(d[1],d[2])\)

这样子顺次合并就行了。

至于中间值爆\(ll\)的问题，发现额外计算一下的过程就是一个取模+减法

所以龟速乘解决就好了。

然后无解就是某一步的时候\(exgcd\)无解，直接判就好。

为啥他们都说是拓展CRT，我怎么不知道啊？？？

这题我的代码写得好乱啊

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

using namespace std;

#define ll long long

#define MAX 100100

inline ll read()

{

	ll x=0;bool fl=false;char ch=getchar();

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

	if(ch=='-')fl=true,ch=getchar();

	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();

	return fl?-x:x;

}

int n,m;

ll a[MAX],p[MAX],g[MAX],atk[MAX];

ll LCM(ll a,ll b){return (a/__gcd(a,b))*b;}

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

{

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

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

	y-=a/b*x;return d;

}

namespace Choose

{

	multiset<ll> S;

	multiset<ll>::iterator it,itt;

	void Work()

	{

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

		{

			it=itt=S.upper_bound(a[i]);

			if(it!=S.begin())--itt,atk[i]=*itt,S.erase(itt);

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

			S.insert(g[i]);

		}

	}

}

ll X0[MAX],d[MAX];

void init()

{

	Choose::S.clear();

	memset(a,0,sizeof(a));memset(atk,0,sizeof(atk));

	memset(g,0,sizeof(g));memset(p,0,sizeof(p));

	memset(X0,0,sizeof(X0));memset(d,0,sizeof(d));

}

ll Multi(ll a,ll b,ll p)

{

	ll s=0;

	while(b){if(b&1)s=(s+a)%p;a=(a+a)%p;b>>=1;}

	return (s+p)%p;

}

bool Solve()

{

	ll x,y;

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

	{

		ll D=__gcd(atk[i],p[i]),t,G,bs;

		if(a[i]%D)return false;

		exgcd(atk[i]/D,p[i]/D,x,y);

		G=p[i]/D;t=Multi(x,a[i]/D,G);

		if(t==0)t+=G;

		x=t;y=(a[i]-atk[i]*x)/p[i];

		if(y>0)

		{

			t=-y;G=atk[i]/D;

			t=(t%G+G)%G;bs=(t+y)/G;

			y=-t;x+=bs*(p[i]/D);

		}

		X0[i]=x,d[i]=p[i]/D;

	}

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

	{

		if(X0[i]<X0[i-1])swap(X0[i],X0[i-1]),swap(d[i],d[i-1]);

		ll c=X0[i]-X0[i-1],D=__gcd(d[i],d[i-1]),G,t,bs;

		if(c%D!=0)return false;

		exgcd(d[i-1]/D,d[i]/D,x,y);

		G=d[i]/D;t=Multi(x,c/D,G);

		x=t;y=(c-x*d[i-1])/d[i];

		if(y>0)

		{

			t=-y;G=d[i-1]/D;

			t=(t%G+G)%G;bs=(t+y)/D;

			y=t;x+=bs*(d[i]/D);

		}

		X0[i]-=d[i]*y;d[i]=LCM(d[i],d[i-1]);

	}

	return true;

}

int main()

{

	freopen("dragon.in","r",stdin);

	freopen("dragon.out","w",stdout);

	int T=read();

	while(T--)

	{

		init();

		n=read();m=read();

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

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

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

		for(int i=1;i<=m;++i)Choose::S.insert(read());

		Choose::Work();

		if(!Solve())puts("-1");

		else printf("%lld\n",X0[n]);

	}

	return 0;

}

巴特西

【BZOJ5418】【NOI2018】屠龙勇士（数论，exgcd）

【NOI2018】屠龙勇士（数论，exgcd）

题面

题解

最新文章

热门文章