T5

T5.

本题考虑分块做法。由于本题只有查询，所以我们可以想到离线做，我们只需要考虑两种情况：

• 1.当步长 $\geq sqrt(n)$的时候，那么每次只要走 $sqrt(n)$步就能走完，我们可以暴力走，最坏时间复杂度$O(n\sqrt{n})$。
• 2.当步长 $\leq sqrt(n)$的时候，这样步长很小，暴力会超时，但是可以发现这样的步长的种类不是很多，我们可以按步长进行排序，虽然起点可能不一样，但是终点都是在最后一个长度为$sqrt(n)$的块里面，所以我们可以从后往前推即可。这样的时间复杂度最坏也是 $O(n\sqrt{n})$。

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 300010;
int n, a[N], q, last = -1;
LL prex[N], ans[N];
vector<array<int,3>>que;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    int Block = sqrt(n);
    cin >> q;
    for(int i = 1; i <= q; i ++ ){
        int x, y; cin >> x >> y;
        que.push_back({x, y, i});
    }
    sort(que.begin(), que.end(),[&](array<int,3> A, array<int,3> B){
        return A[1] < B[1];
    });
    for(int i = 0; i < q; i ++ ){
        int b = que[i][1];
        int st = que[i][0];
        int idx = que[i][2];
        if(b >= Block){
            LL sum = 0;
            for(int j = st; j <= n; j += b){
                sum += a[j];
            }
            ans[idx] = sum;
        }else{
            if(last == b){
                ans[idx] = prex[st];
                continue;
            } 
            for(int j = n; j >= 1; j -- ){
                if(j + b > n) prex[j] = a[j];
                else prex[j] = prex[j + b] + a[j];
            }
            ans[idx] = prex[st];
            last = b;
        }
    }
    for(int i = 1; i <= q; i ++ ){
        cout << ans[i] << '\n';
    }
    return 0;
}