CF-1207 F. Remainder Problem(分块)

CF-1207 F. Remainder Problem(分块)

题目链接

题意

一共5e5个数字,两种操作:

1 x y , a[x] += y

2 x y , $\sum\limits_{i\in{n}}{a_i}, n\in{[1, 5e5]}, n % x = y $

思路

分块$\sqrt{5e5}=707$

模数大于707的数字暴力求,复杂度$O(\sqrt{n})$

模数小于707的记录答案,$ans[x][y]$表示模x余y的答案,每次更新一个数计算它对于707以内的模数贡献,复杂度$O(\sqrt{n})$

总复杂度: $O(n\sqrt{n})$

#include <bits/stdc++.h> const int maxn = 5e5 + 5; using namespace std; long long ans[705][705], a[maxn]; int main() { int q; cin >> q; while (q--) { int op, x, y; cin >> op >> x >> y; if (op == 1) { a[x] += y; for (int i = 1; i <= 700; ++i) { ans[i][x % i] += y; } }else { if (x <= 700) cout << ans[x][y] << endl; else { int sum = 0; for (int i = y; i < maxn; i += x) { sum += a[i]; } cout << sum << endl; } } } return 0; }