本题目思路以分块思想为框架，而具体实现却也卡了我很久，思路参见2014年国家队集训论文集中王悦同的《根号算法——不只是分块》。
太多技巧和方法需要掌握了，路漫漫其修远兮！
1 #include<iostream>
2 #include<algorithm>
3 #include<cmath>
4 #define ll long long
5 ll arr[300010];
6 ll dp[300010];
7 using namespace std;
8 struct qujian {
9 int a;
10 int b;
11 int id;
12 ll sum;
13 int operator<(const qujian& s)
14 {
15 return id < s.id;
16 }
17 }qujians[300010];
18 int cmpare(qujian a, qujian b)
19 {
20 return a.b < b.b;
21 }
22
23 inline int read()//inline 加速读入
24 {
25 int x = 0;char c = getchar();//x代表返回值，c代表读取的字符
26 while (c < '0' || c>'9') c = getchar();//读取所有非数部分
27 while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();//如果读取的字符为数，加入返回值
28 return x;
29 }
30
31 int main(void)
32 {
33 int n;
34 cin >> n;
35 for (int i = 1;i <= n;i++)
36 arr[i]=read();
37 int m;
38 cin >> m;
39 int sqr_n = sqrt(n);
40 for (int i = 1;i <= m;i++)
41 {
42 qujians[i].id = i;
43 qujians[i].a = read();
44 qujians[i].b = read();
45 }
46 //为什么要建立这样的结构体呢？因为我试过了创建一个Di[i：300010][j：600]来代表mod j后余数为i的集合，然后直接O（1）得到答案，而超了内存限制了。
47 //走qujians这条结构体是为了把输入和输出分开，对于每个b我进行一次递推，推导出每个余数的sum值，然后再赋给qujians【i】.sum。
48 //其中的两次sort来使得成功将输入和输出分离，是我学到的新东西。
49 sort(qujians, qujians + m, cmpare);
50 int b = -1;
51 for (int i = 1;i <= m;i++)
52 {
53 if (qujians[i].b < sqr_n)
54 {
55 if (qujians[i].b == b)
56 qujians[i].sum = dp[qujians[i].a];
57 else
58 {
59 b = qujians[i].b;
60 for (int j = n;j > 0;j--)
61 {
62 if (b + j > n)
63 dp[j] = arr[j];
64 else
65 dp[j] = dp[j + b] + arr[j];
66 }
67 //此处的递推方法也是让我耳目一新的，路漫漫其修远兮。。。
68 qujians[i].sum = dp[qujians[i].a];
69 }
70 }
71 else
72 {
73 qujians[i].sum = 0;
74 for (int j = qujians[i].a;j <= n;j += qujians[i].b)
75 qujians[i].sum += arr[j];
76 }
77 }
78 sort(qujians, qujians + m);
79 for (int i = 1;i <= m;i++)
80 printf("%lld\n",qujians[i].sum );
81 return 0;
82 }