P5330 [SNOI2019] Number Theory

Given positive integers $P, Q, T$, an integer set $A$ of size $n$, and an integer set $B$ of size $m$, please compute: $$ \sum_{i=0}^{T-1}[(i\bmod P) \in A \land (i\bmod Q) \in B] $$ In other words, ask how many non-negative integers $x$ less than $T$ satisfy: the remainder of $x$ divided by $P$ belongs to $A$, and the remainder of $x$ divided by $Q$ belongs to $B$.

The first line contains $5$ integers separated by spaces: $P, Q, n, m, T$. The second line contains $n$ integers separated by spaces, representing the set $A=\{A_1,A_2,\cdots,A_n\}$. It is guaranteed that all $A_i$ are pairwise distinct, and $0 \leq A_i < P$. The third line contains $m$ integers separated by spaces, representing the set $B=\{B_1,B_2,\cdots,B_m\}$. It is guaranteed that all $B_i$ are pairwise distinct, and $0 \leq B_i < Q$.

Output one integer on a single line, denoting the answer.

For all testdata, $1 \leq n,m \leq 10^6$, $1 \leq P,Q \leq 10^6$, and $1 \leq T \leq 10^{18}$. For $10\%$ of the testdata, $T \leq 10^6$. For another $20\%$ of the testdata, $P,Q \leq 1000$. For another $10\%$ of the testdata, $T$ is a common multiple of $P$ and $Q$. For another $10\%$ of the testdata, $P$ and $Q$ are coprime, and $P,Q \leq 10^5$. For another $10\%$ of the testdata, $P$ and $Q$ are coprime. For another $10\%$ of the testdata, $P,Q \leq 10^5$. For the remaining $30\%$ of the testdata, there are no special constraints. - 2023.11.17 Added three groups of hack testdata. Translated by ChatGPT 5