CF360D Levko and Sets

Levko 非常喜欢各种集合。 Levko 有两个整数数组 $a_{1},a_{2},\ldots,a_{n}$ 和 $b_{1},b_{2},\ldots,b_{m}$，还有一个质数 $p$。今天他要生成 $n$ 个集合。下面描述第 $i$ 个集合的生成过程： 1. 首先，集合中只有一个数字 $1$。 2. 对于集合中的任意一个元素 $c$，对所有 $j$（$1\leq j\leq m$），如果数字 $(c \cdot a_{i}^{b_{j}}) \bmod p$ 没有出现在集合中，则将其加入集合。 3. 只要还能往集合中加入至少一个新元素，就重复第 2 步。 Levko 想知道，有多少个数字至少属于一个集合。也就是说，他想知道这 $n$ 个生成的集合的并集的大小是多少。

第一行包含三个整数 $n$、$m$ 和 $p$（$1 \leq n \leq 10^{4}$，$1 \leq m \leq 10^{5}$，$2 \leq p \leq 10^{9}$），$p$ 是质数。 第二行包含以空格分隔的 $a_{1},a_{2},\ldots,a_{n}$（$1 \leq a_{i} < p$）。 第三行包含以空格分隔的 $b_{1},b_{2},\ldots,b_{m}$（$1 \leq b_{i} \leq 10^{9}$）。

输出一个整数，表示这些集合的并集的大小。

由 ChatGPT 5 翻译