F. Remainder Problem 根号分治

Problem - F - Codeforces

 题意：一个500000长度的数列，一开始都是0，进行q次操作，操作如下

　　1，输入x,y，令a[x]+=y。

　　2，输入x,y，输出对于sum(a[idx])，idx的条件是idx=x%y。

做法：如果我们模拟做，那么第一种操作就是o(1)，第二种操作就是o(n)。

我们换种想法， 建立一个二维数组 b[x][y]，表示对于idx%x=y的a[idx]的sum，这种做法下，第一种的操作是o(n)，第二种操作是o(1)。

我们考虑融合两种想法，取二者之长。于是我们的做法就出炉了：

　　对于小于等于sqrt（500000）的而言，我们采用第二种操作，其复杂度为sqrt（500000）。

　　对于大于sqrt（500000）的而言，我们采用第一种操作，其复杂度同样最大为sqrt（500000）；

void solve(){
    int q;cin>>q;
    vector<int>a(500010);
    int m=sqrt(500000);
    vector<vector<int>>b(m+1);//b[x][y]  modx=y;
    for(int i=1;i<=m;i++)b[i].resize(i);
    while(q--){
        int op;cin>>op;
        if(op==1){
            int x,y;cin>>x>>y;
                for(int i=1;i<=m;i++)b[i][x%i]+=y;
                a[x]+=y;
        }
        else{
            int x,y;cin>>x>>y;
            if(x<=m)cout<<b[x][y]<<"\n";
            else{
                int sum=0;
                for(int i=y;i<=500000;i+=x)sum+=a[i];
                    cout<<sum<<"\n";
            }
        }
    }
}