#3096. 「SNOI2019」数论

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给出正整数 P, Q, T ,大小为 n 的整数集 A 和大小为 m 的整数集 B ,请你求出:

\sum_{i=0}^{T-1} [(i\in A\pmod P)\land(i\in B\pmod Q)]

换言之,就是问有多少个小于 T 的非负整数 x 满足: x 除以 P 的余数属于 A x 除以 Q 的余数属于 B

输入格式

第一行 5 个用空格隔开的整数 P,Q,n,m,T

第二行 n 个用空格隔开的整数,表示集合 A=\{A_1,A_2,\dots ,A_n\} 。保证 A_i 两两不同,且 0 \le A_i < P

第三行 m 个用空格隔开的整数,表示集合 B=\{B_1,B_2,\dots ,B_m\} 。保证 B_i 两两不同,且 0 \le B_i < Q

输出格式

输出一行一个整数表示答案。

样例

样例输入 1

4 6 3 3 14
0 1 3
2 4 5

样例输出 1

4

样例 2

见附加文件。

数据范围与提示

对于所有数据, 1 \le n, m \le 10^6, 1 \le P, Q \le 10^6, 1 \le T \le 10^{18}

  • 对于 10\% 的数据, T \le 10^6

  • 对于另外 20\% 的数据, P, Q \le 1000

  • 对于另外 10\% 的数据, T P, Q 的公倍数。

  • 对于另外 10\% 的数据, P, Q 互质,且 P,Q \le 10^5

  • 对于另外 10\% 的数据, P, Q 互质。

  • 对于另外 10\% 的数据, P,Q \le 10^5

  • 对于余下 30\% 的数据,无特殊限制。