Luogu

LOJ

分析

考虑枚举一个 $A_i$，则我们需要计算
$$
\sum_{x=0}^{\lfloor\frac{T-A_i-1}{P}\rfloor}[(Px+A_i)\bmod Q\in B]
$$
发现 $(Px+A_i)\bmod Q$ 有长度为 $\frac{Q}{\gcd(P,Q)}$ 的循环节，因此我们可以暴力求出循环节，然后计算。这样子是 $\mathcal{O}\left(\frac{nQ}{\gcd(P,Q)}\right)$ 的。

注意到模 $\gcd(P,Q)$ 意义下相等的 $A_i$ 循环节内的元素完全相同，不同的只是起始位置而已。所以我们可以将这些 $A_i$ 放到一起处理，每次先算出某个 $A_i$ 的循环节，剩下的 $A_i$ 的循环节相当于这一个平移了若干位，很好计算贡献。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int P,Q,n,m,a[N],b[N],vb[N],s[N<<1],pos[N];
ll T,D,L;

int main() {
    P=read(),Q=read(),n=read(),m=read(),T=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=m;++i) b[i]=read();
    if (P>Q) swap(P,Q),swap(n,m),swap(a,b);
    for (int i=1;i<=m;++i) vb[b[i]]=1;
    D=__gcd(P,Q),L=1ll*P*Q/D;
    sort(a+1,a+n+1,[](int x,int y) { return x%D<y%D; });
    ll ans=0;
    for (int i=0,j=1;i<D;++i) {
        int len=Q/D;
        for (int k=1,w=i;k<=len;++k,w=(w+P)%Q) s[k]=s[k+len]=vb[w],pos[w]=k;
        for (int k=1;k<=len<<1;++k) s[k]+=s[k-1];
        for (;j<=n&&a[j]%D==i;++j) {
            if (T<=a[j]) continue;
            int p=pos[a[j]],l=((T-a[j]-1)/P+1)%len;
            ans+=((T-a[j]-1)/P+1)/len*s[len]+s[p+l-1]-s[p-1];
        }
    }
    printf("%lld\n",ans);
    return 0;
}