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
久久精品卫校国产小美女
|
国产成人无码精品久久久久免费
|
亚洲国产精品无码久久久不卡
|
久久综合久久鬼色
|
久久婷婷国产综合精品
|
色综合久久最新中文字幕
|
久久亚洲精品国产精品婷婷
|
久久夜色精品国产噜噜亚洲AV
|
aaa级精品久久久国产片
|
久久九九久精品国产
|
国产综合久久久久
|
色婷婷综合久久久久中文字幕
|
久久无码人妻一区二区三区午夜
|
国产午夜电影久久
|
久久久噜噜噜久久中文福利
|
久久夜色撩人精品国产
|
香蕉久久一区二区不卡无毒影院
|
久久中文字幕人妻丝袜
|
久久99精品免费一区二区
|
久久久久久午夜成人影院
|
中文字幕无码免费久久
|
久久精品亚洲乱码伦伦中文
|
国产∨亚洲V天堂无码久久久
|
少妇无套内谢久久久久
|
久久久久噜噜噜亚洲熟女综合
|
2021少妇久久久久久久久久
|
国产成人精品久久
|
三级韩国一区久久二区综合
|
久久93精品国产91久久综合
|
国产精品久久久久久
|
久久精品www人人爽人人
|
中文字幕久久波多野结衣av
|
性欧美大战久久久久久久
|
国产精品99久久久久久宅男
|
久久青青草原综合伊人
|
国产亚洲欧美精品久久久
|
久久精品无码午夜福利理论片
|
中文字幕日本人妻久久久免费
|
精品无码久久久久久久久久
|
精品视频久久久久
|
久久国产精品无
|