Untitled
domovonok
c_cpp
a year ago
2.4 kB
4
Indexable
Never
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif using ll = long long; using ull = unsigned long long; using db = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<db, db>; using tiii = tuple<int, int, int>; using str = string; #define vt vector #define pb push_back #define eb emplace_back #define ins insert #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() #define mp make_pair #define mt make_tuple #define fi first #define se second constexpr int maxN = 1e5; constexpr int S = 317; vt<int> a(maxN); struct Block { int l, r; vt<vt<int>> data; Block(int lx, int rx) { l = lx; r = rx; data.assign(S + 1, vt<int> (S + 1)); for (int i = l; i < r; i++) { for (int p = 1; p <= S; p++) { data[p][(i - l) % p] += a[i]; } } debug(data); } int calc(int p, int q) { debug(data, p, q - (l % p)); int c = q - (l % p); if (c < 0) { c += p; } return data[p][c]; } }; vt<Block> sd; void solve() { int n, Q; cin >> n >> Q; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int l = 0; l < n; l += S) { sd.pb(Block(l, min(n, l + S))); } while (Q--) { int p, q; cin >> q >> p; if (p == q) { cout << "0\n"; continue; } // sum(a[i]), i = p * k + q; k = 0 .. (n - q - 1) / p if ((n - q - 1) / p + 1 <= S) { int ans = 0; for (int k = 0; k <= (n - q - 1) / p; k++) { ans += a[p * k + q]; } cout << ans << '\n'; } else { // p <= S int ans = 0; for (int i = 0; i < sz(sd); i++) { ans += sd[i].calc(p, q); } cout << ans << '\n'; } } } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tests = 1; // cin >> tests; while (tests--) { solve(); } return 0; }