yukicoder : No.896 友達以上恋人未満

なんでこのタイトルにしたんだろ。
https://yukicoder.me/problems/no/896

問題

整数対(X[i],Y[i])が与えられる。
これは値X[i]がY[i]個あることを意味する。

クエリとして、(A[i],B[i])が与えられる。
A[i]の倍数でありながらA[i]*B[i]の倍数ではない値の個数を求めよ。

解法

まず、整数対からZ[X[i]]+=Y[i]の手順で各整数の個数を数えよう。
次に、各整数の倍数の個数を数える。

これは各整数xに対して、xの倍数yに対してZ[x] += Z[y]という処理をxの小さい順に行えば求められる。
あとは各クエリZ[A[i]]-Z[A[i]*B[i]]を答えていこう。

int M,N;
ll MX,AX,MY,AY,mo;
int X[1010],Y[1010],A[1010],B[1010];
ll Z[1<<24];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>N>>MX>>AX>>MY>>AY>>mo;
	FOR(i,M) cin>>X[i];
	FOR(i,M) cin>>Y[i];
	FOR(i,M) cin>>A[i];
	FOR(i,M) cin>>B[i];
	
	ll px=X[M-1],py=Y[M-1];
	FOR(i,N) {
		if(i<M) {
			Z[X[i]]+=Y[i];
		}
		else {
			px=(px*MX+AX)%mo;
			py=(py*MY+AY)%mo;
			Z[px]+=py;
		}
	}
	for(i=1;i<mo;i++) {
		for(j=i*2;j<mo;j+=i) Z[i]+=Z[j];
	}
	
	ll pa=A[M-1],pb=B[M-1],xo=0;
	FOR(i,N) {
		
		ll ret=0;
		if(i<M) {
			if(A[i]<mo) {
				ret+=Z[A[i]];
				if(A[i]*B[i]<mo) ret-=Z[A[i]*B[i]];
			}
			cout<<ret<<endl;
		}
		else {
			pa=(pa*MX+AX+mo-1)%mo+1;
			pb=(pb*MY+AY+mo-1)%mo+1;
			if(pa<mo) {
				ret+=Z[pa];
				if(pa*pb<mo) ret-=Z[pa*pb];
			}
		}
		xo^=ret;
	}
	cout<<xo<<endl;
	
}

まとめ

変数が多くて最初問題の理解に手間取った。