154. Factorial
time limit per test: 0.25 sec.memory limit per test: 4096 KB input: standard input
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 [submit] [forum]
| Author: | Andrew V. Lazarev |
| Resource: | Saratov Subregional School Team Contest, 2002 |
| Date: | Spring, 2002 |
思路：对于一个数n的阶乘n！，要求n！的尾部有多少个0........而如果已知尾部有Q个0，则最小的n为多少.......首先在阶乘n！中只要把每个数都拆分为质因数的积，则只需要
质因数5的个数即可，因为2的个数会比5多很多，所以质因数有多少5，尾部就有多少0........
有：
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)]
注意：当Q为0时要输出1
AC代码：
#include#include #include using namespace std; int fun(int x) { //求x尾部有多少个0 int sum = 0; while(x) { sum += x / 5; x /= 5; } return sum; } int main() { int Q; while(scanf("%d", &Q) != EOF) { if(Q == 0) { printf("1\n"); continue; } int N = Q * 4 / 5 * 5; //依据公式先大致算到4*Q（除5乘5是为了N正好是5的倍数），然后再往后推 while(fun(N) < Q) { N += 5; } if(fun(N) == Q) printf("%d\n", N); else printf("No solution\n"); } return 0; }