---

1. 题意理解

我们要求满足以下条件的非负整数 $x$ 的个数（$x < T$）：

$$x \bmod P \in A \quad \text{且} \quad x \bmod Q \in B $$

其中 $A$ 是模 $P$ 的余数集合，$B$ 是模 $Q$ 的余数集合。

---

2. 直接枚举不可行

$T$ 最大到 $10^{18}$，不能直接枚举 $x$。

---

3. 转化为同余方程组

条件等价于：

$$\begin{cases} x \equiv a \pmod{P}, & a \in A \\ x \equiv b \pmod{Q}, & b \in B \end{cases} $$

对于每一对 $(a,b)$，我们要求解同余方程组：

$$x \equiv a \ (\text{mod } P),\quad x \equiv b \ (\text{mod } Q) $$

---

4. 方程组解的结构

设 $d = \gcd(P, Q)$。

方程组有解当且仅当

$$a \equiv b \pmod{d}$$

因为 $x \equiv a \pmod{P} \implies x \equiv a \pmod{d}$，
$x \equiv b \pmod{Q} \implies x \equiv b \pmod{d}$，
所以必须有 $a \bmod d = b \bmod d$。

如果有解，则解在模 $\mathrm{lcm}(P, Q)$ 下唯一。

---

4.1 有解时的通解

设 $P = d \cdot p$, $Q = d \cdot q$，其中 $\gcd(p, q) = 1$。

方程组等价于：

$$x = a + P t$$

代入第二个方程：

$$a + P t \equiv b \pmod{Q}$$ $$d p \cdot t \equiv b - a \pmod{d q}$$

两边除以 $d$（因为 $a \equiv b \pmod{d}$，所以 $b-a$ 是 $d$ 的倍数）：

$$p t \equiv \frac{b-a}{d} \pmod{q}$$

由于 $\gcd(p, q) = 1$，$p$ 在模 $q$ 下有逆元 $p^{-1}$，所以：

$$t \equiv p^{-1} \cdot \frac{b-a}{d} \pmod{q}$$

设 $t_0$ 是上面同余式的最小非负解，则：

$$t = t_0 + k q,\quad k \in \mathbb{Z}$$

于是：

$$x = a + P (t_0 + k q) = a + P t_0 + k \cdot P q$$

即：

$$x \equiv a + P t_0 \pmod{P q}$$

记 $M = \mathrm{lcm}(P, Q) = P q = \frac{P Q}{d}$。

所以对于每一对 $(a,b)$ 满足 $a \bmod d = b \bmod d$，解在模 $M$ 下唯一，设这个解为 $r_{a,b}$（$0 \le r_{a,b} < M$）。

---

5. 统计 $x < T$ 的个数

对于每一对 $(a,b)$ 满足 $a \bmod d = b \bmod d$，解的形式为：

$$x = r_{a,b} + k M,\quad k \ge 0$$

我们要计算 $x < T$ 的个数。

即：

$$r_{a,b} + k M < T$$ $$k < \frac{T - r_{a,b}}{M}$$

非负整数 $k$ 的个数为：

$$\max\left(0, \left\lfloor \frac{T - 1 - r_{a,b}}{M} \right\rfloor + 1 \right) $$

（注意 $x$ 从 $0$ 开始，所以 $T-1$ 是上界）

---

6. 直接枚举 $(a,b)$ 不可行

$n, m$ 最大 $10^6$，$n \times m$ 太大。

---

7. 按余数模 $d$ 分组

由于必须有 $a \bmod d = b \bmod d$，我们按这个公共余数 $r_d$ 分组。

对于固定的 $r_d$，设：

• $A_{r_d} = \{ a \in A \mid a \bmod d = r_d \}$
• $B_{r_d} = \{ b \in B \mid b \bmod d = r_d \}$

那么对于 $a \in A_{r_d}$，可以写成 $a = r_d + d \cdot a'$，其中 $0 \le a' < p$。
对于 $b \in B_{r_d}$，可以写成 $b = r_d + d \cdot b'$，其中 $0 \le b' < q$。

---

8. 化简方程组

原方程组：

$$x \equiv r_d + d a' \pmod{P},\quad x \equiv r_d + d b' \pmod{Q} $$

