首页 > 代码库 > 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 }
View Code

 

bzoj2005: [Noi2010]能量采集