Posted on 2009-06-16 13:53
Hero 阅读(87)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
1 //SGU 154 .CPP_VS Accepted 0 ms 0 kb
2 /*
3 阶乘末尾0的个数 = n/5 + n/25 + n/125 + n/625 + 
4 题目求阶乘末尾有Q个0的最小正整数
5
6 注意可以有1，2，3，4，6个0的，但是没有5个0的
7 简单的方案是转换成二分验证答案
8
9 注意最后结果最好在进行验证一下
10 */
11 #include <stdio.h>
12
13 int inn ;
14
15 int fNumOfZero( int x )
16 {
17 int cnt = 0 ;
18
19 while( x )
20 {
21 x = x / 5 ;
22 cnt = cnt + x ;
23 }
24
25 return cnt ;
26 }
27
28 int main()
29 {
30 while( scanf( "%d", &inn ) != EOF )
31 {
32 int left = 1; int right = 500000000 ; int mid ;
33
34 while( left < right )
35 {
36 mid = ( left + right ) / 2 ;
37 if( fNumOfZero( mid ) < inn )
38 {
39 left = mid + 1 ;
40 }
41 else if( fNumOfZero( mid ) > inn )
42 {
43 right = mid - 1 ;
44 }
45 else
46 {
47 right = mid ;
48 }
49 }
50
51 //最后再验证下最后的结果
52 if( left == right && (fNumOfZero( right ) == inn) )
53 printf( "%d\n", right ) ;
54 else
55 printf( "No solution\n" ) ;
56 }
57
58 return 0 ;
59 }