小圆前辈的素数

求出集合$A+BA+B$A+B后，把下标为质数的项的系数加起来就行。

由于某一项的系数最大可以为$1e5\ast 1e5>9982443531e5*1e5>998244353$1e5∗1e5>998244353，所以用$NTTNTT$NTT会出错，建议直接用FFT。

code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=(1<<18)+7,mod=998244353;
vector<int>prime;
bool vis[maxn];
inline void pre() {
	for(int i=2; i<maxn; ++i) {
		if(!vis[i]) prime.emplace_back(i),vis[i]=1;
		for(int j:prime) {
			if(i*j>=maxn) break;
			vis[i*j]=1;
			if(i%j==0) break;
		}
	}
}
inline int qpow(int x,int y) {
	int res(1);
	while(y) {
		if(y&1) res=1LL*res*x%mod;
		x=1LL*x*x%mod;
		y>>=1;
	}
	return res;
}
int r[maxn];
inline void ntt(int *x,int lim,int opt) {
	int i,j,k,m,gn,g,tmp;
	for(i=0; i<lim; ++i)
		if(i<r[i]) swap(x[i],x[r[i]]);
	for(m=2; m<=lim; m<<=1) {
		k=m>>1;
		gn=qpow(3,(mod-1)/m);
		for(i=0; i<lim; i+=m) {
			g=1;
			for(j=0; j<k; ++j,g=1LL*g*gn%mod) {
				tmp=1LL*x[i+j+k]*g%mod;
				x[i+j+k]=(x[i+j]-tmp+mod)%mod;
				x[i+j]=(x[i+j]+tmp)%mod;
			}
		}
	}
	if(opt==-1) {
		reverse(x+1,x+lim);
		int inv=qpow(lim,mod-2);
		for(i=0; i<lim; ++i) x[i]=1LL*x[i]*inv%mod;
	}
}
int a[maxn],b[maxn];
int main() {
	cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
	pre();
	int T,lim=(1<<18);
    for(int i=1; i<lim; ++i) r[i]=(i&1)*(lim>>1)+(r[i>>1]>>1);
	cin>>T;
	while(T--) {
		int n,m;
		cin>>n>>m;
		for(int i=0;i<lim;++i) a[i]=b[i]=0;
		for(int i=1,x; i<=n; ++i) {
			cin>>x;
			++a[x];
		}
		for(int i=1,x; i<=m; ++i) {
			cin>>x;
			++b[x];
		}
		ntt(a,lim,1);
		ntt(b,lim,1);
		for(int i=0; i<lim; ++i) a[i]=1LL*a[i]*b[i]%mod;
		ntt(a,lim,-1);
		long long ans(0);
		for(int i:prime) {
			if(a[i]) ans=ans+a[i];
		}
		cout<<ans<<'\n';
	}
}