算法與程序--游戲與玩樂
一個(gè)新程序員在計(jì)算技術(shù)上的學(xué)習(xí)經(jīng)驗(yàn)
C++博客
|
首頁(yè)
|
發(fā)新隨筆
|
發(fā)新文章
|
聯(lián)系
|
聚合
|
管理
隨筆:142 文章:0 評(píng)論:37 引用:0
pku-2478
歐拉函數(shù)的應(yīng)用
#include
<
stdio.h
>
#include
<
math.h
>
const
int
MAX
=
1000001
;
int
prime[MAX
/
5
];
int
len
=
0
;
__int64 dp[MAX];
int
check (
int
n )
/**/
/*
得到最小質(zhì)因數(shù)
*/
{
if
(
!
( n
&
1
) )
{
return
2
;
}
int
m
=
(
int
)sqrt ( (
double
)n );
int
l, r, mid;
l
=
0
;
r
=
len
-
1
;
while
( l
<=
r )
{
mid
=
( l
+
r )
/
2
;
if
( prime[mid]
>
m )
{
r
=
mid
-
1
;
}
else
{
l
=
mid
+
1
;
}
}
for
(
int
i
=
0
; i
<=
r; i
++
)
{
if
( n
%
prime[i]
==
0
)
{
return
prime[i];
}
}
prime[len
++
]
=
n;
return
n;
}
void
cup ()
{
dp[
1
]
=
1
;
dp[
2
]
=
1
;
dp[
3
]
=
2
;
dp[
4
]
=
2
;
dp[
5
]
=
4
;
prime[
0
]
=
2
;
prime[
1
]
=
3
;
prime[
2
]
=
5
;
len
=
3
;
for
(
int
i
=
6
; i
<
MAX; i
++
)
{
int
min
=
check ( i );
if
( (i
/
min)
%
min )
{
dp[i]
=
dp[i
/
min]
*
(min
-
1
);
}
else
{
dp[i]
=
dp[i
/
min]
*
min;
}
}
for
( i
=
3
; i
<
MAX; i
++
)
{
dp[i]
+=
dp[i
-
1
];
}
}
int
main ()
{
int
n;
cup ();
while
( scanf (
"
%d
"
,
&
n )
!=
EOF
&&
n )
{
printf (
"
%I64d\n
"
, dp[n] );
}
return
0
;
}
發(fā)表于 2008-06-08 15:25
ghbxx
閱讀(270)
評(píng)論(1)
編輯
收藏
引用
評(píng)論
#
re: pku-2478
看了你的代碼,思維還不錯(cuò),但是二分查找那里實(shí)在沒有必要,只要把循環(huán)那里
改成 for ( i=0; i<len&&prime[i]<=m; i++ )
{
if ( n % prime[i] == 0 )
{
return prime[i];
}
}
prime[len++] = n;
這樣就可以了,把循環(huán)的終止條件變成i<len&&prime[i]<=m,這樣我覺得效率會(huì)稍微高一點(diǎn)點(diǎn).
c迷2
評(píng)論于 2008-09-12 19:10
回復(fù)
更多評(píng)論
刷新評(píng)論列表
只有注冊(cè)用戶
登錄
后才能發(fā)表評(píng)論。
【推薦】100%開源!大型工業(yè)跨平臺(tái)軟件C++源碼提供,建模,組態(tài)!
網(wǎng)站導(dǎo)航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
<
2008年6月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
公告
決定從線程開始!!
常用鏈接
我的隨筆
我的評(píng)論
我參與的隨筆
留言簿
(6)
給我留言
查看公開留言
查看私人留言
隨筆檔案
2009年3月 (1)
2008年12月 (1)
2008年9月 (1)
2008年8月 (6)
2008年7月 (11)
2008年6月 (49)
2008年4月 (40)
2008年3月 (33)
搜索
最新評(píng)論
1.?re: pku-1811
樓主啊,稍微改一下你的代碼咋就錯(cuò)了。不用miller labin直接用費(fèi)馬定理原來(lái)的寫不是錯(cuò)就超時(shí)啊
--re
2.?re: pku-1811
hugeint product_mod(hugeint A, hugeint B, hugeint C)
這個(gè)函數(shù)中, D = (D + D) % C; 應(yīng)該錯(cuò)了吧。
--re
3.?re: pku-1338
牛逼
--CAT
4.?re: pku-3159
好復(fù)雜啊。。。
--搜咯翻車魚
5.?re: pku-1001(1)
大數(shù)模板啊 要是能支持小數(shù)就好了 O(∩_∩)O~
--abilitytao
閱讀排行榜
1.?RFC-1321MD5算法(1519)
2.?SCOKS4協(xié)議及其改進(jìn)(1496)
3.?RFC1929-SCOKS V5的用戶名/密碼認(rèn)證方式(1489)
4.?RFC977-網(wǎng)絡(luò)新聞組協(xié)議文檔(1474)
5.?RFC1928-SCOKS V5協(xié)議(1348)
評(píng)論排行榜
1.?大家好,這是一個(gè)程序和算法薈萃的地方(4)
2.?pku-1338(4)
3.?pku-2002(3)
4.?pku-1811(3)
5.?pku-1723(3)
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 ghbxx
国产精品久久久久久久人人看
|
色88久久久久高潮综合影院
|
国产激情久久久久影院
|
久久国产精品99精品国产987
|
色成年激情久久综合
|
久久精品亚洲欧美日韩久久
|
波多野结衣久久一区二区
|
久久精品国产亚洲av水果派
|
久久精品国产亚洲AV不卡
|
综合久久国产九一剧情麻豆
|
国产成人综合久久综合
|
欧美粉嫩小泬久久久久久久
|
亚洲欧美日韩久久精品
|
国产精品久久久久jk制服
|
精品久久久久一区二区三区
|
人妻少妇久久中文字幕一区二区
|
青青青国产精品国产精品久久久久
|
日日狠狠久久偷偷色综合0
|
久久大香香蕉国产
|
久久婷婷五月综合成人D啪
|
久久久久久毛片免费播放
|
性欧美大战久久久久久久久
|
欧美激情精品久久久久
|
国内精品久久久久影院薰衣草
|
国产高清美女一级a毛片久久w
|
精品久久久无码21p发布
|
美女久久久久久
|
狠狠色丁香婷婷综合久久来来去
|
久久综合九色综合网站
|
欧美精品国产综合久久
|
欧美久久一区二区三区
|
美女写真久久影院
|
国产精品99久久久久久人
|
无码日韩人妻精品久久蜜桃
|
模特私拍国产精品久久
|
人妻无码精品久久亚瑟影视
|
久久er国产精品免费观看8
|
久久精品国产亚洲av瑜伽
|
久久精品国产精品亜洲毛片
|
久久99国产精品成人欧美
|
精品久久人人妻人人做精品
|