博客

C. Primitive Primes

time limit per test1.5 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

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)=a0+a1x+⋯+an−1xn−1 and g(x)=b0+b1x+⋯+bm−1xm−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(a0,a1,…,an−1)=gcd(b0,b1,…,bm−1)=1. Let h(x)=f(x)⋅g(x). Suppose that h(x)=c0+c1x+⋯+cn+m−2xn+m−2.

You are also given a prime number p. Professor R challenges you to find any t such that ct 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

The first line of the input contains three integers, n, m and p (1≤n,m≤106,2≤p≤109), — 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 a0,a1,…,an−1 (1≤ai≤109) — ai is the coefficient of xi in f(x).

The third line contains m integers b0,b1,…,bm−1 (1≤bi≤109) — bi is the coefficient of xi in g(x).

Output

Print a single integer t (0≤t≤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.

Examples

inputCopy

3 2 2

1 1 2

2 1

outputCopy

1

inputCopy

2 2 999999937

2 1

3 1

outputCopy

2

Note

In the first test case, f(x) is 2×2+x+1 and g(x) is x+2, their product h(x) being 2×3+5×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 x2+5x+6, so the answer can be any of the powers as no coefficient is divisible by the given prime.

题意

：给出了两个多项式的系数，求两个多项式相乘后问系数不能被p整除的幂的值

思路

：用a[i]表示第一个多项式的i次方的系数 b[i]表示第二个多项式的i次方的系数

c[i]表示相乘后i次方的乘积后的系数

想想c[0]、c[1]、c[2]。。。它们是

c[0]=a[0]*b[0]，

c[1]=a[0]*a[1]+b[0]*b[1]，

c[2]=a[0]*b[2]+a[1]*b[1]+a[2]*b[0]

c[n]=a[0]*b[n]+a[1]*b[n-1]+a[2]*b[n-2]…+a[n-1]*b[1]+a[n]

b[0]

需要找到不可被p整除的ct，意思是ct=p

x+y，其中x可以是任意整数，y%p！=0。

所以找到了f（x）和g（x）的第一个不可被p整除的系数，分别称它们为a[i]和b[j]。

我们知道a[1]、a[2]……a[i-1]和b[1]、b[2]……b[j-1]都可以被p整除。如果选择ct作为x^（i+j）的系数，那么ct=a[0]*b[i+j]+a[1]*b[i+j-1]。。。a[i+j]*b[0]

这里每个项都有a[0]到a[i-1]或b[0]到b[j-1]的一部分，除了正好有一个项是a[i]*b[j]，并且a[i]或b[j]都不能被p整除。由于p是素数，我们只是将两个数a[i]

b[j]相乘，因此它不能被p整除，所以ct可以写成ct=p

x+y，所以x^（i+j）的系数就是所要的答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define fi first
#define se second
int main()
{
    ll n,m,p;
    cin>>n>>m>>p;
    int a=-1,b=-1;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        if(a==-1&&x%p!=0) a=i;
    }

    for(int i=0;i<m;i++){
        int x;cin>>x;
        if(b==-1&&x%p!=0) b=i;
    }
    cout<<a+b<<endl;
    return 0;
}