CF1316C Primitive Primes

这是 R 教授教学生涯的最后一堂课。每次上课时，R 教授都会给学生们出一道特别的题目让他们解决。你作为他最喜欢的学生，决定最后一次全心全意地解答这道题。 你被给定了两个多项式 $f(x) = a_0 + a_1x + \dots + a_{n-1}x^{n-1}$ 和 $g(x) = b_0 + b_1x + \dots + b_{m-1}x^{m-1}$，它们的系数都是正整数。保证这两个多项式的所有系数的最大公约数均为 $1$，即 $gcd(a_0, a_1, \dots, a_{n-1}) = gcd(b_0, b_1, \dots, b_{m-1}) = 1$。令 $h(x) = f(x) \cdot g(x)$，假设 $h(x) = c_0 + c_1x + \dots + c_{n+m-2}x^{n+m-2}$。 你还被给定了一个质数 $p$。R 教授的挑战是让你找到任意一个 $t$，使得 $c_t$ 不能被 $p$ 整除。他保证在这些条件下一定存在这样的 $t$。如果有多个满足条件的 $t$，输出其中任意一个即可。 由于输入数据较大，请使用高效的输入读取方法。

输入的第一行包含三个整数 $n$、$m$ 和 $p$（$1 \leq n, m \leq 10^6, 2 \leq p \leq 10^9$），$n$ 和 $m$ 分别表示 $f(x)$ 和 $g(x)$ 的项数（即多项式次数加一），$p$ 是给定的质数。 保证 $p$ 是质数。 第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$（$1 \leq a_{i} \leq 10^{9}$），其中 $a_i$ 是 $f(x)$ 中 $x^i$ 的系数。 第三行包含 $m$ 个整数 $b_0, b_1, \dots, b_{m-1}$（$1 \leq b_{i} \leq 10^{9}$），其中 $b_i$ 是 $g(x)$ 中 $x^i$ 的系数。

输出一个整数 $t$（$0 \leq t \leq n+m-2$），表示 $h(x)$ 中 $x^t$ 的系数不能被给定的质数 $p$ 整除。如果有多个满足条件的 $t$，输出其中任意一个即可。

在第一个测试样例中，$f(x)$ 为 $2x^2 + x + 1$，$g(x)$ 为 $x + 2$，它们的乘积 $h(x)$ 为 $2x^3 + 5x^2 + 3x + 2$，因此答案可以是 $1$ 或 $2$，因为 $3$ 和 $5$ 都不能被 $2$ 整除。 在第二个测试样例中，$f(x)$ 为 $x + 2$，$g(x)$ 为 $x + 3$，它们的乘积 $h(x)$ 为 $x^2 + 5x + 6$，因此答案可以是任意一个幂次，因为没有系数能被给定的质数整除。 由 ChatGPT 4.1 翻译