SGU 154. Factorial

点击打开链接

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

题目大意：

就是给你一个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)]

注意：当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;
}