Yuan
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
noi 2010 能量采集 八中2005 ★★★ 公约数确定的对数
/**/
/*
题意:原题可转化为求在n*m范围内
n m
∑∑ 2*(gcd(x,y)-1)+1
x=1 y=1
感觉挺像visible trees的用容斥做,但不会容斥做
看了
http://hi.baidu.com/570193465/blog/item/d4219303d7b43e1c738b6547.html
O(nsqrt(n))
对于上式,重点是求出 t=gcd(x,y) 时的(x,y)对数
可以枚举gcd
记录cnt[i] = (n/i)*(m/i) 即公约数是i的倍数(k*i)的对数
然后再调整cnt[i],使其表示公约数是i的对数
cnt[i]-=cnt[k*i]即可!
*/
#include
<
cstdio
>
#include
<
cstring
>
inline
int
min(
int
a,
int
b)
{
return
a
<
b
?
a:b;}
const
int
MAXN
=
100010
;
long
long
cnt[MAXN];
int
main()
{
int
n,m;
while
(
~
scanf(
"
%d%d
"
,
&
n,
&
m))
{
int
t
=
min(n,m);
for
(
int
i
=
2
;i
<=
t;i
++
)
//
gcd = i
cnt[i]
=
(
long
long
)(n
/
i)
*
(m
/
i);
//
cnt[i] : the number of whose gcd is k*i
for
(
int
i
=
t;i
>=
1
;i
--
)
for
(
int
k
=
2
;k
*
i
<=
t;k
++
)
cnt[i]
-=
cnt[k
*
i];
//
to get the real number of whose gc is i
long
long
ans
=
0
;
for
(
int
i
=
1
;i
<=
t;i
++
)
ans
+=
2
*
(i
-
1
)
*
cnt[i];
printf(
"
%I64d\n
"
,ans
+
(
long
long
)n
*
m);
}
return
0
;
}
发表于 2010-09-07 23:59
_Yuan
阅读(540)
评论(2)
编辑
收藏
引用
所属分类:
OJ解题报告
评论
#
re: noi 2010 能量采集 八中2005 ★★★ 公约数确定的对数
赞一个~代码好短
#
re: noi 2010 能量采集 八中2005 ★★★ 公约数确定的对数
@LitIce
那个是看别人写的 #_#
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
SRM 239 HiddenTriangles ★★★★
CodeForces 59E 以边为状态bfs ★★★★
TCO'10 Wildcard Round 500pt CalculationCards
zoj 3462 bitset
SRM 496 PalindromfulString 容斥写法 ★★★★
CodeForces 57D
CodeForces 55D 数位统计 记忆化搜索 跟pre有关 ★★★★
CodeForces 55E Very simple problem
zoj 3455 统计出现次数 判断相等 用l[i]记录字母出现i次的个数 ★★★★
zoj 3354 映射 环 计数 ★★★
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
常用链接
我的随笔
我的评论
我参与的随笔
随笔分类
Dp(27)
(rss)
OJ解题报告(153)
(rss)
OThers(17)
(rss)
TopCoder
(rss)
计算几何(2)
(rss)
枚举(4)
(rss)
数据结构(6)
(rss)
数论(5)
(rss)
搜索(2)
(rss)
贪心(4)
(rss)
图论(10)
(rss)
学习笔记(6)
(rss)
学习总结(19)
(rss)
组合数学(3)
(rss)
Links
Lord Li
Lord zeus
搜索
最新评论
1. re: 双向BFS[未登录]
博主,只用一个队列不就可以解决你第一个问题了吗
--jason
2. re:nvgagkguaioguaiiananfajfofajiosfgoasoajgia[未登录]
cscdcuis
--1
3. re: zoj 3436 逆推 搜
评论内容较长,点击标题查看
--ZH
4. re: zoj 2318 计算几何 spfa判负环
写得好!
--ipqhjjybj
5. re: Poj 1066
@杨书鉴
你写的排序好像不对啊。。。
--小猊