HUST 1061 Shepherd http://acm.hust.edu.cn/problem.php?id=1601

p1601.cpp

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

const int N = 100000;

int n, m, w[N], a[N], b[N], order[N];
long long sum[N], result[N];

bool by_b(int i, int j) {
    return b[i] < b[j];
}

int main() {
    while (scanf("%d", &n) == 1) {
        assert(1 <= n && n <= N);
        for (int i = 0; i < n; ++ i) {
            assert(scanf("%d", w + i) == 1);
            assert(1 <= w[i] && w[i] <= 1000000000);
        }
        int magic = (int)(sqrt(n) + 0.5);
        assert(scanf("%d", &m) == 1);
        assert(1 <= m && m <= N);
        for (int i = 0; i < m; ++ i) {
            assert(scanf("%d%d", a + i, b + i) == 2);
            assert(1 <= a[i] && a[i] <= n);
            assert(0 <= b[i] && b[i] <= n);
            a[i] --;
            order[i] = i;
        }
        std::sort(order, order + m, by_b);
        for (int i = 0; i < m; ++ i) {
            int d = b[order[i]];
            if (d < magic) {
                if (!i || b[order[i - 1]] < d) {
                    for (int j = n - 1; j >= 0; -- j) {
                        sum[j] = w[j];
                        if (d && j + d < n) {
                            sum[j] += sum[j + d];
                        }
                    }
                }
                result[order[i]] = sum[a[order[i]]];
            } else {
                long long &ref = result[order[i]];
                ref = 0;
                for (int j = a[order[i]]; j < n; j += d) {
                    ref += w[j];
                }
            }
        }
        for (int i = 0; i < m; ++ i) {
            printf("%lld\n", result[i]);
        }
    }
}