HUST 1601 Shepherd

Description

Hehe keeps a flock of sheep, numbered from 1 to n and each with a weight  wi. To keep the sheep healthy, he prepared some training for his sheep.  Everytime he selects a pair of numbers (a,b), and chooses the sheep with number a, a+b, a+  2b, … to get trained. For the distance between the sheepfold and the training site is too far, he needs to arrange a truck with appropriate loading capability to transport those sheep. So he wants to know the total weight of the sheep he selected each time, and he finds you to help him. 

Input

There’re several test cases. For each case: 
The first line contains a positive integer n (  1≤n≤10^5)---the number of sheep  Hehe keeps. 
The second line contains n positive integer  wi(  1≤n≤10^9), separated by spaces, where the  i-th number describes the weight of the  i-thsheep. 
The third line contains a positive integer q (  1≤q≤10^5)---the number of training plans  Hehe prepared. 
Each following line contains integer parameters a and b (  1≤a,  b≤n)of the corresponding plan. 

Output

For each plan (the same order in the input), print the total weight of sheep selected. 

Sample Input

5 1 2 3 4 5 3 1 1 2 2 3 3

Sample Output

15 6

3

可以先预处理出间隔为1到60的前缀和，然后超过60的暴力就好了，本来这题应该是离线nsqrt（n）的，然而数据太水了，而且数据也是错的，明明说了b>=1，结果竟然有0的，暴力也能跑的过去，只能说数据太有问题了

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
int n,m,a[maxn],x,y;
LL sum[maxn][61];

int main()
{
  while (~scanf("%d",&n))
  {
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    int k=min(60,n);
    for (int i=n;i>=1;i--)
    {
      for (int j=1;j<=k;j++)
      {
        if (i+j<=n) sum[i][j]=sum[i+j][j]+a[i];
        else sum[i][j]=a[i];
      }
    }
    scanf("%d",&m);
    while (m--)
    {
      scanf("%d%d",&x,&y);
      if (y>k)
      {
        LL ans=0;
        for (int i=x;i<=n;i+=y) ans+=a[i];
        printf("%lld\n",ans);
      }
      else if (y) printf("%lld\n",sum[x][y]);
      else printf("%d\n",a[x]);
    }
  }
  return 0;
}