cf1316c Primitive Primes

首先题目保证有答案

这里用到一个约数的性质

(a+b*g+c*g...)%g=a%g

这题主要是要排除掉a%p!=0,b%p!=0,但（a+b）%p==0

找到最小的不被p整除的数a_i和b_j，则c_i+j就是符合条件的，因为如果有其他项（假设为o，p）也参与了的x_i+j的系数，即o+p=i+j则o，p中必有（o<i或 p<j）

根据约数性质，有o+p项得到的系数（由于i，j是最小，之前都可被p整除）必会被p整除掉，不会影响i+j项的系数

所以x_i+j项系数（a₀*b_i+j+a₁*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整除，所以整项系数不被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;
}