点击打开链接
154. Factorial
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
memory limit per test: 4096 KB
input: standard input
output: standard output
output: standard output
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.
Input
One number Q written in the input (0<=Q<=10^8).
Output
Write "No solution", if there is no such number N, and N otherwise.
Sample test(s)
Input
2
Output
10
题目大意：
就是给你一个Q，表示有Q个0，然后让你找最小的n！包涵Q个0，输出n，如果没有输出“No solution”
解题思路：
Q = N/5 + N/(5^2) + N/(5^3) + ...
由等比数列求和可得（设只到前k项）：
Q = N(5^k - 1) / [4*(5^k)]，由此得：
N = 4Q * [(5^k)/(5^k-1)]
由等比数列求和可得（设只到前k项）：
Q = N(5^k - 1) / [4*(5^k)]，由此得：
N = 4Q * [(5^k)/(5^k-1)]
注意：当Q为0时要输出1
上代码：
/*
Date : 2015-09-07 晚上
Author : ITAKING
Motto :
今日的我要超越昨日的我，明日的我要胜过今日的我；
以创作出更好的代码为目标，不断地超越自己。
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int get(int m)
{
int sum = 0;
while(m)
{
sum += m/5;
m /= 5;
}
return sum;
}
int main()
{
int Q;
while(~scanf("%d",&Q))
{
if(Q == 0)
cout<<1<<endl;
else
{
int res = 4*Q/5*5;
while(get(res) < Q)
res += 5;
if(get(res) == Q)
cout<<res<<endl;
else
puts("No solution");
}
}
return 0;
}
