题意：给你一些数，有两种操作，一种是给你一个模数x和余数y，问你在模数x的条件下，余数为y的数的总和为多少，另一种操作是修改一个位置的数值
思路：看了题解，没想到是对模数分块，小规模打表，大规模暴力，这种操作我也是第一次见，我们直接把sqrt n之内的数直接暴力求一遍，这样的复杂度是nsqrt n的
然后sqrt修改，小于sqrt n就是O1查询，大于的部分其实不超过sqrt n块，所以就sqrt n查询
代码；
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include <algorithm> using namespace std; typedef long long LL; inline LL read() { LL x=0,f=1;char ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } const int maxn=150007; int n,m; int a[maxn]; LL f[1001][1001]; int block; int main() { n=read(),m=read();block=min((int)sqrt(n),1001); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=block;i++){ for(int j=1;j<=n;j++){ f[i][j%i]+=a[j]; } } // for(int i=1;i<=n;i++){ // for(int j=1;j<=block;j++){ // f[j][i%j]+=a[i]; // } // } while(m--){ char op[5]; scanf("%s",op); if(op[0]==‘A‘){ int x=read(),y=read(); if(x<=block){ printf("%lld\n",f[x][y]); } else{ LL sum=0; y%=x; if(y==0)y=x; // printf("test %d %d %d\n",x,y,a[5]+a[10]); for(int i=y;i<=n;i+=x){ sum+=a[i]; } printf("%lld\n",sum); } } else{ int x=read(),y=read(); LL val=y-a[x]; for(int i=1;i<=block;i++){ f[i][x%i]+=val; } a[x]=y; } } return 0; }
原文：https://www.cnblogs.com/lalalatianlalu/p/9484240.html