NOI2018D2T1 屠龙勇士(EXCRT)

Author Avatar
Sakits 10月 29, 2018

题解

  不知道为啥学了一下EXCRT。
  首先可以通过multiset得到杀每条龙时的攻击力,那么要杀掉这条龙必须满足:

atki×xaiatki×xai (mod pi)\begin{aligned} atk_i\times x&\geq a_i\\ atk_i\times x &\equiv a_i \ (\text{mod}\ p_i) \end{aligned}

  要求 xx,但左边有个烦人的 atkatk,考虑把 atkatk 除过去,但 atkatkpip_i 不一定互质,故不一定有逆元。
  考虑 xx 有解的条件是 gcd(atki, pi)  aigcd(atk_i,\ p_i)\ |\ a_i,所以如果有解的话可以左右两边同除以 gcd(atki, pi)gcd(atk_i,\ p_i),那么就可以使 atkiatk_ipip_i 互质了,然后就可以愉快地求得 xx 的最小值。
  但是还要满足第一个条件,xx 每次加上 pip_ilcmlcm 都是符合条件的,于是利用加上 lcmlcm 找到最小的满足第一个条件的 xx 即可。

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm>
#include<set>
#define ll long long 
#define ddq multiset<ll>::iterator
#define MOD(x) ((x)>=mod?((x)-mod):(x))
using namespace std;
const int maxn=500010, inf=1e9;
ll n, m;
ll a[maxn], p[maxn], atk[maxn], atk2[maxn];
multiset<ll>s;

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline ll mul(ll a, ll b, ll mod)
{
	ll ans=0;
	for(;b;b>>=1, a=MOD(a+a))
	if(b&1) ans=MOD(ans+a);
	return ans;
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if(!b) return x=1, y=0, a;
	ll d=exgcd(b, a%b, x, y);
	ll tmp=x; x=y; y=tmp-a/b*y;
	return d;
}

inline ll excrt()
{
	ll M=p[1], x=a[1];
	for(int i=2;i<=n;i++)
	{
		ll m=p[i], y=a[i];
		ll k1, k2;
		ll d=exgcd(M, m, k1, k2);
		if((y-x)%d) return -1;
		ll tmp=m/d;
		k1=(k1%tmp+tmp)%tmp;
		ll lcm=M/d*m;
		tmp=(y-x%m+m)%m/d;
		k1=mul(k1, tmp, lcm);
		x=(x+mul(M, k1, lcm))%lcm;
		M=lcm;
	}
	return x;
}

ll gcd(ll a, ll b) {return b?gcd(b, a%b):a;}

inline ll solve()
{
	s.clear();
	read(n); read(m); ll x;
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(p[i]);
	for(int i=1;i<=n;i++) read(atk2[i]);
	for(int i=1;i<=m;i++) read(x), s.insert(x);
	for(int i=1;i<=n;i++)
	{
		ddq it=s.upper_bound(a[i]);
		if(it!=s.begin()) it--, atk[i]=*it;
		else atk[i]=*it;
		s.erase(it);
		s.insert(atk2[i]);
		ll d=gcd(atk[i], p[i]);
		if(a[i]%d) return -1;
		a[i]/=d; atk[i]/=d; p[i]/=d;
	}
	ll limit=0; 
	for(int i=1;i<=n;i++) limit=max(limit, (ll)ceil(1.0*a[i]/atk[i]));
	ll tmp1, tmp2, d;
	for(int i=1;i<=n;i++) 
	{
		d=exgcd(atk[i], p[i], tmp1, tmp2);
		ll tmp=p[i]/d;
		tmp1=(tmp1%tmp+tmp)%tmp;
		a[i]=mul(a[i], tmp1, p[i]);
	}
	ll ans=excrt(); if(ans==-1) return -1;
	ll lcm=1; for(int i=1;i<=n;i++) lcm=lcm/gcd(lcm, p[i])*p[i];
	if(ans>=limit) return ans;
	ll xs=(ll)ceil(1.0*(limit-ans)/lcm);
	ans+=xs*lcm;
	return ans; 
}

int main()
{
	freopen("dragon.in", "r", stdin);
	freopen("dragon.out", "w", stdout);
	int T; read(T);
	while(T--) printf("%lld\n", solve());
}