Primitive Primes
Contest: CodeCraft-20 (Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, math, ternary search

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.

Input format:
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)$$$.

Output format:
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.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3 2 2
1 1 2
2 1

Example output:
1

Example input:
2 2 999999937
2 1
3 1

Example output:
2

Editorial:
We will prove a simple result thereby giving one of the power that satisfies the constraint:
We know that cumulative gcd of coefficients is one in both cases. Hence no prime divides all the coefficients of the polynomial. We call such polynomials primitive polynomials. This question in a way tells us that the product of two primitive polynomials is also a primitive polynomial.
Let $$$x_i$$$ be the lowest power of $$$x$$$ in $$$f(x)$$$ whose coefficient is coprime to given prime $$$p$$$, and $$$x_j$$$ be the lowest power of $$$x$$$ in $$$g(x)$$$ whose coefficient is coprime to given prime $$$p$$$. Since both such coefficients exist, the answer is proved to exist.
When we multiply $$$f(x)$$$ and $$$g(x)$$$, we get the following as the coefficient for $$$x^{i + j}$$$,
$$$(a_0 * b_{i + j} + a_1 * b_{i + j - 1} + ...) + a_i * b_j + (a_{i + 1} * b_{j - 1} + a_{i + 2} * b_{j - 2} +...)$$$
We see the terms inside parentheses are all divisible by the prime $$$p$$$, and only $$$a_i * b_j$$$ is not divisible by $$$p$$$. So, we can say that the coefficient of $$$x^{i+j}$$$ is not divisible by $$$p$$$.
Time complexity : $$$O(n+m)$$$