复杂度为$n \sqrt n$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 300010;
// \sqrt maxn = 548
int a[maxn], f[600][600];
int n, m;

struct node{
	int t, k;
	int ans, dfn;
};
node que[maxn];
bool cmp(node x, node y) {
	return x.t > y.t;
}
bool cmp2(node x, node y) {
	return x.dfn < y.dfn;
}

void run(int t, int k) {
	if(t > 548) {
		int ans = 0;
		for(int i=t; i<=n; i+=k) {
			ans += a[i];
		}
		cout << ans << endl;
	} else {
		cout << f[t][k] << endl;
	}
}
int dp[maxn+1000];
void run(int idx) {
	int ans = 0;
	if(que[idx].k >= 548) {
		for(int i=que[idx].t; i<=n; i+=que[idx].k) {
			ans += a[i];
		}
		que[idx].ans = ans;
	} else {
		if(que[idx].k == que[idx-1].k and idx != 1) {
			que[idx].ans = dp[que[idx].t];
			return;
		} else {
			for(int i=n; i>=1; --i) {
				dp[i] = dp[i+que[idx].k] + a[i];
			}
			que[idx].ans = dp[que[idx].t];
		}
	}
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; ++i) {
		cin >> a[i];
	}
	cin >> m;
	for(int i=1; i<=m; ++i) {
		cin >> que[i].t >> que[i].k;
		que[i].dfn = i;
	}
	sort(que+1, que+1+m, cmp);
	for(int i=1; i<=m; ++i) {
		run(i);
	}
	sort(que+1, que+1+m, cmp2);
	for(int i=1; i<=m; ++i) {
		cout << que[i].ans << endl;
	} 
	return 0;
}