学步园

这题的官方时限是4s，开始直接爆，果然TLE了==后来优化了一下，1420ms过了。。。所以说坑爹啊！！！

优化方法是因为题目中的b是数与数之间的间隔，当间隔大于600时可以直接遍历，当小于600时就要记录处于当前间隔的情况有多少种，然后从后向前推，推得的tmp[j]表示j~n间隔为i的和（相当于预处理），这样就把最坏的复杂度降了下来，以后就直接O(1)就找到当前的答案。

#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <time.h>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <cstdlib>
#include <limits.h>
#include <string.h>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

#define LL long long
#define MIN INT_MIN
#define MAX INT_MAX
#define PI acos(-1.0)
#define FRE freopen ("input.txt","r",stdin)
#define FF  freopen ("output.txt","w",stdout)
#define eps 1e-8
#define N 300005
LL num[N];
LL tmp[N];
struct node {
    int id;
    int a,b;
    LL ans;
    node(){
        ans = 0;
    }
}p[N];
vector<node> v[N];
int main(){
    int n;
    scanf("%d",&n);
    int i,j;
    for (i = 1; i <= n; i++) {
        scanf("%d",&num[i]);
    }
    int m;
    scanf("%d",&m);
    for (i = 1; i <= m; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        p[i].a = a;
        p[i].b = b;
        p[i].id = i;
        p[i].ans = 0;
        if (b > 400) {
            for (j = a; j <= n; j+=b ){
                p[i].ans += num[j];
            }
        }else
        v[b].push_back(p[i]);
    }
    for (i = 1; i <= 400; i++ ){
        if (v[i].size() > 0){
            for (j = n; j >= 1; j--) {
                tmp[j] = num[j];
                if (i+j <= n) {
                    tmp[j] += tmp[i+j];
                }
            }
            for (j = 0; j < v[i].size(); j++) {
                p[v[i][j].id].ans = tmp[v[i][j].a];
            }
        }
    }
    for (i = 1; i <= m; i++){
        printf("%I64d\n",p[i].ans);
    }
    return 0;
}