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棵植物，在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失。

题意为求1-n之间的所有数和1-m之间的所有数两两之间的GCD。
一道非常经典的莫比乌斯反演的例题，但有一种容斥的方法更加简单。

考虑枚举每个gcd，那么gcd为当前gcd的倍数的数对就有n/gcd*m/gcd个。

在考虑把多余的方案去掉，只要枚举gcd的所有倍数，把它们都减掉就好了。

做的时候就倒着枚举gcd就可以了。

#include<iostream>

#include<cstdio>

using namespace std;

int gcd(int x,int y){return y?gcd(y,x%y):x;}

int n,m,mi;

long long ans,f[];

int main()

{

    cin>>n>>m;mi=min(m,n);

     for(int i=mi;i>=;--i)

      {

          f[i]=(long long)(m/i)*(n/i);

          for(int j=(i<<);j<=mi;j+=i)f[i]-=f[j];

          ans+=f[i]*(i*-);

      }

    cout<<ans;

    return ;

}

巴特西

NOI2010能量采集(数学)

最新文章

热门文章