CF1866B Battling with Numbers 题解

前置知识：如果 \(p=x^a,q=x^b\)，那么 \(\gcd(p,q)=x^{\min(a,b)},\operatorname{lcm}(p,q)=x^{\max(a,b)}\)。

对于每个 \(x \in a_i\)，令 \(x\) 在 \(Y\) 中的指数为 \(d_i\)（实际上不一定），计算贡献时，考虑将 \(b_i\) 与 \(d_i\) 分别放入 \(p\) 和 \(q\) 中：

• 如果 \(b_i < d_i\)，贡献为 \(0\)。（不存在 \(\operatorname{lcm}(p,q) < \gcd(p,q)\) 的情况）
• 如果 \(b_i = d_i\)，贡献为 \(1\)。（在下面代码中表现为不乘）
• 如果 \(b_i > d_i\)，贡献为 \(2\)。

最后将每个 \(x \in a_i\) 的贡献相乘，即为答案。

code:

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int N=1e5+10,mod=998244353;
int ans=1,n,m,a[N],b[N],c[N],d[N];
map<int,int> ma,ma2;
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]),ma2[a[i]]=b[i];
	scanf("%d",&m);
	for(int i=1;i<=m;i++)scanf("%d",&c[i]);
	for(int i=1;i<=m;i++)scanf("%d",&d[i]),ma[c[i]]=d[i];
	for(int i=1;i<=n;i++)if(b[i]>ma[a[i]])ans=ans*2%mod;
	for(int i=1;i<=m;i++)if(ma2[c[i]]<ma[c[i]])ans=0;
	printf("%d",ans);
}