[NOI2010]能量采集 解题报告
[NOI2010]能量采集
题目描述
栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。
栋栋的植物种得非常整齐,一共有\(n\)列,每列有\(m\)棵,植物的横竖间距都一样,因此对于每一棵植物,栋栋可以用一个坐标\((x, y)\)来表示,其中\(x\)的范围是\(1\)至\(n\),表示是在第\(x\)列,\(y\)的范围是\(1\)至\(m\),表示是在第\(x\)列的第\(y\)棵。
由于能量汇集机器较大,不便移动,栋栋将它放在了一个角上,坐标正好是\((0,0)\)。
能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有\(k\)棵植物,则能 量的损失为\(2k + 1\)。例如,当能量汇集机器收集坐标为\((2, 4)\)的植物时,由于连接线段上存在一棵植物\((1, 2)\),会产生\(3\)的能量损失。注意,如果一棵植物与能量汇集机器连接的线段上没有植物,则能量损失为\(1\)。现在要计算总的能量损失。
下面给出了一个能量采集的例子,其中\(n = 5\),\(m = 4\),一共有\(20\)棵植物,在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失。
在这个例子中,总共产生了\(36\)的能量损失。
输入输出格式
输入格式:
仅包含一行,为两个整数\(n\)和\(m\)。
输出格式:
仅包含一个整数,表示总共产生的能量损失。
说明
对于\(10\%\)的数据:\(1 ≤ n, m ≤ 10\);
对于\(50\%\)的数据:\(1 ≤ n, m ≤ 100\);
对于\(80\%\)的数据:\(1 ≤ n, m ≤ 1000\);
对于\(90\%\)的数据:\(1 ≤ n, m ≤ 10,000\);
对于\(100\%\)的数据:\(1 ≤ n, m ≤ 100,000\)。
题意:求
\]
直接暴力推式子了
\]
\]
设\(a=\lfloor\frac{n}{k}\rfloor,b=\lfloor\frac{m}{k}\rfloor\)
\]
\]
\]
\]
\]
到这里虽然不够优,但是显然已经可以了。
复杂度:\(O(\sum\limits_{i=1}^ni^{\frac{1}{2}})\)其实就是\(O(n\sqrt n)\)
Code:
#include <cstdio>
#define ll long long
const int N=1e5;
ll ans=0;
int mu[N+10],pri[N+10],ispri[N+10],cnt;
void init()
{
for(int i=2;i<=N;i++)
{
if(!ispri[i])
{
mu[i]=-1;
pri[++cnt]=i;
}
for(int j=1;j<=cnt&&pri[j]*i<=N;j++)
{
ispri[i*pri[j]]=1;
if(i%pri[j]==0) break;
else mu[i*pri[j]]=-mu[i];
}
}
mu[1]=1;
for(int i=2;i<=N;i++) mu[i]+=mu[i-1];
}
int n,m;
int min(int x,int y){return x<y?x:y;}
int main()
{
init();
scanf("%d%d",&n,&m);
for(int k=1;k<=min(n,m);k++)
{
int a=n/k,b=m/k;
ll sum=0;
for(int l=1,r;l<=min(a,b);l=r+1)
{
r=min(a/(a/l),b/(b/l));
sum+=1ll*(mu[r]-mu[l-1])*(a/l)*(b/l);
}
ans+=sum*k;
}
printf("%lld\n",ans*2ll-1ll*n*m);
return 0;
}
2018.10.21
最新文章
- ASP.NET MVC Razor
- JS中修改属性
- hdu 5927 Auxiliary Set
- Docker指令集
- oracle常见小问题解答ORA-01008,ORA-01036
- dataTable 禁止排序
- PAT_1072 Gas Station
- java中的String.format使用
- C#计算某个时间距离当前日期的天数
- 五年26个版本:Linux系统内核全程回顾
- lazyMan
- 选择 25k 的 996 还是 18k 的 965
- 在github上创建自己的项目
- python_study-1
- 鼠标监听事件MouseListener
- SpringMVC(三):参数绑定、输入输出转换
- 不用ajax实现异步请求:XmlHttpRequest 小记
- for循环中进行联网请求数据、for循环中进行异步数据操作,数据排序错乱问题解决;
- 在Ubuntu 14.04 64bit上安装百度云Linux客户端BCloud
- (五)ROS节点