CF-1207 F. Remainder Problem(分塊)

題目鏈接

題意

一共5e5個數(shù)字,兩種操作:

1 x y , a[x] += y

2 x y , $\sum _{i\in n}{a}_i,n\in [1,5e5],n\%x=y$

思路

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

模數(shù)大于707的數(shù)字暴力求,復(fù)雜度$O(\sqrt{n})$

模數(shù)小于707的記錄答案,$ans[x][y]$表示模x余y的答案,每次更新一個數(shù)計(jì)算它對于707以內(nèi)的模數(shù)貢獻(xiàn),復(fù)雜度$O(\sqrt{n})$

總復(fù)雜度: $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; }

總結(jié)

以上是生活随笔為你收集整理的CF-1207 F. Remainder Problem(分块)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。