Educational Codeforces Round 71 (Rated for Div. 2)

F - Remainder Problem

Description

*2100

一个最多 500000 个元素的序列，默认所有元素都是 0，支持以下两种操作：

• 1 x y：将 $a_x$ 增加 $y$；
• 2 x y：计算 $\sum\limits_{i \in R(x, y)} a_i$，其中 $R(x,y)$ 表示 1 到 500000 中模 $x$ 余 $y$ 的数字集合。

数据范围：$1 \le q \le 500000$。

Solution

这好像是 XJOI 上做过的原题，分块，就是找不到了 qwq

分块个毛线

直接 $F(x,y)$ 表示满足 $i \bmod x=y$ 的 $\sum a_i$ 不就好了？？
操作 2 如果 $x\le 700$ 就直接 $F(x,y)$，否则直接数组里去跳……
就是这么暴力……

Code

#include 
using namespace std;

//#define int long long
inline int read(){

int ret=0,f=1;char ch=getchar();

while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}

while (ch>='0'&&ch<='9') ret=ret10+ch-'0',ch=getchar();

return retf;

}
const int maxn=500005;

const int N=500000;
int q;

int a[maxn];

int f[705][705];
signed main() {

q=read();

while (q--){

int opt=read(),x=read(),y=read();

if (opt==1){

a[x]+=y;

for (int i=1;i<=700;i++) f[i][x%i]+=y;

} else {

if (x<=700) printf("%d\n",f[x][y]); else {

int ans=0;

for (int i=y;i<=N;i+=x) ans+=a[i];

printf("%d\n",ans);

}

}

}

return 0;

}