SGU[154] Factorial

Description

描述

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 1*2*...*N. For example, 5! = 120, 120 contains one zero on the trail.

你的任务是找一个最小的自然数N，使得十进制下N!末尾包含Q个零。正如你知道的N! = 1 * 2 * ... * N。例如，5! = 120，120的末尾包含1个0。

 

Input

输入

One number Q written in the input (0<=Q<=10^8).

输入包含一个数Q (0 <= Q <= 10^8)。

Output

输出

Write "No solution", if there is no such number N, and N otherwise.

如果不存在这样的N，输出“No solution”，否则输出N。

Sample Input

样例输入

2

Sample Output

样例输出

10

 

Analysis

分析

统计N!末尾0的个数，其实只要看因数2和5个数的最小值，因为只有2 * 5会产生0。然而实际上因数2的个数远大于因数5的个数，所以只要看因数5的个数。

由于题目给出的空间限制只有4096KB，所以不能打表，会MLE。百度题解以后发现可以用二分。

二分的时候统计1到N这N个数中因数5的个数，我们采用这样的方法：ans = N / 5 + N / 5^2 + N / 5^3 + ...

处理这个过程有两种方法，一个是打表，把5的幂次打表出来，还有一种利用类似秦九邵算法的思想，每次ans += N / 5，同时N /= 5。

需要注意的是，当输入0的时候，要输出1，因为0不是自然数。还有二分的上下界应为[1, 2147483647]。

 

Solution

解决方案

#include <iostream>

using namespace std;

const int MAX = 2147483647;

int main()
{
	int N;
	while(cin >> N)
	{
		if(N == 0) { cout << 1 << endl; continue; }
		int l = 1, r = MAX, ans = -1;
		while(l <= r)
		{
			int nMid = (l + r) >> 1;
			int nTmp = nMid, nCnt = 0;
			while(nTmp) { nCnt += nTmp / 5; nTmp /= 5; }
			if(nCnt == N) { ans = nMid; r = nMid - 1; }
			else if(nCnt < N) { l = nMid + 1; }
			else { r = nMid - 1; }
		}
		if(ans == -1) { cout << "No solution" << endl; }
		else { cout << ans << endl; }
	}
	return 0;
}

　　

这道题目一开始WA了好几次，后来发现是二分的上界设置的太小了。