题目描述

小 D 最近在网上发现了一款小游戏。游戏的规则如下：

游戏的目标是按照编号 (1 ightarrow n) 顺序杀掉 (n) 条巨龙，每条巨龙拥有一个初始的生命值 (a_i)。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 (p_i)，直至生命值非负。只有在攻击结束后且当生命值恰好为 (0) 时它才会死去。
游戏开始时玩家拥有 (m) 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻击力最低的一把剑作为武器。
机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 (x) 次，使巨龙的生命值减少(x imes ATK)。
之后，巨龙会不断使用恢复能力，每次恢复 (p_i)生命值。若在使用恢复能力前或某一次恢复后其生命值为(0)，则巨龙死亡，玩家通过本关。

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。
小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 (x) 设置为多少，才能用最少的攻击次数通关游戏吗？

当然如果无论设置成多少都无法通关游戏，输出 (-1) 即可。

多测，(Tle 5)
(n,mle 10^5,operatorname{lcm}(p_i)le 10^{12},a_ile 10^{12},a_ile p_i, ext{攻击力}le 10^6)
但有两个测试点，(p_i=1) ，不保证 (a_ile p_i)

将题目分成多个步骤去做

计算每次选择的剑的攻击力

很显然，每次用的剑是确定的
我直接用的线段树，所以常数上可能有些差
因为攻击力是很小的，所以直接让攻击力当线段树叶子节点的下标
然后每个区间维护当前最小和最大的，有对应的剑的攻击力
也就是说，在处理叶子节点的时候，如果当前攻击力没有对应的剑，那么此节点的最小攻击力设为极大值，最大攻击力设为极小值

查询时，如果能查到([1,min(a_i,10^6)])中最大的攻击力的剑，那肯定就选这个剑
如果不能，那么就查询([1,10^6])中的最小攻击力的剑
然后单点修改，用去的剑的对应攻击力减一，得到的剑的攻击力加一

整理同余方程

设我们对每次攻击选出的剑的攻击力分别是(ATK_i)
则根据题目中杀死龙的条件，并将这(n)个式子都放在(mod p_i)的意义下构成同余方程：

[xcdot ATK_i-a_i=kp_i ]

[xcdot ATK_i-a_iequiv 0pmod {p_i} ]

[xcdot ATK_iequiv a_ipmod{p_i} ]

如果我们想用 exCRT 去解决这个同余方程组，(x)的系数要为 (1)
由 exgcd 的原理，我们可以找到(x',y'in Z)，使得：

[x'cdot ATK_i+y'p_i=gcd(ATK_i,p_i) ]

那么可以以此做变形

[frac{x'cdot ATK_i}{gcd(ATK_i,p_i)}+frac{y'cdot p_i}{gcd(ATK_i,p_i)}=1 ]

此时，已经可以用 exgcd 求得(x',y')的值

