转载注明来源：https://www.cnblogs.com/syc233/p/13654606.html

首先发现对每条龙使用的剑是固定的，于是可以用multiset预处理出对每条龙使用的剑 \(b_i\) 。

然后发现题其实是要求一堆形如这个的式子：

\[a_i-x \cdot b_i+y \cdot p_i=0 \ (x,y \in \Z) \]

明显这是一个二元一次不定方程，把它化成标准形式：

\[x \cdot b_i+y \cdot p_i=a_i \ (x,y \in \Z) \]

用exgcd求出这个方程的一组通解 \(x_0,y_0\) 。若无解，则直接输出 \(-1\) ，否则有（为了方便，以下均使用 \((i,j)\) 表示 \({\rm{gcd}}(i,j)\) ）：

\[x=\frac{a_i}{(b_i,p_i)}x_0+k \cdot \frac{p_i}{(b_i,p_i)} \iff x \equiv x_0 \ ({\rm{mod}} \ \frac{p_i}{(b_i,p_i)}) \]

对每一个二元一次不定方程进行上述操作，令 \(A_i=x_0,B_i=\frac{p_i}{(b_i,p_i)}\) ，则需要求解如下同余方程组：

\[\begin{cases} x \equiv A_1 \ ({\rm{mod}} \ B_1)\\ x \equiv A_2 \ ({\rm{mod}} \ B_2)\\ \cdots \\ x \equiv A_n \ ({\rm{mod}} \ B_n)\\ \end{cases} \]

用exCRT合并即可。

特判 \(p_i=1\) ，让所有龙的血量非正即可。

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#define maxn 100005
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;

template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

inline lxl fti(lxl a,lxl b,lxl mod)
{
	lxl res=0;
	while(b>0)
	{
		if(b&1) (res+=a)%=mod;
		(a+=a)%=mod;
		b>>=1;
	}
	return res;
}

inline lxl exgcd(lxl a,lxl b,lxl &x,lxl &y)
{
	if(!b) {x=1,y=0;return a;}
	lxl res=exgcd(b,a%b,x,y);
	lxl z=x;x=y;y=z-(a/b)*y;
	return res;
}

int n,m;
lxl a[maxn],p[maxn],b[maxn],aw[maxn];
multiset<lxl> s;
#define IT multiset<lxl>::iterator

lxl A[maxn],B[maxn];

int main()
{
	// freopen("P4774.in","r",stdin);
	int T;read(T);
	while(T--)
	{
		read(n),read(m);
		s.clear();
		lxl mx=0;
		for(int i=1;i<=n;++i) read(a[i]);
		for(int i=1;i<=n;++i) read(p[i]),mx=max(mx,p[i]);
		for(int i=1;i<=n;++i) read(aw[i]);
		for(int i=1;i<=m;++i)
		{
			lxl w;read(w);
			s.insert(w);
		}
		bool flag=true;
		for(int i=1;i<=n;++i)
		{
			IT it=s.upper_bound(a[i]);
			if(it!=s.begin()) --it;
			b[i]=*it;
			s.erase(it);
			s.insert(aw[i]);
			lxl x,y,d=exgcd(b[i],p[i],x,y);
			if(a[i]%d) {flag=false;break;}
			a[i]/=d,p[i]/=d;
			x=fti(x,a[i],p[i]);
			B[i]=p[i];
			A[i]=(x%B[i]+B[i])%B[i]; 
		}
		if(!flag) {puts("-1");continue;}
		if(mx==1)
		{
			lxl ans=0;
			for(int i=1;i<=n;++i)
				ans=max(ans,(a[i]+b[i]-1)/b[i]);
			printf("%lld\n", ans);
			continue;
		}
		lxl M=B[1],ans=A[1];
		for(int i=2;i<=n;++i)
		{
			lxl b1=M,b2=B[i],c=(A[i]-ans%b2+b2)%b2,x,y;
			lxl d=exgcd(b1,b2,x,y);
			if(c%d) {flag=false;break;}
			b2/=d,c/=d;
			x=fti(x,c,b2);
			ans+=M*x;
			M*=B[i]/d;
			(ans+=M)%=M;
		}
		if(!flag) {puts("-1");continue;}
		printf("%lld\n",(ans+M)%M);
	}
	return 0;
}

参考资料：

扩展欧几里得定理

CRT 中国剩余定理

其实是忘完了去复习了一下