首页 > 代码库 > bzoj2005: [Noi2010]能量采集
bzoj2005: [Noi2010]能量采集
【题意】
一块n*m大小的田，人站在（0，0）位置。对于每个（i,j）位置的植物，从（0，0）到（i,j）的连线中有k棵植物，能量损失就为2*k-1（包括端点上的植物）。求所有植物的能量损失。
n,m<=10^5
【题解】
实际上对于每棵植物k就是x坐标,y坐标的公约数，不过n*m棵植物显然不能一个个公约数求过来。
仔细想一下最大公约数d<=min(n,m),所以我们考虑枚举d并计算一下最大公约数为d的数对个数，这个值就设为f（d）好了。
首先直接（n/d）*（m/d）计算出来的只是公约数包含d的数对，所以减去最大公约数为2*d，3*d……的数对个数。
f（d）=（n/d）*（m/d）-[f（2*d）+f（3*d）+……+f（min（n,m）/d*d）]，这个f（d）就倒着递推一遍就行了。
【代码】
1 #include <cstdio> 2 #include <iostream> 3 #define ll long long 4 using namespace std; 5 int l,n,m; 6 ll ans,f[100100]; 7 int main() 8 { 9 cin>>n>>m; 10 l=n>m?m:n; 11 for (int i=l;i;--i) 12 { 13 f[i]=(ll)(n/i)*(m/i); 14 for (int j=i+i;j<=l;j+=i) 15 f[i]-=f[j]; 16 ans=ans+f[i]*(2*i-1); 17 } 18 cout<<ans<<endl; 19 return 0; 20 }
bzoj2005: [Noi2010]能量采集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。