Yuan
|
首頁
|
發(fā)新隨筆
|
發(fā)新文章
|
聯(lián)系
|
聚合
|
管理
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
;
}
發(fā)表于 2010-09-07 23:59
_Yuan
閱讀(579)
評論(2)
編輯
收藏
引用
所屬分類:
OJ解題報告
評論
#
re: noi 2010 能量采集 八中2005 ★★★ 公約數確定的對數
贊一個~代碼好短
LitIce
評論于 2010-11-15 14:57
回復
更多評論
#
re: noi 2010 能量采集 八中2005 ★★★ 公約數確定的對數
@LitIce
那個是看別人寫的 #_#
_Yuan
評論于 2010-11-15 15:49
回復
更多評論
刷新評論列表
只有注冊用戶
登錄
后才能發(fā)表評論。
【推薦】100%開源!大型工業(yè)跨平臺軟件C++源碼提供,建模,組態(tài)!
相關文章:
SRM 239 HiddenTriangles ★★★★
CodeForces 59E 以邊為狀態(tài)bfs ★★★★
TCO'10 Wildcard Round 500pt CalculationCards
zoj 3462 bitset
SRM 496 PalindromfulString 容斥寫法 ★★★★
CodeForces 57D
CodeForces 55D 數位統(tǒng)計 記憶化搜索 跟pre有關 ★★★★
CodeForces 55E Very simple problem
zoj 3455 統(tǒng)計出現次數 判斷相等 用l[i]記錄字母出現i次的個數 ★★★★
zoj 3354 映射 環(huán) 計數 ★★★
網站導航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
常用鏈接
我的隨筆
我的評論
我參與的隨筆
隨筆分類
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判負環(huán)
寫得好!
--ipqhjjybj
5.?re: Poj 1066
@楊書鑒
你寫的排序好像不對啊。。。
--小猊
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 _Yuan
精品久久久久久无码国产
|
久久伊人五月丁香狠狠色
|
国产精品一久久香蕉产线看
|
2021少妇久久久久久久久久
|
99久久精品免费国产大片
|
久久精品国产精品亚洲
|
97精品伊人久久大香线蕉
|
9久久9久久精品
|
久久久久久无码国产精品中文字幕
|
久久99亚洲网美利坚合众国
|
国产精品久久久久久影院
|
亚洲äv永久无码精品天堂久久
|
51久久夜色精品国产
|
深夜久久AAAAA级毛片免费看
|
久久一日本道色综合久久
|
精品无码久久久久久国产
|
国产午夜免费高清久久影院
|
武侠古典久久婷婷狼人伊人
|
美女写真久久影院
|
久久99精品久久只有精品
|
久久精品亚洲AV久久久无码
|
亚洲嫩草影院久久精品
|
久久精品久久久久观看99水蜜桃
|
91精品无码久久久久久五月天
|
99蜜桃臀久久久欧美精品网站
|
久久天天躁狠狠躁夜夜av浪潮
|
久久综合给合久久国产免费
|
一本色道久久88综合日韩精品
|
日韩中文久久
|
久久精品女人天堂AV麻
|
国产成人精品综合久久久
|
欧美一区二区三区久久综
|
免费久久人人爽人人爽av
|
亚洲国产成人精品女人久久久
|
国产精品成人精品久久久
|
蜜桃麻豆www久久
|
国产高清美女一级a毛片久久w
|
国产午夜久久影院
|
91精品国产91热久久久久福利
|
国产福利电影一区二区三区久久老子无码午夜伦不
|
日本欧美久久久久免费播放网
|