栋栋有一块长方形的地, 他在地上种了一种能量植物, 这种植物可以采集太阳光的能量. 在这些植物采集能量后, 栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起.
栋栋的植物种得非常整齐, 一共有 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[100009];
- int main()
- {
- cin>>n>>m;mi=min(m,n);
- for(int i=mi;i>=1;--i)
- {
- f[i]=(long long)(m/i)*(n/i);
- for(int j=(i<<1);j<=mi;j+=i)f[i]-=f[j];
- ans+=f[i]*(i*2-1);
- }
- cout<<ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2795433.html