[frac{x'cdot ATK_i}{gcd(ATK_i,p_i)}equiv 1pmod{frac{p_i}{gcd(ATK_i,p_i)}} ]

那么，则可以得知：

[xequiv a_ifrac{x'}{gcd(ATK_i,p_i)}pmod {frac{p_i}{gcd(ATK_i,p_i)}} ]

相当于求了个逆元
以上，也可以作为一个用 exgcd 求(ax+by=c)的一组解的过程，在这里其实就是(xcdot ATK_i+ycdot p_i=a_i)
很显然，这要求(gcd(ATK_i,p_i)mid a_i)，对于上一行那个式子也就是(gcd(a,b)mid c)，这是有解的充要条件（斐蜀定理）

那么此时系数就化为 (1) 了
要注意在此过程中要让(p_i=dfrac{p_i}{gcd(ATK_i,p_i)})

exCRT 求解

看这里，应该比较详细了

特判

个人感觉特判在数论题里也比较恶心
~~而且你特判完一个地方以后永远不知道有没有其它需要特判的地方~~

(p_i=1)，这两个点要特判掉，每次恢复一个生命，那么只要将他打到生命为非正就行了，答案是：(max(lceildfrac{a_i}{ATK_i} ceil))
(p_i=a_i)，直接解同余方程结果是(0)，不对
初始生命和恢复生命相等，那么应该把它打到生命为(ka_i)就行，(k)为非正整数，具体用(gcd)实现，见 work_p_a 函数
如果攻击力(mod p_i)以后为 (0)，则无解
特别的，如果此时初始生命就等于恢复能力((a_i=p_i))，那么显然有解，且此时 (x) 可以为任意大于 (0) 的整数（可以理解为随便打一下就行了），此时这个方程就没用了，要标记一下，exCRT 的时候跳过

细节

用快速乘
线段树一定要把(a_i)和(10^6)取(min)
~~我因为这个RE了~~

( exttt{code.})

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline LL read(){
	register LL x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
struct tr{
	tr *ls,*rs;
	int maxatk,minatk;
}dizhi[2000006],*root=&dizhi[0];
int tot;
int sword[1000006],extra[100006];
LL a[100006],p[100006],ATK[100006];
int no[100006];//标记一个方程是否有用 
inline void pushup(tr *tree){
	tree->maxatk=max(tree->ls->maxatk,tree->rs->maxatk);
	tree->minatk=min(tree->ls->minatk,tree->rs->minatk);
}
void build(tr *tree,int l,int r){
	if(l==r){
		if(sword[l]) tree->maxatk=tree->minatk=l;
		else tree->maxatk=0,tree->minatk=1e9;
		return;
	}
	tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
	int mid=(l+r)>>1;
	build(tree->ls,l,mid);build(tree->rs,mid+1,r);
	pushup(tree);
}
void change(tr *tree,int l,int r,int pos){
//		std::printf("change : %d %d
",l,r);
	if(l==r){
//			std::puts("return !");
		if(sword[l]) tree->maxatk=tree->minatk=l;
		else tree->maxatk=0,tree->minatk=1e9;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) change(tree->ls,l,mid,pos);
	else change(tree->rs,mid+1,r,pos);
	pushup(tree);
}
int findmax(tr *tree,int l,int r,int ql,int qr){
//		std::printf("find_max : %d %d %d %d
",l,r,ql,qr);
	if(ql<=l&&r<=qr) return tree->maxatk;
	int mid=(l+r)>>1;
	if(qr<=mid) return findmax(tree->ls,l,mid,ql,qr);
	if(ql>mid) return findmax(tree->rs,mid+1,r,ql,qr);
	return max(findmax(tree->ls,l,mid,ql,qr),findmax(tree->rs,mid+1,r,ql,qr));
}
int findmin(tr *tree,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tree->minatk;
	int mid=(l+r)>>1;
	if(qr<=mid) return findmin(tree->ls,l,mid,ql,qr);
	if(ql>mid) return findmin(tree->rs,mid+1,r,ql,qr);
	return min(findmin(tree->ls,l,mid,ql,qr),findmin(tree->rs,mid+1,r,ql,qr));
}
inline LL mul(LL a,LL b,LL p){
	reg LL ans=0;
	while(b){
		if(b&1) ans=(ans+a)%p;
		b>>=1;a=(a+a)%p;
	}
	return ans;
}
LL exgcd(LL a,LL b,LL &x,LL &y){
	if(!b) return x=1,y=0,a;
	LL gcd=exgcd(b,a%b,x,y);
	LL xx=x;x=y;
	y=xx-(a/b)*y;
	return gcd;
}
inline void get_atk(int n){//calc ATK
//		std::puts("begin to get_atk");
	build(root,1,1000000);
	for(reg int i=1;i<=n;i++){
		if(a[i]==1) ATK[i]=findmin(root,1,1000000,1,1000000);
		else{
			ATK[i]=findmax(root,1,1000000,1,std::min(a[i],1000000ll));
			if(!ATK[i]) ATK[i]=findmin(root,1,1000000,1,1000000);
		}
		sword[ATK[i]]--;change(root,1,1000000,ATK[i]);
		sword[extra[i]]++;change(root,1,1000000,extra[i]);
	}
//		std::printf("ATK :  ");for(reg int i=1;i<=n;i++) std::printf("%lld ",ATK[i]);EN;
//		std::puts("finish getint_atk");
}
inline int pre(int n){//处理同余方程系数化为 1 
//		std::puts("begin to pre");
	LL x,y;
//		EN;EN;EN;
	for(reg int i=1;i<=n;i++){
		ATK[i]%=p[i];
		if(!ATK[i]){
			//特判，如果攻击力模完以后为 0，则无解
			//特别的，如果此时初始生命就等于恢复能力，那么显然有解，且此时 x 可以为任意大于 0 的整数 
			if(a[i]==p[i]) no[i]=1;
			else{
//				std::puts("!ATK[i] & a[i]!=p[i]");
				return 0;
			}
		}
		else{
			LL gcd=exgcd(ATK[i],p[i],x,y);
//				std::printf("(%lld %lld->%lld) ",ATK[i],p[i],gcd);
			if(a[i]%gcd){
//				std::puts("! a[i]%gcd");
				return 0;
			}
			//此处应放在 mod p[i]/gcd 意义下进行 
			p[i]/=gcd;
			x=(x+p[i])%p[i];
			a[i]=mul(x,a[i]/gcd,p[i]);
		}
	}
	return 1;
}
inline int p_1(int n){
	for(reg int i=1;i<=n;i++)if(p[i]!=1) return 0;
	return 1;
}
inline int p_a(int n){
	for(reg int i=1;i<=n;i++)if(p[i]!=a[i]) return 0;
	return 1;
}
inline void work_p_1(int n){
	LL ans=0;
	for(reg int i=1;i<=n;i++) ans=max(ans,std::ceil((double)a[i]/ATK[i]));
	std::printf("%lld
",ans);
}
inline void work_p_a(int n){
	LL ans=0;
	for(reg int i=1;i<=n;i++){
		LL tmp=a[i]/std::__gcd(a[i],ATK[i]);
		ans=(ans/std::__gcd(tmp,ans))*tmp;
	}
	std::printf("%lld
",ans);
}
int main(){
//	std::freopen("dragon18.in", "r", stdin);
//	std::freopen("dragon.out", "w", stdout);
int T=read();while(T--){
	int n=read(),m=read();
	for(reg int i=1;i<=n;i++) a[i]=read();
	for(reg int i=1;i<=n;i++) p[i]=read();
	for(reg int i=1;i<=n;i++) extra[i]=read();
	std::memset(sword,0,sizeof sword);tot=0;
	for(reg int i=1;i<=m;i++) sword[read()]++;
	get_atk(n);
	if(p_a(n)){work_p_a(n);continue;}
	if(p_1(n)){work_p_1(n);continue;}
	LL ans=1,x,y,M;
	if(!pre(n)) goto FAIL;
	{
	reg int i=1;
	for(;i<=n;i++)if(!no[i]){//找第一个有效方程 
		ans=a[i];M=p[i];break;
	}
	for(i++;i<=n;i++){
		if(no[i]) continue;
		LL b=((a[i]-ans)%p[i]+p[i])%p[i];
		LL gcd=exgcd(M,p[i],x,y);
//			gcd=std::__gcd(M,p[i]);
		if(b%gcd){
//			std::puts("! b%gcd");
			goto FAIL;
		}
		x=mul(x,b/gcd,p[i]);
		ans+=mul(x,M,M/gcd*p[i]);
		M=M/gcd*p[i];
		ans=(ans+M)%M;
	}
	}
	std::printf("%lld
",ans);continue;
	FAIL:;
	std::puts("-1");
}
	return 0;
}