C. Primitive Primes

Link: C. Primitive Primes

Description

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

Examples
input
3 2 2
1 1 2
2 1
output
1
input
2 2 999999937
2 1
3 1
output
2
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.

Problem solving

这道题的意思就是给你两个多项式，让你找到他们的乘积多项式中对p取模不为0的一个系数。
首先我们知道，一个数x，若想对p取模不为0，那么x一定满足$x=y \cdot p+z$，其中的z满足$z<p$.
那么我们现在去找这两个多项式的系数当中第一个对p取模不为0的系数，这两个系数的和就是答案，即这两个系数相乘之后在c中的系数。
可是为什么呢？
假设我们找到的这两个系数分别为x,y,因为我们找的是对p取模不为0的一个系数。换句话说就是在x，y前面的系数对p取模都为0.
我们再看x，y相乘在c中得到的项是$c^{x+y}$,假设这一项的系数是t，那么t就等于

$$t=a_0b_{x+y}+a_1b_{x+y-1}+a_2b{x+y-2}+\cdots+a_xb_y+\cdots+a_{x+y-2}b_2+a{x+y-1}b_1+a_{x+y}b_0$$

我们不难发现，在t中除了$a_xb_y$这一项，其他项对p取模均为0。
因为其他每一项中都有一个$a_{i} \quad i \in(0, x)$或者$b_{i} \quad i \in(0, y)$，这两个项我们上面已经说过了对p取模为0，所以他们乘上一个数之后对p取模仍然为0。所以我们的t就可以变成$t=y \cdot p+z$的形式，$z=a_x \cdot b_y$。
所以我们只要分别找到两个多项式中第一个对p取模不为0的项数即可。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n, m, p, a;

    scanf("%lld%lld%lld", &n, &m, &p);
    ll x = -1, y = -1;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a); if (a % p && x < 0) x = i;
    }
    for (int i = 0; i < m; i++) {
        scanf("%lld", &a); if (a % p && y < 0) y = i;
    }
    printf("%lld\n", x + y);
}

FFT模板

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 410000;
const double pi=acos(-1);
struct E
{
    double x,y;
    E(){x=y=0;}
    E(double a,double b){x=a;y=b;}
}a[maxn],b[maxn],c[maxn],w[maxn];
int id[maxn],an,bn,cn,n,ln;
E operator +(E x,E y){return E(x.x+y.x,x.y+y.y);}
E operator -(E x,E y){return E(x.x-y.x,x.y-y.y);}
E operator *(E x,E y){return E(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);}

void fft(E *s,int sig)
{
    for(int i=0;i<n;i++)if(i<id[i])swap(s[i],s[id[i]]);
    for(int m=2;m<=n;m<<=1)
    {
        int t=m>>1,tt=n/m;
        for(int i=0;i<t;i++)
        {
            E wn=sig==1?w[i*tt]:w[n-i*tt];
            for(int j=i;j<n;j+=m)
            {
                E tx=s[j],ty=s[j+t]*wn;
                s[j]=tx+ty;
                s[j+t]=tx-ty;
            }
        }
    }
    if(sig==-1)for(int i=0;i<n;i++)s[i].x/=(double)n;
}

int main()
{
    scanf("%d%d",&an,&bn);an++;bn++;
    for(int i=0;i<an;i++) scanf("%lf",&a[i].x);
    for(int i=0;i<bn;i++) scanf("%lf",&b[i].x);

    n=1;ln=0;while(n<(an+bn))ln++,n<<=1;
    for(int i=0;i<n;i++) id[i]=id[i>>1]>>1|((i&1)<<(ln-1));
    for(int m=2;m<=n;m<<=1)
    {
        int t=m>>1,tt=n/m;
        for(int i=0;i<t;i++)
        {
            w[i*tt]=E(cos(i*2*pi/m),sin(i*2*pi/m));
            w[n-i*tt]=E(cos(i*2*pi/m),sin(-i*2*pi/m));
        }
    }

    fft(a,1);fft(b,1);
    for(int i=0;i<n;i++) c[i]=a[i]*b[i];
    fft(c,-1);
    printf("%d",int(c[0].x+0.5));
    for(int i=1;i<an+bn-1;i++)printf(" %d",int(c[i].x+0.5));
    printf("\n");

    return 0;
}