题目:
传说有一块高阶魔法石,它有一个特征那就是它的重量进行阶乘运算后末尾有几个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){ 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'); });
|