跟这个题好像，或者说比那题还简单一点，重组环的方法一模一样，看我那题的题解就行。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+10;
int pos[N],_pos[N],v1[N],v2[N],d[N],s[N],len,p,q,n,m,t;
signed main()
{
	cin>>p>>q>>n>>m>>t;
	for(int i=1,x;i<=n;i++)cin>>x,v1[x]=1;
	for(int i=1,x;i<=m;i++)cin>>x,v2[x]=1;
	int qlen=q/__gcd(p,q);
	for(int i=0;i<q;i++)if(_pos[i]==0)
	{
		int nw=i,lst=len;
		while(_pos[nw]==0)_pos[nw]=++len,pos[len]=nw,nw=(nw+p)%q;
		for(int i=lst+1;i<=lst+qlen;i++)pos[++len]=pos[i];
	}
	for(int i=1;i<=q*2;i++)d[i]=v2[pos[i]];
	for(int i=1;i<=q*2;i++)s[i]=s[i-1]+d[i];
	int ans=0;
	for(int i=0;i<p;i++)if(v1[i])
	{
		int b=i%__gcd(p,q),tot=t/p+(i<=t%p-1),j=i%q;
		ans+=s[_pos[j]+tot%qlen-1]-s[_pos[j]-1];
		ans+=(s[_pos[j]+qlen-1]-s[_pos[j]-1])*(tot/qlen);
	}
	cout<<ans;
	return 0;
}

$\text{Description}$

给定 $T,P,Q$ 和大小为 $n$ 的集合 $A$ 与大小为 $m$ 的集合 $B$，求：

$$\sum_{i=0}^{T-1}[(i\bmod{P})\in A]\times[(i\bmod{Q})\in B]$$

$T\le 10^{18},P,Q,n,m\le 10^6$

$\text{Solution}$

不妨设 $P<Q$。

记 $L=\operatorname{lcm}(P,Q)$，则两个余数有最小正周期 $L$。

对于本题，可以将 $T$ 缩到 $L$ 级别，即我们可以分解为 $[0,L-1]$ 和 $[0,T\bmod{L}]$ 两个子问题。

我们需要一个线性解，可以考虑枚举 $A$ 中的数，然后求出其可以对应的 $B$ 中的数的个数。

观察 $[0,L-1]$ 中的整数可以对应的 $B$ 的个数，首先可以考虑将 $[0,L-1]$ 按其对 $P$ 取模的值分成 $P$ 个递增的序列，然后考虑第 $i$ 个序列的第 $j$ 个数，其对应的原值是 $jP+i$，则其对应的对 $Q$ 取模的值为 $(i+Pj)\bmod{Q}$，容易发现这个东西是循环的，我们将这样的一个循环节称作轨道（自己 yy 的）。

那么每个序列都会属于一个轨道，特别地，若 $P,Q$ 互质，则只存在一个轨道。

注意到无论是 $[0,L-1]$ 还是 $[0,T\bmod{L}]$，我们要求的都是轨道内的一个区间内属于 $B$ 的数的个数，对于一个数 $x$，其权值设为 $[x\in B]$，则我们只需预处理一个轨道的权值和与其权值前缀和，就可以迅速求出环上任意区间的权值和了。

由于所有轨道的数的个数和为 $Q$，故时间复杂度为 $O(P+Q)$。

细节较多，建议参考以下代码。

$\text{Code}$

#include<bits/stdc++.h>
#define REG register
using namespace std;
typedef long long ll;
const int N=1000005;
inline void read(int& x){
	static char c;
	while(!isdigit(c=getchar()));x=c^48;
	while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll& x){
	static char c;
	while(!isdigit(c=getchar()));x=c^48;
	while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

int n,m;
ll P,Q,T,L;

int A[N],tmp,IB[N],IA[N],Rk[N];

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

vector<ll> PWS[N];

ll Ask(int p,int l,int r){return l<=r?PWS[p][r]-PWS[p][l-1]:PWS[p][r]+PWS[p][PWS[p].size()-1]-PWS[p][l-1];}

inline void Init(){
	read(P),read(Q),read(n),read(m),read(T);L=lcm(P,Q);
	if(P>Q){
    	swap(n,m),swap(P,Q);
    	for(REG int i=1;i<=m;++i) read(tmp),IB[tmp]=1;
    	for(REG int i=1;i<=n;++i) read(A[i]);
        
    }
	else{
    	for(REG int i=1;i<=n;++i) read(A[i]);
    	for(REG int i=1;i<=m;++i) read(tmp),IB[tmp]=1;
    }
	for(REG int i=0;i<P;++i){
	if(Rk[i]) continue;
    	PWS[i].push_back(0);
    	int Now=i;
    	while(!Rk[Now]) PWS[i].push_back(PWS[i][PWS[i].size()-1]+IB[Now]),IA[Now]=i,Rk[Now]=PWS[i].size()-1,Now=(Now+P)%Q;
    }
}

inline void Work(){
	Init();
	ll Per=T/L,Sur=T%L-1;
	ll Ans1=0,Ans2=0;
	for(REG int i=1;i<=n;++i) Ans1+=PWS[IA[A[i]]][PWS[IA[A[i]]].size()-1];
	for(REG int i=1;i<=n;++i) Ans2+=A[i]<=Sur?Ask(IA[A[i]],Rk[A[i]%Q],Rk[(A[i]%Q+(Sur-A[i])/P*P%Q)%Q]):0ll;
	printf("%lld\n",Per*Ans1+Ans2);
}

int main(){Work();}