思路：考虑离线操作，以y为关键字排序，对于y相同的一起操作，然后考虑y的范围，当y<=sqrt(n)时，直接O(n)预处理出f[x]表示f[x]+f[x+y]+f[x+2*y]+..+f[x+k*y]的答案，然后这样的y显然不超过sqrt(n)个，复杂度也就是O(n*sqrt(n))的；如果y>sqrt(n)，那么这样直接暴力统计答案，因为答案的项数也显然不会超过sqrt(n)，这样整个算法的时间复杂度就是O(n*sqrt(n))。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 300005 int n,Q;
int a[maxn];
long long f[maxn],ans[maxn]; struct query{
int x,y,id;
bool operator <(const query &a)const{return y<a.y;}
}q[maxn]; int read(){
int x=;char ch=getchar();
for (;ch<''||ch>'';ch=getchar());
for (;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';
return x;
} int main(){
n=read();int size=sqrt(n);
for (int i=;i<=n;i++) a[i]=read();
Q=read();
for (int i=;i<=Q;i++) q[i].x=read(),q[i].y=read(),q[i].id=i;
sort(q+,q+Q+);
for (int i=;i<=Q;i++){
if (q[i].y<=size){
int y=q[i].y;
if (y!=q[i-].y) for (int j=n;j;j--) f[j]=(j+y>n?a[j]:f[j+y]+a[j]);
ans[q[i].id]=f[q[i].x];
}
else{
int x=q[i].x,y=q[i].y,id=q[i].id;
while (x<=n) ans[id]+=a[x],x+=y;
}
}
for (int i=;i<=Q;i++) printf("%I64d\n",ans[i]);
return ;
}