/**
题目:bzoj2005 能量采集
链接:https://vjudge.net/contest/178455#problem/F
题意:栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,
栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。 栋栋的植物种得非常整齐,一共有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的能
量损失。 思路:
等价于求sigma(gcd(x,y)*2-1) (1<=x<=n,1<=y<=m); = sigma(gcd(x,y)*2)-n*m = 2*sigma(gcd(x,y)) - n*m = 2*sigma(k*gcd) - n*m;(k表示gcd出现的次数) 数据范围小的时候:
定义:
f(n)表示gcd(x,y)==n的对数。
F(n)表示n|gcd(x,y)的对数。 因为F(n)包含了gcd是n的倍数的值。所以要把他们减掉。 f(n) = F(n)-f(2*n)-f(3*n)-..-f(k*n); (k*n<=min(n,m)) 后面的n,m是数据范围. 逆序处理即可,注意溢出!!! 数据范围大的时候:
定义:
f(n)表示gcd(x,y)==n的对数。
F(n)表示n|gcd(x,y)的对数。 枚举gcd==p,1<=p<=min(n,m); f(p) = sigma(mu[d/p]*F(d)) (p|d) F(d) = (n/d)*(m/d); f(p)表示gcd(x,y)==p的对数。x在[1,n],y在[1,m];等价于:求f(1)表示gcd(x,y)==1的对数。x在[1,n/p],y在[1,m/p]; 用除法的取值,预处理莫比乌斯前缀和。 N*sqrt(N)复杂度。 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int, int> P;
const LL INF = 1e10;
const int mod = 1e9 + ;
const int maxn = 1e5 + ;
LL f[maxn], g[maxn];
/*
int prime[maxn], tot, not_prime[maxn];
int mu[maxn], sum[maxn];
void init()
{
mu[1] = 1;
tot = 0;
for(int i = 2; i < maxn; i++){
if(!not_prime[i]){
prime[++tot] = i;
mu[i] = -1;
}
for(int j = 1; prime[j]*i<maxn; j++){
not_prime[prime[j]*i] = 1;
if(i%prime[j]==0){
mu[prime[j]*i] = 0;
break;
}
mu[prime[j]*i] = -mu[i];
}
}
for(int i = 1; i < maxn; i++) sum[i] = sum[i-1]+mu[i];
}
LL solve(int n,int m)///x在[1,n], y在[1,m] gcd(x,y)=1的对数。
{
LL ans = 0;
int last;
for(int i = 1; i <= n; i=last+1){
last = min(n/(n/i),m/(m/i));
ans += (LL)(sum[last]-sum[i-1])*(n/i)*(m/i);
}
return ans;
}*/
int main()
{
//freopen("in.txt","r",stdin);
int T;
int n, m;
//init();
while(scanf("%d%d",&n,&m)==)
{
if(n>m) swap(n,m);
LL ans = ;
for(int i = n; i >= ; i--){
g[i] = (LL)(n/i)*(m/i);
for(int j = i*; j <= n; j+=i){
g[i] -= f[j];
}
f[i] = g[i];
ans += i*f[i];
} printf("%lld\n",ans*-(LL)n*m);///溢出了啊。
}
return ;
}

最新文章

  1. 1001 数组中和等于K的数对 1090 3个数和为0
  2. Ubuntu14.04 Django Mysql安装部署全过程
  3. jquery_ui_api中文
  4. java jar包解析:打包文件,引入文件
  5. 八 mybatis查询缓存(一级缓存,二级缓存)和ehcache整合
  6. gtd好文两篇收藏
  7. apache httpclient 4.5 兼容 http https
  8. JQuery 插件 - 弹窗:BlockUI
  9. win7 删除服务
  10. POJ 2756 Autumn is a Genius 采用string大数减法
  11. php追加数组
  12. Java实现猜字母游戏
  13. IFrame父页面和子页面的交互
  14. python_10_文件操作
  15. weblogic部署web项目出现错误
  16. 安卓笔记-可以滚动的TextView
  17. HDU1237
  18. 关于Java方法重载
  19. 用antd和webview打造一款大数据客户端程序
  20. [LeetCode]最大系列(最大正方形221,最大加号标志764)

热门文章

  1. 构建高可用Linux服务器二
  2. SQL Server datetime数据类型设计、优化误区
  3. [Tools] Batch Create Markdown Files from a Template with Node.js and Mustache
  4. Hibernate关系映射(一) 基于外键的单向一对一
  5. nginx听课随记杂记
  6. jConsole,jvisualvm和jmap使用
  7. 分享一下自己ios开发笔记
  8. 【微信小程序】loading标签使用,可自定义时长
  9. C#代码覆盖率 -vsinstr和OpenCover
  10. C#通过webbrowser控件与javascript交互