Remainder Problem

这个其实并不难，只是看看考察有没有分块的思路

思路：用一个ans[i][j]来记录所有k=(1~5e5)中所有a[k]%i==j的和，在查询的时候可以达到复杂度位O(1)

当然因为数据很大，不能够分很多块，而且也没有必要分很多块，因为如果在进行2操作的时候，如果x=1e5,y=1e5-1，那么在数据范围内只有五个数满足条件，可以每次跳过x个数计算值的和，操作：
ll Ans=0;

for(int i=y;i<=int(5e5);i+=x) Ans+=a[i];

cout<<Ans<<endl;
另外：还发现了，在输出换行的时候使用cout<<'\n'会比cout<<endl块很多，甚至差一倍，因为cout<<endl还要清空缓存区，所以会慢一点

代码：

// Created by CAD on 2019/8/24.

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int blo=280;

const int maxn=5e5+5;

ll ans[blo+5][blo+5];

int a[maxn];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);cout.tie(0);

    int t; cin>>t;

    while(t--)

    {

        int op,x,y; cin>>op>>x>>y;

        if(op==1)

        {

            a[x]+=y;

            for(int i=1;i<=blo;++i) ans[i][x%i]+=y;

        }

        else

        {

            if(x<=blo) cout<<ans[x][y]<<'\n';

            else

            {

                ll Ans=0;

                for(int i=y;i<=int(5e5);i+=x) Ans+=a[i];

                cout<<Ans<<'\n';

            }

        }

    }

    return 0;

}

巴特西

Remainder Problem

最新文章

热门文章