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=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

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;
}