#PQJ61x355. QOJ 61_355
QOJ 61_355
给出正整数 ,大小为 的整数集 和大小为 的整数集 ,请你求出:
$$\sum_{i=0}^{T-1} [(i\in A \pmod P)\ \land\ (i \in B \pmod Q)]$$换言之,就是问有多少个小于 的非负整数 满足: 除以 的余数属于 且 除以 的余数属于 。
输入格式
第一行 个用空格隔开的整数 。
第二行 个用空格隔开的整数,表示集合 。保证 两两不同,且 。
第三行 个用空格隔开的整数,表示集合 。保证 两两不同,且 。
输出格式
输出一行一个整数表示答案。
样例数据
样例输入
4 6 3 3 14 0 1 3 2 4 5
样例输出
4
子任务
对于所有数据,$1 \le n, m \le 10^6, 1 \le P, Q \le 10^6, 1 \le T \le 10^{18}$。
对于 的数据,。
对于另外 的数据,。
对于另外 的数据, 是 的公倍数。
对于另外 的数据, 互质,且 。
对于另外 的数据, 互质。
对于另外 的数据,。
对于余下 的数据,无特殊限制。