算法与程序--游戏与玩乐
一个新程序员在计算技术上的学习经验
C++博客
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
随笔:142 文章:0 评论:37 引用:0
pku-2478
欧拉函数的应用
#include
<
stdio.h
>
#include
<
math.h
>
const
int
MAX
=
1000001
;
int
prime[MAX
/
5
];
int
len
=
0
;
__int64 dp[MAX];
int
check (
int
n )
/**/
/*
得到最小质因数
*/
{
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
;
}
发表于 2008-06-08 15:25
ghbxx
阅读(263)
评论(1)
编辑
收藏
引用
评论
#
re: pku-2478
看了你的代码,思维还不错,但是二分查找那里实在没有必要,只要把循环那里
改成 for ( i=0; i<len&&prime[i]<=m; i++ )
{
if ( n % prime[i] == 0 )
{
return prime[i];
}
}
prime[len++] = n;
这样就可以了,把循环的终止条件变成i<len&&prime[i]<=m,这样我觉得效率会稍微高一点点.
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
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
公告
决定从线程开始!!
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(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)
搜索
最新评论
1. re: pku-1811
楼主啊,稍微改一下你的代码咋就错了。不用miller labin直接用费马定理原来的写不是错就超时啊
--re
2. re: pku-1811
hugeint product_mod(hugeint A, hugeint B, hugeint C)
这个函数中, D = (D + D) % C; 应该错了吧。
--re
3. re: pku-1338
牛逼
--CAT
4. re: pku-3159
好复杂啊。。。
--搜咯翻车鱼
5. re: pku-1001(1)
大数模板啊 要是能支持小数就好了 O(∩_∩)O~
--abilitytao
阅读排行榜
1. RFC-1321MD5算法(1487)
2. SCOKS4协议及其改进(1463)
3. RFC1929-SCOKS V5的用户名/密码认证方式(1460)
4. RFC977-网络新闻组协议文档(1433)
5. RFC1928-SCOKS V5协议(1318)
评论排行榜
1. pku-1338(4)
2. 大家好,这是一个程序和算法荟萃的地方(4)
3. pku-1811(3)
4. pku-1723(3)
5. pku-2002(3)