Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

提供一个其他思路

Posted by liheyuan at 2008-07-21 11:18:15 on Problem 1401
没有数论解法那么强悍。。

每次只计算最多含有5,5^2,5^3……的数字个数
每次含有5的[n/5]
........25.[n/25]

注意,当统计最多含有5^2的因子的时候,5的个数应该为[n/25]而不是[n/25]*2因为,在含有[n/5]的时候已经统计过一次了
所以,只需要把[n/5],[n/25]...加起来就可以了

例如1~100中
(1)含有5的:5,10,15....总计100/5=20个,每个之中含有1个5,总5因子数为20
(2)含有25的:25,50,75,100,总计100/25=4个,每个之中含有2个5,但是因为在(1)中含5的数字已经统计过一次因子,所以这里仍然记录因子个数1*5个
。。。。所以1~100中含有5的因子一共100/5+100/25=24个

我们可以知道,1~n中含有5的因子个数绝对比2多,所以构成‘0’就是计算5的因子个数

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator