「NOI2018」屠龙勇士（EXCRT）

终于把传说中 \(NOI2018D2\) 的签到题写掉了。。。

开始我还没读懂题目。。。而且这题细节巨麻烦。。。（可能对我而言）

首先我们要转换一下，每次的 \(atk[i]\) 都可以用 \(multiset\) 找。

我们发现题目求的是 \(atk*x\equiv a_i(\text{mod}\ p_i)\)，所以我们做一遍 \(exgcd\)，求出同余方程。

然后就可以愉快的 \(EXCRT\) 了~

不过发现一次要把龙的血量清零，所以一定要减到负数。我们在求 \(atk[i]\) 的时候顺便求一下最大值就行了。

当然，中间无论什么时候无解都输出 \(-1\)

\(Code\ Below:\)

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=100000+10;

int n,m,flag;ll a[maxn],p[maxn],b[maxn],c[maxn],A[maxn],B[maxn],Max;

multiset<ll> s;

multiset<ll>::iterator it;

void exgcd(ll a,ll b,ll &g,ll &x,ll &y){

	if(b==0){

		g=a;x=1;y=0;

		return;

	}

	exgcd(b,a%b,g,y,x);

	y-=(a/b)*x;

}

inline ll mul(ll a,ll b,ll mod){

	ll ret=0;b=(b%mod+mod)%mod;

	for(;b;b>>=1,a=(a+a)%mod)

		if(b&1) ret=(ret+a)%mod;

	return ret;

}

inline void merge(ll &a1,ll &b1,ll a2,ll b2){

	ll d=a2-a1,g,x,y;

	exgcd(b1,b2,g,x,y);

	if(d%g==0){

		x=(mul(x,d/g,b2/g)+(b2/g))%(b2/g);

		a1=x*b1+a1;b1=b1/g*b2;

	}

	else flag=1;

}

inline ll excrt(ll *a,ll *b){

	ll a1,b1,a2,b2;

	a1=a[1];b1=b[1];

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

		a2=a[i];b2=b[i];

		merge(a1,b1,a2,b2);

		if(flag) return -1;

	}

	if(a1>=Max) return a1;

	return a1+((Max-a1)/b1+((Max-a1)%b1?1:0))*b1;

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--){

		scanf("%d%d",&n,&m);flag=Max=0;s.clear();

		ll d,g,x,y;

		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",&b[i]);

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

			scanf("%lld",&x);

			s.insert(x);

		}

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

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

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

			c[i]=*it;s.erase(s.find(*it));s.insert(b[i]);

			Max=max(Max,a[i]/c[i]+(a[i]%c[i]?1:0));

		}

		//atk * x = a_1 (mod p_1)

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

			d=a[i];exgcd(c[i],p[i],g,x,y);

			if(d%g){flag=1;break;}

			x=(mul(x,d/g,p[i]/g)+(p[i]/g))%(p[i]/g);

			A[i]=x;B[i]=p[i]/g;

		}

		if(flag) printf("-1\n");

		else printf("%lld\n",excrt(A,B));

	}

	return 0;

}