Primitive Primes

题意翻译

- 给定两个序列 $a$ 和 $b$，其中序列 $a$ 的长度为 $n$，序列 $b$ 的长度为 $m$。 - 分别保证序列中所有数字的最大公约数为 $1$。即 $\gcd(a_0, a_1 \dots a_{n - 1}) = 1$，$\gcd(b_0, b_1, \dots b_{m - 1}) = 1$。 - 设 $a$ 与 $b$ 卷积的结果为序列 $c$。即 $c_k = \sum\limits_{0 \leq i \leq k \land i < n \land k - i < m } a_i \times b_{k - i}$。 - 给出一个 **质数** $p$，请你求出一个下标 $t$，满足 $c_t$ **不能**被 $p$ 整除。如果有多个满足要求的 $t$，请任意输出一个。 - $1 \leq n, m \leq 10^6$，$1 \leq p, a_i, b_i \leq 10^9$。

题目描述

It is Professor R's last class of his teaching career. Every time Professor R taught a class, he gave a special problem for the students to solve. You being his favourite student, put your heart into solving it one last time. You are given two polynomials $ f(x) = a_0 + a_1x + \dots + a_{n-1}x^{n-1} $ and $ g(x) = b_0 + b_1x + \dots + b_{m-1}x^{m-1} $ , with positive integral coefficients. It is guaranteed that the cumulative GCD of the coefficients is equal to $ 1 $ for both the given polynomials. In other words, $ gcd(a_0, a_1, \dots, a_{n-1}) = gcd(b_0, b_1, \dots, b_{m-1}) = 1 $ . Let $ h(x) = f(x)\cdot g(x) $ . Suppose that $ h(x) = c_0 + c_1x + \dots + c_{n+m-2}x^{n+m-2} $ . You are also given a prime number $ p $ . Professor R challenges you to find any $ t $ such that $ c_t $ isn't divisible by $ p $ . He guarantees you that under these conditions such $ t $ always exists. If there are several such $ t $ , output any of them. As the input is quite large, please use fast input reading methods.

输入输出格式

输入格式

The first line of the input contains three integers, $ n $ , $ m $ and $ p $ ( $ 1 \leq n, m \leq 10^6, 2 \leq p \leq 10^9 $ ), — $ n $ and $ m $ are the number of terms in $ f(x) $ and $ g(x) $ respectively (one more than the degrees of the respective polynomials) and $ p $ is the given prime number. It is guaranteed that $ p $ is prime. The second line contains $ n $ integers $ a_0, a_1, \dots, a_{n-1} $ ( $ 1 \leq a_{i} \leq 10^{9} $ ) — $ a_i $ is the coefficient of $ x^{i} $ in $ f(x) $ . The third line contains $ m $ integers $ b_0, b_1, \dots, b_{m-1} $ ( $ 1 \leq b_{i} \leq 10^{9} $ ) — $ b_i $ is the coefficient of $ x^{i} $ in $ g(x) $ .

输出格式

Print a single integer $ t $ ( $ 0\le t \le n+m-2 $ ) — the appropriate power of $ x $ in $ h(x) $ whose coefficient isn't divisible by the given prime $ p $ . If there are multiple powers of $ x $ that satisfy the condition, print any.

输入输出样例

输入样例 #1

3 2 2
1 1 2
2 1

输出样例 #1

1

输入样例 #2

2 2 999999937
2 1
3 1

输出样例 #2

2

说明

In the first test case, $ f(x) $ is $ 2x^2 + x + 1 $ and $ g(x) $ is $ x + 2 $ , their product $ h(x) $ being $ 2x^3 + 5x^2 + 3x + 2 $ , so the answer can be 1 or 2 as both 3 and 5 aren't divisible by 2. In the second test case, $ f(x) $ is $ x + 2 $ and $ g(x) $ is $ x + 3 $ , their product $ h(x) $ being $ x^2 + 5x + 6 $ , so the answer can be any of the powers as no coefficient is divisible by the given prime.