cf1316c Primitive Primes
首先题目保证有答案
这里用到一个约数的性质
(a+b*g+c*g...)%g=a%g
这题主要是要排除掉a%p!=0,b%p!=0,但（a+b）%p==0
找到最小的不被p整除的数ai和bj，则ci+j就是符合条件的，因为如果有其他项（假设为o，p）也参与了的xi+j的系数，即o+p=i+j则o，p中必有（o<i或 p<j）
根据约数性质，有o+p项得到的系数（由于i，j是最小，之前都可被p整除）必会被p整除掉，不会影响i+j项的系数
所以xi+j项系数（a0*bi+j+a1*bi+j-1+…）+ai*bj+（ai+1*bj-1+ai+2*bj-2+…）中只有ai*bj不被p整除，所以整项系数不被p整除
代码
#include <iostream>
using namespace std;
const int N=1e6+9;
long long n,m,p,x,y,f[N],g[N];
int main(int argc, char *argv[]) {
ios::sync_with_stdio(false);
cin>>n>>m>>p;
x=y=-1;
for(int i=0;i<n;i++){
cin>>f[i];
if(x==-1) if(f[i]%p) x=i;
}
for(int i=0;i<m;i++){
cin>>g[i];
if(y==-1) if(g[i]%p) y=i;
}
cout<<x+y;
return 0;
} 
抖音信息公司氛围 651人发布
查看3道真题和解析
投递网易等公司10个岗位 >