令 $y = \frac{x - r_d}{d}$（因为 $x \equiv r_d \pmod{d}$，所以 $x - r_d$ 是 $d$ 的倍数），则方程组变为：

$$y \equiv a' \pmod{p},\quad y \equiv b' \pmod{q}$$

其中 $\gcd(p, q) = 1$。

---

9. 中国剩余定理（CRT）

因为 $\gcd(p, q) = 1$，模 $p$ 和模 $q$ 的方程组在模 $pq$ 下有唯一解。

设 $y \equiv y_0 \pmod{pq}$ 是解，其中 $0 \le y_0 < pq$。

那么：

$$x = r_d + d y_0 + k \cdot d p q = r_d + d y_0 + k M $$

这里 $M = \mathrm{lcm}(P, Q) = d p q$。

所以对于 $(a', b')$，解为：

$$x \equiv r_d + d \cdot y_0 \pmod{M}$$

其中 $y_0$ 是 $y \equiv a' \pmod{p}$ 和 $y \equiv b' \pmod{q}$ 的唯一解。

---

10. 快速计算所有 $(a',b')$ 对应的解

我们注意到，对于固定的 $r_d$，$(a', b')$ 来自 $A' = \{ \frac{a - r_d}{d} \mid a \in A_{r_d} \}$ 和 $B' = \{ \frac{b - r_d}{d} \mid b \in B_{r_d} \}$。

由于 $\gcd(p, q) = 1$，CRT 建立了一个双射：

$$(a', b') \leftrightarrow y_0$$

其中 $y_0$ 是模 $pq$ 下的唯一解。

因此，问题转化为：
对于每个 $r_d$，我们有一个 $A' \subset \mathbb{Z}_p$，$B' \subset \mathbb{Z}_q$，通过 CRT 映射到 $\mathbb{Z}_{pq}$ 的一个子集 $S_{r_d}$，然后对每个 $s \in S_{r_d}$，计算 $x \equiv r_d + d s \pmod{M}$ 在 $[0, T-1]$ 中的个数。

---

11. 更简单的实现方法

其实我们可以直接这样：

1. 枚举 $r_d = 0, 1, \dots, d-1$。
2. 对每个 $r_d$，收集 $A_{r_d}$ 和 $B_{r_d}$。
3. 对每个 $a \in A_{r_d}$ 和 $b \in B_{r_d}$，解同余方程组得到 $r_{a,b} \in [0, M)$。
4. 用公式 $\lfloor (T - 1 - r_{a,b})/M \rfloor + 1$（如果 $r_{a,b} < T$，否则 0）计数。

但第 3 步枚举所有对还是可能太大，如果 $|A_{r_d}| \cdot |B_{r_d}|$ 很大。

---

12. 利用 CRT 双射优化

对于固定的 $r_d$，我们建立映射：

• $f: A_{r_d} \to \mathbb{Z}_p$，$f(a) = (a - r_d)/d$。
• $g: B_{r_d} \to \mathbb{Z}_q$，$g(b) = (b - r_d)/d$。

CRT 给出双射 $\phi: \mathbb{Z}_p \times \mathbb{Z}_q \to \mathbb{Z}_{pq}$，$\phi(a', b')$ 是模 $pq$ 下的唯一解。

那么 $S_{r_d} = \{ \phi(f(a), g(b)) \mid a \in A_{r_d}, b \in B_{r_d} \}$。

注意 $\phi$ 是双射，所以 $|S_{r_d}| = |A_{r_d}| \cdot |B_{r_d}|$，但我们可以直接得到 $S_{r_d}$ 而不必枚举所有对：
实际上 $\phi(f(a), g(b))$ 可以写成：

$$y_0 \equiv a' \cdot q \cdot q^{-1}_p + b' \cdot p \cdot p^{-1}_q \pmod{pq} $$

其中 $q^{-1}_p$ 是 $q$ 模 $p$ 的逆元，$p^{-1}_q$ 是 $p$ 模 $q$ 的逆元。

所以：

$$y_0 = (a' \cdot Q_1 + b' \cdot Q_2) \bmod{pq}$$

其中 $Q_1 = q \cdot (q^{-1} \bmod p)$，$Q_2 = p \cdot (p^{-1} \bmod q)$ 是 CRT 系数。

