CodeCraft-20 (Div. 2) C. Primitive Primes

原题链接：https://codeforces.com/contest/1316/problem/C

题意

\(给出两个本原多项式f(x)和g(x)，h(x)=f(x)*g(x)\)

\(然后给出一个素数p，问h(x)中哪一项的系数无法被p整除。\)

思路

\(f(x)和g(x)各自按照x的指数从小到达排列后，\)

\(各取第一项无法被p整除的项，乘起来所得即为答案。\)

证明

\(假设f(x)中第一个无法被p整除的为第i项，\)

\(g(x)中第一个无法被p整除的为第j项，\)

\(所以f(x)中的前i-1项均可以被p整除，\)

\(g(x)中前j-1项均可以被p整除，\)

\(由多项式乘法，h(x)中第i+j项所取的系数可以表示为\)

\(a_i*b_j+p*k\)

\(显然无法被p整除，得证。\)

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pp;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const double pi=acos(-1);
const double eps=1e-6;
mt19937 rnd(time(0));
int main()
{
    int n,m,p;
    scanf("%d%d%d",&n,&m,&p);
    int ans=0,f=0;int x;
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        if(x%p!=0&&!f)ans+=i,f=1;
    }
    f=0;
    for(int i=0;i<m;i++){
        scanf("%d",&x);
        if(x%p!=0&&!f)ans+=i,f=1;
    }cout<<ans<<endl;
    return 0;
}