题目描述
众所周知，模数的hash会产生冲突。例如，如果模的数p=7，那么4和11便冲突了。
B君对hash冲突很感兴趣。他会给出一个正整数序列value[]。
自然，B君会把这些数据存进hash池。第value[k]会被存进(k%p)这个池。这样就能造成很多冲突。
B君会给定许多个p和x，询问在模p时，x这个池内数的总和。
另外，B君会随时更改value[k]。每次更改立即生效。
保证1<=p<n1<=p<n.
输入输出格式
输入格式：
第一行，两个正整数n,m，其中n代表序列长度，m代表B君的操作次数。
第一行，n个正整数，代表初始序列。
接下来m行，首先是一个字符cmd，然后是两个整数x,y。
-
若
cmd='A'，则询问在模x时，y池内数的总和。 -
若
cmd='C'，则将value[x]修改为y。
输出格式：
对于每个询问输出一个正整数，进行回答。
输入输出样例
输入样例#1：
10 51 2 3 4 5 6 7 8 9 10A 2 1C 1 20A 3 1C 5 1A 5 0
输出样例#1：
254111
说明
样例解释
A 2 1的答案是1+3+5+7+9=25.
A 3 1的答案是20+4+7+10=41.
A 5 0的答案是1+10=11.
数据规模
对于10%的数据，有n<=1000,m<=1000.
对于60%的数据，有n<=100000.m<=100000.
对于100%的数据，有n<=150000,m<=150000.
保证所有数据合法，且1<=value[i]<=1000.
题解
- 我们可以设f[i][j]为在模i意义下余数为j的个数
- 那么显然发现，这样直接做是过不了滴
- 考虑一下分块
- 然后我们以 sqrt(
1 #include2 #include 3 #include 4 #include 5 #include 6 #define ll long long 7 using namespace std; 8 int n,m,x,y,a[150010]; 9 ll f[400][400];10 char ch;11 int main()12 {13 scanf("%d%d",&n,&m);14 for (int i=1;i<=n;i++) 15 {16 scanf("%d",&a[i]);17 for (int j=1;j<=sqrt(n);j++) f[j][i%j]+=a[i];18 }19 while (m--)20 {21 scanf("\n%c%d%d",&ch,&x,&y);22 if (ch=='A')23 {24 if (x*x<=n) printf("%lld\n",f[x][y]);25 else 26 {27 ll sum=0;28 for (int i=y;i<=n;i+=x) sum+=a[i];29 printf("%lld\n",sum);30 }31 }32 else 33 {34 for (int i=1;i<=sqrt(n);i++) f[i][x%i]+=y-a[x];35 a[x]=y;36 }37 }38 }