5609

Educational Codeforces Round 71 (Rated for Div. 2)-F. Remainder Problem-技巧分块

<h1 id="educational-codeforces-round-71-rated-for-div.-2-f.-remainder-problem-技巧分块">Educational Codeforces Round 71 (Rated for Div. 2)-F. Remainder Problem-技巧分块

<hr /><h2 id="problem-description">【Problem Description】</h2>

​ 初始\([1,500000]\)都为0,后续有两种操作:

​ \(1\)、将\(a[x]\)的值加上\(y\)。

​ \(2\)、求所有满足\(i\ mod\ x=y\)的\(a[i]\)的和。

<h2 id="solution">【Solution】</h2>

​ 具体做法就是,对于前\(\sqrt{500000}=708\)个数,定义\(dp[j][k]\)表示所有满足\(i\ mod\ j=k\)的\(a[i]\)的和。每次进行\(1\)操作的时候,\(O(\sqrt{500000})\)预处理一下。查询时可\(O(1)\)查询。

​ 对于大于\(O(\sqrt{500000})\)的数,可暴力求解:\(i\ mod\ x=y\Leftrightarrow i+x\cdot t=y\)。所以只需要枚举\(\frac{500000}{x}\)次即可。而\(x\)不小于\(\sqrt{500000})=708\),所以枚举次数不大于\(708\)次,所以总复杂度为\(O(500000^{\frac{3}{2}})\)。

<hr /><h2 id="code">【Code】</h2> /* * @Author: Simon * @Date: 2019-08-28 14:34:47 * @Last Modified by: Simon * @Last Modified time: 2019-08-28 15:02:25 */ #include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define maxn 1005 #define maxm 500005 int dp[maxn][maxn]/*下标满足模i余数为j的 值的和*/,a[maxm]; int main(){ #ifndef ONLINE_JUDGE //freopen("input.in","r",stdin); //freopen("output.out","w",stdout); #endif ios::sync_with_stdio(false); cin.tie(0); int q,m=ceil(sqrt(maxm));cin>>q; while(q--){ int p,x,y;cin>>p>>x>>y; if(p==1){ a[x]+=y; for(int i=1;i<=m;i++) dp[i][x%i]+=y; } else{ if(x<=m) cout<<dp[x][y]<<endl; else{ int ans=0; for(int i=y;i<maxm;i+=x) ans+=a[i]; cout<<ans<<endl; } } } #ifndef ONLINE_JUDGE cout<<endl;system("pause"); #endif return 0; }

来源:博客园

作者:__Simon

链接:https://www.cnblogs.com/--Simon/p/11424348.html

Recommend