思路
暴力 (O(n^2).) 期望得分: (9.)
考虑到此题有两种做法：
(1.) (O(n^2)) 复杂度，每次询问的时候累加：
ans = 0;
for (int q = y;q <= n;q += x) {
ans += a[q];
}
printf ("%d
",ans);
(2.) (O(n^2)) 的时间预处理，设 (f[i][j]) 表示模 (i) 等于 (j) 的数字总和。
for (int q = 1;q <= n;++ q) {
for (int w = 1;w <= n;++ w) {
f[w][q % w] += a[q];
}
}
于是便有了一种新的思想，根号分治。
顾名思义，根号分治就是前 (sqrt{n}) 的数据预处理，剩下的暴力求解。
预处理复杂度为 (O(nsqrt{n})) ，那么剩下的询问 (p) 就超过了 (sqrt{n}) ，此时只有不到 (sqrt{n}) 个数对他有贡献，每一次暴力的复杂度 (O(sqrt{n}))
剩下还有更改，需要 (O(sqrt{n})) 的时间处理 (f) 数组。
总的时间复杂度是 (O((m + n)sqrt{n}).)
代码
暴力：(小学生都会写的)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 50010;
int n, m ,a[MAXN] ,ans;
int main () {
scanf ("%d%d",&n ,&m);
for (int q = 1;q <= n;++ q)
scanf ("%d",&a[q]);
int x ,y;
while (m --) {
ans = 0;
char ch = getchar ();
while (ch != 'A' && ch != 'C') ch = getchar ();
scanf ("%d%d",&x ,&y);
if (ch == 'A') {
for (int q = 1;q <= n;++ q) {
if (q % x == y) ans += a[q];
}
printf ("%d
",ans);
}
else a[x] = y;
}
return 0;
}
正解：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 50010;
int n ,m ,a[MAXN];
int f[401][401];//f[i][j]表示模 i 余 j 的池的数的总和
int main () {
scanf ("%d%d",&n ,&m);
for (int q = 1;q <= n;++ q)
scanf ("%d",&a[q]);
int siz = sqrt (n);
for (int q = 1;q <= n;++ q) {
for (int w = 1;w <= siz;++ w) {
f[w][q % w] += a[q];
}
}
// for (int q = 1;q <= siz;++ q) {
// for (int w = 1;w <= siz;++ w) {
// printf ("mod %d = %d sum: %d
",q ,w ,f[q][w]);
// }
// }
int x ,y ,ans;
char ch;
while (m --) {
ch = getchar ();
while (ch != 'A' && ch != 'C') ch = getchar ();
scanf ("%d%d",&x ,&y);
if (ch == 'A') {
if (x <= siz) {
printf ("%d
",f[x][y]);
}
else {
ans = 0;
for (int q = y;q <= n;q += x) {
ans += a[q];
}
printf ("%d
",ans);
}
}
else {
int add_ = y - a[x];
for (int w = 1;w <= siz;++ w) {
f[w][x % w] += add_;
}
a[x] = y;
}
}
return 0;
}