于是 $S_{r_d} = \{ (f(a) \cdot Q_1 + g(b) \cdot Q_2) \bmod{pq} \mid a \in A_{r_d}, b \in B_{r_d} \}$。

这仍然需要枚举所有对，但我们可以用卷积思想（因为模 $pq$ 加法）？但 $pq$ 可能很大。

---

13. 实际可行的方法（$P, Q \le 10^6$）

由于 $P, Q \le 10^6$，$d \le 10^6$，且 $\sum_{r_d} |A_{r_d}| = n$，$\sum_{r_d} |B_{r_d}| = m$，最坏情况是某个 $r_d$ 的 $|A_{r_d}| \cdot |B_{r_d}|$ 很大，但平均情况下可能可接受。

我们可以直接枚举 $r_d$，然后枚举 $A_{r_d}$ 和 $B_{r_d}$，解方程组。

解方程组的方法：

• 用扩展欧几里得解 $p t \equiv (b-a)/d \pmod{q}$ 得到 $t_0$，然后 $r_{a,b} = (a + P t_0) \bmod M$。

复杂度：最坏 $O(n m)$，但数据随机可能较快。

---

14. 对于大数据（$n, m$ 大但 $P, Q$ 中等）

我们可以用 meet-in-the-middle：

对于每个 $r_d$，枚举 $a \in A_{r_d}$，计算 $a' = (a - r_d)/d$，解 $y \equiv a' \pmod{p}$，通解 $y = a' + k p$。

对于每个 $b \in B_{r_d}$，解 $y \equiv b' \pmod{q}$，通解 $y = b' + l q$。

我们要 $a' + k p = b' + l q$，即 $k p - l q = b' - a'$。

由于 $\gcd(p, q) = 1$，$k \equiv (b' - a') \cdot p^{-1} \pmod{q}$。

所以对每个 $(a', b')$，$k$ 模 $q$ 唯一确定，即 $y$ 模 $pq$ 唯一确定。

这样我们仍要枚举所有对，但可以在 $B_{r_d}$ 按 $b'$ 分组，对每个 $a'$ 直接找到对应的 $b'$ 来批量计算？这里 $b'$ 是固定的集合，所以还是需要枚举。

---

15. 实现方案（直接枚举对，针对小数据）

对于大数据，正解需要用循环卷积或二维偏序，但这里给出直接法的框架：

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

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) { x = 1; y = 0; return a; }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll inv(ll a, ll m) {
    ll x, y;
    exgcd(a, m, x, y);
    return (x % m + m) % m;
}

int main() {
    ll P, Q, T;
    int n, m;
    cin >> P >> Q >> n >> m >> T;
    vector<int> A(n), B(m);
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < m; i++) cin >> B[i];

    ll d = gcd(P, Q);
    ll p = P / d, q = Q / d;
    ll M = P * q; // lcm(P, Q)

    // 按 r_d 分组
    vector<vector<int>> Ag(d), Bg(d);
    for (int a : A) Ag[a % d].push_back(a);
    for (int b : B) Bg[b % d].push_back(b);

    ll ans = 0;
    ll inv_p = inv(p, q);

    for (int r = 0; r < d; r++) {
        if (Ag[r].empty() || Bg[r].empty()) continue;
        for (int a : Ag[r]) {
            for (int b : Bg[r]) {
                // 解方程组
                // x = a + P t
                // a + P t ≡ b (mod Q)
                // P t ≡ b - a (mod Q)
                // d p t ≡ b - a (mod d q)
                // p t ≡ (b - a)/d (mod q)
                ll rhs = (b - a) / d;
                ll t0 = (rhs * inv_p) % q;
                if (t0 < 0) t0 += q;
                ll x0 = a + P * t0;
                // 解在模 M 下唯一
                x0 %= M;
                if (x0 < 0) x0 += M;
                // 计算 x0 + k M < T 的个数
                if (x0 < T) {
                    ans += (T - 1 - x0) / M + 1;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

---

16. 总结

这道题的核心是将条件转化为同余方程组，利用 $\gcd(P, Q)$ 分组，再运用中国剩余定理将问题化到模 $\mathrm{lcm}(P, Q)$ 下，最后利用除法计数公式统计解数。大数据下需要进一步优化枚举对的过程，例如用循环卷积或二维偏序。