题意:
两个多项式相乘,得h(x),随便找到h(x)的某一项系数
C
t
C_t
C
t
%p!=0,输出t即可
思路:
考虑乘完之后h(x)的每一项系数
c
0
:
a
0
∗
b
0
c_0:a_0*b_0
c
0
:
a
0
∗
b
0
c
1
:
a
0
∗
b
1
+
a
1
∗
b
0
c_1:a_0*b_1+a_1*b_0
c
1
:
a
0
∗
b
1
+
a
1
∗
b
0
c
2
:
a
0
∗
b
2
+
a
1
∗
b
1
+
a
2
∗
b
0
c_2:a_0*b_2+a_1*b_1+a_2*b_0
c
2
:
a
0
∗
b
2
+
a
1
∗
b
1
+
a
2
∗
b
0
很容易发现
c
x
c_x
c
x
应该是
a
0
,
a
1
,
a
2
.
.
.
.
.
a
x
−
1
,
a
x
a_0,a_1,a_2…..a_{x-1},a_x
a
0
,
a
1
,
a
2
.
.
.
.
.
a
x
−
1
,
a
x
b
x
,
b
x
−
1
,
b
x
−
2
.
.
.
.
.
.
b
2
,
b
1
b_x,b_{x-1},b_{x-2}……b_2,b_1
b
x
,
b
x
−
1
,
b
x
−
2
.
.
.
.
.
.
b
2
,
b
1
这两行上下对应相乘再求和
有了这个之后,分别找到a数组和b数组中第一个%p!=0的数的位置
假设
a数组的第一个是a[x]%p!=0(x前面的都能整除p)
b数组的第一个是b[y]%p!=0(y前面的都能整除p)
c
x
+
y
c_{x+y}
c
x
+
y
应该是
a
0
,
a
1
,
a
2
.
.
.
.
.
.
.
.
.
.
.
.
a_0,a_1,a_2…………
a
0
,
a
1
,
a
2
.
.
.
.
.
.
.
.
.
.
.
.
a
x
.
.
.
.
.
.
a
x
+
y
−
1
,
a
x
+
y
a_x……a_{x+y-1},a_{x+y}
a
x
.
.
.
.
.
.
a
x
+
y
−
1
,
a
x
+
y
b
x
,
b
x
−
1
,
b
x
−
2
.
.
.
.
.
.
b
y
b_x,b_{x-1},b_{x-2}……b_y
b
x
,
b
x
−
1
,
b
x
−
2
.
.
.
.
.
.
b
y
.
.
.
.
.
.
b
2
,
b
1
……b_2,b_1
.
.
.
.
.
.
b
2
,
b
1
有一项是
a
x
∗
a
y
a_x*a_y
a
x
∗
a
y
,它肯定不能整除p
而其他的项的乘积都能整除p(因为蓝色字体部分都能整除p)
所有
c
x
+
y
c_{x+y}
c
x
+
y
不能整除p
注:
每个数组肯定都有一个数不能整除p,因为如果他们都能整除p,那它们的gcd应该等于p,与题中所说的gcd=1不符
代码:
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
typedef long long ll;
#define PII make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int MAXN=1e6+50;
const int inf=0x3f3f3f3f;
const int M=5000*4;
int a[MAXN],b[MAXN];
int main()
{
int n,m,p;
cin>>n>>m>>p;
rep(i,0,n-1)scanf("%d",&a[i]);
rep(i,0,m-1)scanf("%d",&b[i]);
int p1,p2;
rep(i,0,n-1){
if(a[i]%p!=0){
p1=i;
break;
}
}
rep(i,0,m-1){
if(b[i]%p!=0){
p2=i;
break;
}
}
cout<<p1+p2<<endl;
return 0;
}
/*
*/