[2019.1.14]BZOJ2005 [Noi2010]能量采集

灰太狼 2021-12-23 22:39 164阅读 0赞

### 以下设\\(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

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关 P2048 [NOI2010]超级钢琴

题目描述小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。这架超级钢琴可以弹奏出n个音符，编号为1至n。

桃扇骨/ 2023年08月17日 15:46/ 0 赞/ 69 阅读

相关 [bzoj1951][SDOI2010]古代猪文

题目描述: 计算G^(Sigma(C(n,i)) % P，其中 i | n 题目解答：为叙述方便起见，我们令sigma()为W 显然W是一个非常大的数，如

清疚/ 2022年07月11日 13:21/ 0 赞/ 146 阅读

相关 [bzoj 4650][NOI 2016]优秀的拆分

[ 传送门 ][Link 1] Description > 如果一个字符串可以被拆分为\\(AABB\\) 的形式，其中$ A$和 \\(B\\)是任意非空字符串

水深无声/ 2022年01月09日 07:41/ 0 赞/ 168 阅读

相关「BZOJ1821」[JSOI2010] Group 部落划分

[problem][] Description 聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自

灰太狼/ 2022年01月05日 12:21/ 0 赞/ 289 阅读

相关 [2019.1.14]BZOJ2005 [Noi2010]能量采集

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

灰太狼/ 2021年12月23日 22:39/ 0 赞/ 165 阅读

相关 [BZOJ 1502][NOI2005]月下柠檬树（自适应Simpson积分）

Description 李哲非常非常喜欢柠檬树,特别是在静静的夜晚,当天空中有一弯明月温柔地照亮地面上的景物时,他必会悠闲地坐在他亲手植下的那棵柠檬树旁,独自思索着人生的哲理

古城微笑少年丶/ 2021年12月22日 08:21/ 0 赞/ 166 阅读

相关【BZOJ3545】 [ONTAK2010]Peaks

BZOJ3545 \[ONTAK2010\]Peaks -------------------- Solution 既然会加强版,直接把强制在线的操作去掉就好了.

﹏ヽ暗。殇╰゛Y/ 2021年12月20日 02:23/ 0 赞/ 121 阅读

相关 BZOJ 1562 [NOI2009] 变换序列

[\[NOI2009\] 变换序列][NOI2009_] \[题解\] 就是有一个序列，每个位置可以填两个数，不可重复，问最小字典序。显然，可以建一个二分图，判合

野性酷女/ 2021年12月17日 07:17/ 0 赞/ 182 阅读

相关 bzoj3670: [Noi2014]动物园

题意:求a\[1:i\]的2\|border|<=i的num+1乘积题解:建kmp自动机(即next\[i\]指向i),由于某个点到根就是a\[1:i\]的border,

末蓝、/ 2021年12月09日 03:43/ 0 赞/ 225 阅读

相关 bzoj1491 luogu2047 [NOI2007]社交网络

[https://www.lydsy.com/JudgeOnline/problem.php?id=1491][https_www.lydsy.com_JudgeOnline_

叁歲伎倆/ 2021年10月18日 16:20/ 0 赞/ 260 阅读