Yuan
|
首頁
|
發(fā)新隨筆
|
發(fā)新文章
|
聯(lián)系
|
聚合
|
管理
noi 2010 能量采集 八中2005 ★★★ 公約數(shù)確定的對數(shù)
/**/
/*
題意:原題可轉(zhuǎn)化為求在n*m范圍內(nèi)
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))
對于上式,重點(diǎn)是求出 t=gcd(x,y) 時的(x,y)對數(shù)
可以枚舉gcd
記錄cnt[i] = (n/i)*(m/i) 即公約數(shù)是i的倍數(shù)(k*i)的對數(shù)
然后再調(diào)整cnt[i],使其表示公約數(shù)是i的對數(shù)
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
;
}
發(fā)表于 2010-09-07 23:59
_Yuan
閱讀(587)
評論(2)
編輯
收藏
引用
所屬分類:
OJ解題報告
評論
#
re: noi 2010 能量采集 八中2005 ★★★ 公約數(shù)確定的對數(shù)
贊一個~代碼好短
LitIce
評論于 2010-11-15 14:57
回復(fù)
更多評論
#
re: noi 2010 能量采集 八中2005 ★★★ 公約數(shù)確定的對數(shù)
@LitIce
那個是看別人寫的 #_#
_Yuan
評論于 2010-11-15 15:49
回復(fù)
更多評論
刷新評論列表
只有注冊用戶
登錄
后才能發(fā)表評論。
【推薦】100%開源!大型工業(yè)跨平臺軟件C++源碼提供,建模,組態(tài)!
相關(guān)文章:
SRM 239 HiddenTriangles ★★★★
CodeForces 59E 以邊為狀態(tài)bfs ★★★★
TCO'10 Wildcard Round 500pt CalculationCards
zoj 3462 bitset
SRM 496 PalindromfulString 容斥寫法 ★★★★
CodeForces 57D
CodeForces 55D 數(shù)位統(tǒng)計 記憶化搜索 跟pre有關(guān) ★★★★
CodeForces 55E Very simple problem
zoj 3455 統(tǒng)計出現(xiàn)次數(shù) 判斷相等 用l[i]記錄字母出現(xiàn)i次的個數(shù) ★★★★
zoj 3354 映射 環(huán) 計數(shù) ★★★
網(wǎng)站導(dǎo)航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
常用鏈接
我的隨筆
我的評論
我參與的隨筆
隨筆分類
Dp(27)
(rss)
OJ解題報告(153)
(rss)
OThers(17)
(rss)
TopCoder
(rss)
計算幾何(2)
(rss)
枚舉(4)
(rss)
數(shù)據(jù)結(jié)構(gòu)(6)
(rss)
數(shù)論(5)
(rss)
搜索(2)
(rss)
貪心(4)
(rss)
圖論(10)
(rss)
學(xué)習(xí)筆記(6)
(rss)
學(xué)習(xí)總結(jié)(19)
(rss)
組合數(shù)學(xué)(3)
(rss)
Links
Lord Li
Lord zeus
搜索
最新評論
1.?re: 雙向BFS[未登錄]
博主,只用一個隊列不就可以解決你第一個問題了嗎
--jason
2.?re:nvgagkguaioguaiiananfajfofajiosfgoasoajgia[未登錄]
cscdcuis
--1
3.?re: zoj 3436 逆推 搜
評論內(nèi)容較長,點(diǎn)擊標(biāo)題查看
--ZH
4.?re: zoj 2318 計算幾何 spfa判負(fù)環(huán)
寫得好!
--ipqhjjybj
5.?re: Poj 1066
@楊書鑒
你寫的排序好像不對啊。。。
--小猊
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 _Yuan
久久精品亚洲一区二区三区浴池
|
国产午夜精品久久久久九九电影
|
国产aⅴ激情无码久久
|
国内精品九九久久精品
|
99久久这里只有精品
|
亚洲综合久久夜AV
|
国产麻豆精品久久一二三
|
久久久久亚洲av成人无码电影
|
久久婷婷五月综合色奶水99啪
|
久久精品国产亚洲网站
|
国内精品久久久久久久久电影网
|
青青青青久久精品国产
|
亚洲国产一成人久久精品
|
中文成人无码精品久久久不卡
|
久久精品国产亚洲AV香蕉
|
久久99精品国产99久久6
|
久久精品亚洲一区二区三区浴池
|
久久久久国产
|
精品多毛少妇人妻AV免费久久
|
无码人妻久久久一区二区三区
|
亚洲AV伊人久久青青草原
|
久久91这里精品国产2020
|
久久er热视频在这里精品
|
无码人妻久久久一区二区三区
|
久久免费看黄a级毛片
|
欧美亚洲日本久久精品
|
久久九九久精品国产免费直播
|
国产高清美女一级a毛片久久w
|
精品免费tv久久久久久久
|
国产成人久久精品区一区二区
|
日韩人妻无码精品久久免费一
|
一本久久精品一区二区
|
人妻少妇精品久久
|
久久亚洲国产成人影院网站
|
99热精品久久只有精品
|
91久久精品国产免费直播
|
精品久久久久中文字
|
精品久久久无码中文字幕天天
|
久久国产三级无码一区二区
|
久久久受www免费人成
|
久久久久亚洲爆乳少妇无
|