魔法石的诱惑

题目:

传说有一块高阶魔法石,它有一个特征那就是它的重量进行阶乘运算后末尾有几个0
就拥有同等重量普通魔法石几倍的魔法力。例如 5! = 5 x 4 x 3 x 2 x 1 = 120
而120包含一个0,所以拥有同等重量的普通魔法石1颗
你的任务就是要找到最小的自然数N,使得N!在十进制下包含Q个零

输入格式:

一个数 Q (0 <= Q <= 10^8)

输出格式:

如果无解则输出”No solution”,否则输出N

输入例子:

2

输出例子:

10

实现思路

分治算法
数学方法

分治算法

本题中,N!随着N的增加,0的个数也在增加,所以这是一个单调递增序列,用分治二分法很好解决
那么如何判断N!有多少个零呢?参考公式
$N/5 + N/(5^2) + N/(5^3) + ···$

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
process.stdin.setEncoding('utf8');
var Q = 0;
var bool = false;
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk !== null) {
Q = parseInt(chunk)
}
if(bool){
process.stdin.emit('end')
}
bool = true;
});
function solve(mid){
var ans = 0;
while (mid>0) {
ans = ans+parseInt(mid/5);
mid = parseInt(mid/5);
}
return ans
}
process.stdin.on('end', function() {
var start = 1;
var end = 500000000;
var ans = 500000001;
var mid,t
while(start<=end){
mid = parseInt((end-start)/2)+start;
t = solve(mid);
if(t == Q && mid<ans){
ans = mid;
}
if(t>Q){
end = mid-1;
}
else if(t<Q) {
start = mid+1
}
else{
end = mid-1
}
}
if(ans != 500000001){
console.log("N="+ans);
}
else{
console.log("No solution");
}
process.stdout.write('end');
});

数学方法

此题还可以采用数学的方法解决;
题目给的是Q,要求的是N,由于是要求出最小的自然数,所以N必定是5的倍数,所以得出:
$$Q = N/5 + N/(5^2) + N/(5^3) + ··· $$

$$\Rightarrow Q = N/(5^k-1)/[4*(5^k)]$$

$$\Rightarrow N = 4Q*[(5^k)/(5^k-1)]$$
注意到$1<(5^k)/(5^k-1)\le 5/4$,且当k趋于无穷时,$(5^k)/(5^k-1)$趋于1,所以可以先算出
N = 4Q的末尾零的个数与所给的Q比较,显然所求的数就在4Q的附近

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
process.stdin.setEncoding('utf8');
var Q = 0;
var bool = false;
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk !== null) {
Q = parseInt(chunk);
}
if(bool){
process.stdin.emit('end')
}
bool = true;
});
function solve(mid){ //计算n!的0的个数
var ans = 0;
while (mid>0) {
ans = ans+parseInt(mid/5);
mid = parseInt(mid/5);
}
return ans
}
process.stdin.on('end', function() {
if(!Q){
console.log("1");
return;
}
var i = parseInt(4*Q/5*5);
while (solve(i)<Q) {
i += 5;
}
if(Q == solve(i)){
i = i-(i%5)
console.log("N="+i);
}
else{
console.log("No solution");
}
process.stdout.write('end');
});
© 2017 RABBIT All Rights Reserved.
Theme by hiero