yukicoder : No.2592 おでぶなおばけさん 2

なんでこんなタイトルなんだろ。
https://yukicoder.me/problems/no/2592

問題

N要素の整数列Aが与えられる。
また正整数Kが与えられる。

以下のクエリを処理せよ。

• 部分列A[L,R]が指定される。整数xに対し、の値がどんな(x-K)でも割り切れるか判定せよ

解法

上記式をxの多項式f(x)とみなしたとき、f(x)が(x-K)で割り切れるとは、f(K)=0であることと等しい。
事前にA[i]*K^iのprefix sumを求めておこう。すなわちとすると、g(R)-g(L-1)=0かどうかが判定できればよい。
あいにく、g(n)はとても大きな数になるので、具体的な値を常時メモリに保持することはできない。
そこで、適当な素数でmodを取りそれで判定すればよい。

ll N,Q,K;
ll A[202020];
ll S[3][202020];
ll mo[3];

//素数判定
bool isprime(ll v) {
	for(ll i=2;i*i<=v;i++) if(v%i==0) return false;
	return (v!=1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>K;
	srand(time(NULL));
	FOR(i,3) {
		while(1) {
			ll a=1000000000+rand()%100000000;
			if(__gcd(a,K)>1) continue;
			if(isprime(a)==0) continue;
			mo[i]=a;
			break;
		}
	}
	ll nk[3]={1,1,1};
	FOR(i,N) {
		cin>>A[i];
		FOR(j,3) {
			S[j][i+1]=(S[j][i]+(A[i]%mo[j]*nk[j]%mo[j])+mo[j])%mo[j];
			nk[j]=nk[j]*(K%mo[j])%mo[j];
		}
	}
	while(Q--) {
		int L,R;
		cin>>L>>R;
		L--;
		int ng=0;
		FOR(i,3) if((S[i][R]-S[i][L]+mo[i])%mo[i]==0) ng++;
		if(ng==3) {
			cout<<"No"<<endl;
		}
		else {
			cout<<"Yes"<<endl;
		}
	}
	
	
}

まとめ

本番でさっとこの解法にたどり着けるかな…。