Posted on 2009-06-16 13:53
Hero 閱讀(99)
評論(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 }