首页 > 代码库 > [NOI2010]能量采集
[NOI2010]能量采集
469. [NOI2010]能量采集
★★☆ 输入文件：energy2010.in 输出文件：energy2010.out 简单对比时间限制：1 s 内存限制：512 MB
【问题描述】
栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。
栋栋的植物种得非常整齐，一共有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。
【输出格式】
仅包含一个整数，表示总共产生的能量损失。
【样例输入1】
5 4
【样例输出1】
36
【样例输入2】
3 4
【样例输出2】
20
【数据规模和约定】
对于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。
由题意列式：
最终化简：
1
#include<cstdio>#include<iostream>using namespace std;typedef long long ll;const int N=1e5+5;int n,m,tot,prime[N/3],phi[N],sum[N];bool check[N];ll ans;void prepare(){ phi[1]=1; for(int i=2;i<=n;i++){ if(!check[i]) prime[++tot]=i,phi[i]=i-1; for(int j=1;j<=tot&&i*prime[j]<=n;j++){ check[i*prime[j]]=1; if(!(i%prime[j])){phi[i*prime[j]]=phi[i]*prime[j];break;} else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];}void solve(){ for(int i=1,pos;i<=n;i=pos+1){ pos=min(n/(n/i),m/(m/i)); ans+=1LL*(n/i)*(m/i)*(sum[pos]-sum[i-1]); } ans<<=1;ans-=1LL*n*m; printf("%lld",ans);}int main(){ freopen("energy2010.in","r",stdin); freopen("energy2010.out","w",stdout); scanf("%d%d",&n,&m); if(n>m) swap(n,m); prepare(); solve(); return 0;}
2
#include<cstdio>#include<iostream>using namespace std;typedef long long ll;const int N=1e5+5;int n,m,tot,prime[N/3],phi[N],sum[N];bool check[N];ll ans;void prepare(){ phi[1]=1; for(int i=2;i<=n;i++){ if(!check[i]) prime[++tot]=i,phi[i]=i-1; for(int j=1;j<=tot&&i*prime[j]<=n;j++){ check[i*prime[j]]=1; if(!(i%prime[j])){phi[i*prime[j]]=phi[i]*prime[j];break;} else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];}void solve(){ for(int i=1,pos;i<=n;i=pos+1){ pos=min(n/(n/i),m/(m/i)); ans+=1LL*(n/i)*(m/i)*(sum[pos]-sum[i-1]); } ans<<=1;ans-=1LL*n*m; printf("%lld",ans);}int main(){ freopen("energy2010.in","r",stdin); freopen("energy2010.out","w",stdout); scanf("%d%d",&n,&m); if(n>m) swap(n,m); prepare(); solve(); return 0;}
[NOI2010]能量采集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。