解法

首先我们在\(Q\)的剩余系内枚举数\(x_0\)，对于此每个数表示成\(x = (x_0 + k * P) \mod Q\)，思考一下发现这些数会随着\(k\)变化，且这些数会呈现周期性规律：也就是这些数在一个环上，我们可以考虑记录\(Q\)剩余系中每一个数在\(P\)中的贡献，记录成前缀和，计算答案时比较排名来判断环的方向（长弧或是短弧）。

具体看代码吧，细细品味一下应该就能理解了。

代码

// LOJ3096.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAX_N = 1e6 + 2000;
ll p, q, n, m, t, ai[MAX_N], bi[MAX_N], sum[MAX_N], tot[MAX_N], len, ans;
int key[MAX_N], rk[MAX_N];
bool vis[MAX_N];

ll gcd(ll x, ll y) { return y == 0 ? x : gcd(y, x % y); }

int main()
{
    scanf("%lld%lld%lld%lld%lld", &p, &q, &n, &m, &t);
    len = q / gcd(p, q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]);
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld", &bi[i]), sum[bi[i]]++;
        key[bi[i]] = 1;
    }
    for (int i = 0; i < q; i++)
    {
        if (vis[i])
            continue;
        vis[i] = true;
        int now, last = i;
        rk[i] = 1;
        for (now = (last + p) % q; now != i; last = now, now = (now + p) % q)
            rk[now] = rk[last] + 1, sum[now] += sum[last], vis[now] = true;
        tot[i] = sum[last];
        for (int j = (i + p) % q; j != i; j = (j + p) % q)
            tot[j] = sum[last];
    }
    for (int i = 1; i <= n; i++)
    {
        if (ai[i] >= t)
            continue;
        ll cnt = (t - 1 - ai[i]) / p;
        ll A = ai[i] % q, B = (A + cnt % len * p) % q;
        ans += cnt / len * tot[A];
        if (rk[A] <= rk[B])
            ans += sum[B] - sum[A] + key[A];
        else
            ans += tot[A] - (sum[A] - sum[B] - key[A]);
    }
    printf("%lld", ans);
    return 0;
}