[2019.1.14]BZOJ2005 [Noi2010]能量采集

以下设\(n\ge m\)。

首先,一个点\((x,y)\)到\((0,0)\)的路径上经过的点的数量(不包括首尾)为\(gcd(x,y)-1\)。

所以它的能量损耗为\(2\times gcd(x,y)-1\)。

考虑如何统计\(\sum_{i=1}^n\sum_{j=1}^m 2\times gcd(i,j)-1\)。

记\(f_x=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=x]\),即\(1\le i\le n,1\le j\le m\)时,\(gcd(i,j)=x\)的数量。

我们再记\(F_x=\sum_{x|i}f_i\)。

莫名其妙想到了莫比乌斯反演,但是在这里显然不能用

我们发现\(F(x)\)其实就是满足\(1\le i\le n,1\le j\le m,i|x,j|x\)的\((i,j)\)数量,即\(\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor\)。

我们还发现\(f_i=F_i-\sum_{x=2}^{\lfloor\frac{n}{i}\rfloor}f_{xi}\),即\(F_i\)减去 \(f_k\)的和 ,其中\(k\)是\(i\)的倍数且不等于\(i\)。

于是我们从大到小枚举\(i\)并计算\(f_i\),答案就是\(\sum_{i=1}^n(2\times i-1)\times f_i\)。

根据调和级数,其时间复杂度为\(O(nlogn)\)。

code:

#include<bits/stdc++.h> using namespace std; int n,m; long long num[100010],ans; int main(){scanf("%d%d",&n,&m),n<m?swap(n,m),0:0;for(int i=n;i>=1;--i){num[i]=1ll*(n/i)*(m/i);for(int j=i+i;j<=n;j+=i)num[i]-=num[j];ans+=(2*i-1)*num[i];}printf("%lld",ans);return 0; }

转载于:https://www.cnblogs.com/xryjr233/p/BZOJ2005.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的[2019.1.14]BZOJ2005 [Noi2010]能量采集的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。