能量采集(bzoj 2005)
2024-08-30 00:25:22
Description
栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,
栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。 栋栋的植物种得非常整齐,一共有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的能
量损失。
Input
仅包含一行,为两个整数n和m。
Output
仅包含一个整数,表示总共产生的能量损失。
Sample Input
【样例输入1】
5 4
【样例输入2】
3 4
5 4
【样例输入2】
3 4
Sample Output
【样例输出1】
36
【样例输出2】
20
对于100%的数据:1 ≤ n, m ≤ 100,000。
36
【样例输出2】
20
对于100%的数据:1 ≤ n, m ≤ 100,000。
/*
考虑每个点对于答案的贡献,设点为(x,y),容易得出它对答案的贡献为gcd(x,y)*2-1。
重点在于求出ΣΣgcd(i,j)=Σphi(i)*(n/i)*(m/i),然后用除法分块。
*/
#include<cstdio>
#include<iostream>
#define N 100010
#define lon long long
using namespace std;
int mark[N],prime[N],phi[N],n,m,num;
lon sum[N],ans;
void get_prime(){
phi[]=;
for(int i=;i<N;i++){
if(!mark[i]) prime[++num]=i,phi[i]=i-;
for(int j=;j<=num&&i*prime[j]<N;j++){
mark[i*prime[j]]=;
phi[i*prime[j]]=phi[i]*(prime[j]-);
if(i%prime[j]==){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
for(int i=;i<N;i++) sum[i]=sum[i-]+(lon)phi[i];
}
int main(){
get_prime();
scanf("%d%d",&n,&m);
int last;
for(int i=;i<=min(n,m);i=last+){
last=min(n/(n/i),m/(m/i));
ans+=(sum[last]-sum[i-])*(lon)(n/i)*(lon)(m/i);
}
cout<<ans*-(lon)n*m;
return ;
}
最新文章
- Windows 2012 中文乱码的解决办法
- XSS Filter绕过
- [USACO2002][poj1945]Power Hungry Cows(启发式搜索)
- 关于Java的数据结构HashMap,ArrayList的使用总结及使用场景和原理分析
- MVC开发Markdown编辑器(2)
- 使用Mono Cecil 动态获取运行时数据 (Atribute形式 进行注入 用于写Log) [此文报考 xxx is declared in another module and needs to be imported的解决方法]-摘自网络
- 推荐两个针对github的chrome插件
- luci-bwc(记录流量功能)
- HDU 6043 KazaQ&#39;s Socks (规律)
- 【干货篇】步步为营,带你轻松掌握jQuery!
- birt-j脚本调试 &; 动态sql的实现
- 【洛谷3047】[USACO12FEB]附近的牛Nearby Cows
- UVA 1627 Team them up!
- hbuilder下用plus.barcode.Barcode做二维码扫描,当二维码容器的高度设置过低时,启动扫描会发生闪退
- npm --save-dev 和--save 参数的区别
- 【转】SEGGER Embedded Studio 新建stm32f103工程
- Linux 的 OOM 终结者(Out Of Memory killer)
- xampp lampp 改变网页root目录的方法
- 移植U-Boot时遇到的问题
- Windows任务计划 &; Linux crontab定时自动任务
热门文章
- 当GetWindowText获取不到标题时可以用SendMessage
- python笔记-tuple元组的方法
- 【PHP】Thinkphp 七牛云API对接
- 使用python3下载网易云音乐歌单歌曲,附源代码
- Codeforces Round #460 (Div. 2)-B. Perfect Number
- (ADO.NET)关于C#中“配置”sqlite问题
- Android开发——网易云音乐使用的开源组件集合
- lambda表达式与函数接口的关系以及使用案例
- Java JVM 内存空间解析
- mof格式的文件怎么打开?用什么工具?