Codeforces ECR #071 : F. Remainder Problem

今年もよろしくお願いします。
https://codeforces.com/contest/1207/problem/F

問題

500000要素の整数列があり、初期値は0である。
以下のクエリに順次答えよ。

• 指定された要素A[z]をy加算する
• 整数x,yに対し、z % x == yであるzに対するA[z]の総和を答える

解法

平方分割で答える。
S(x,y) := 後者のクエリに対応する値
とする。

• 後者のクエリのうち√N以上の大きなxに対しては、愚直にその都度S(x,y)を求めても1クエリO(√N)
• √N以下の小さなxに対しては、前者のクエリに対し全xに対しS(x, z%x) += yで値を更新しておく。

int Q;
int A[505050];
int S[751][751];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>i>>x>>y;
		if(i==1) {
			A[x]+=y;
			for(i=1;i<=750;i++) S[i][x%i]+=y;
		}
		else {
			if(x<=750) {
				cout<<S[x][y]<<endl;
			}
			else {
				int sum=0;
				for(i=y;i<=500000;i+=x) sum+=A[i];
				cout<<sum<<endl;
			}
		}
	}
	
}

まとめ

ECRのFにしては簡単？