主要思路

复盘一年前做过的题，现在感觉确实简单。

考虑表示成 \(d’ \in A, d = d’ + xP\)，然后算有多少个 \(x\) 满足 \(d\) 在 \(B\) 中。暴力直接枚举。考虑优化暴力，我们发现这个肯定是有个循环节的，长度为 \(\text{lcm}(P, Q)\)，这个可以做一个轻微的优化。

我们考虑把这个模 \(Q\) 想成一个环形带，然后把起始位置为 \(start_pos\) 的 \(d \in B\) 在这个纸带上进行标记、做前缀和，为了方便判断前缀和的加减顺序，我们还要标记排名。

计算的时候，对于 \(A_i\)，我们需要知道这个元素 \(T\) 经历了多少次（\(cnt\)）循环，然后完整循环的总和算进去。算完这个之后，我们来算开头和结尾。开头位置肯定就是 \(A_i \bmod Q\)，结尾则是 \((A_i + cnt * P \bmod loop) \bmod Q\)。然后前缀和搞下即可。

// P5330.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

typedef long long ll;

int P, Q, n, m, A[MAX_N], B[MAX_N], prefix[MAX_N], rnk[MAX_N], tot[MAX_N], key[MAX_N];
bool vis[MAX_N];
ll T;

int main()
{
    scanf("%d%d%d%d%lld", &P, &Q, &n, &m, &T);
    int len = Q / __gcd(P, Q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d", &B[i]), prefix[B[i]] = 1, key[B[i]] = 1;
    for (int start_pos = 0; start_pos < Q; start_pos++)
    {
        if (vis[start_pos])
            continue;
        int last_pos = start_pos;
        rnk[last_pos] = 1, vis[start_pos] = true;
        for (int curt = (start_pos + P) % Q; curt != start_pos; last_pos = curt, curt = (curt + P) % Q)
            vis[curt] = true, rnk[curt] = rnk[last_pos] + 1, prefix[curt] += prefix[last_pos];
        tot[start_pos] = prefix[last_pos];
        for (int curt = (start_pos + P) % Q; curt != start_pos; curt = (curt + P) % Q)
            tot[curt] = prefix[last_pos];
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (A[i] >= T)
            continue;
        ll loop_cnt = (T - A[i] - 1) / P;
        ll lft = A[i] % Q, rig = (A[i] + loop_cnt % len * P) % Q;
        ans += loop_cnt / len * tot[lft];
        if (rnk[rig] >= rnk[lft])
            ans += prefix[rig] - prefix[lft] + key[lft];
        else
            ans += tot[lft] - (prefix[lft] - prefix[rig] - key[lft]);
    }
    printf("%lld\n", ans);
    return 0;
}