魔法石的诱惑

题目：

传说有一块高阶魔法石，它有一个特征那就是它的重量进行阶乘运算后末尾有几个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) + ···$

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的附近

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');
});