CodeForces 1316C

题意：

给出函数 (f(x)=a_0+a_1*x+⋯+a_{n−1}*x^{n−1})，(g(x)=b_0+b_1*x+⋯+b_{m−1}*x^{m−1})，
保证：(gcd(a_0,a_1,…,a_{n−1})=gcd(b_0,b_1,…,b_{m−1})=1)
令 (h(x)=f(x)*g(x)=c_0+c_1*x+⋯+c_{n+m−2}*x^{n+m−2})；
给出素数 (p) ，要求求出数 (t) 使得 (c_t) 不能被 (p) 整除。
数据范围： (1≤n,m≤10^6,2≤p≤10^9,1≤a_i,b_j≤10^9)

分析：

令 (f(x)) 的系数中不能被 (p) 整除最小系数为 (a_i)，(g(x)) 的系数中不能被 (p) 整除最小系数为 (b_i)，那么有 (c_{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}+...))，显然 (a_i*b_j) 不能被 (p) 整除，即 (t=i+j) 满足条件。
复杂度：(O(n))

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,p,a,ans=0;
    bool f=0;
    scanf("%d%d%d",&n,&m,&p);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        if(a%p!=0&&!f)
        {
            f=1;
            ans+=i;
        }
    }
    f=0;
    for(int i=0;i<m;i++)
    {
        scanf("%d",&a);
        if(a%p!=0&&!f)
        {
            f=1;
            ans+=i;
        }
    }
    printf("%d
",ans);
    return 0;
}