这题与已经离我们而去的TJU上的一个题很像，那是要求N!末尾有多少个0，答案就是\frac{N}{5}+\frac{N}{5^2}+\frac{N}{5^3}+\dots 。如果把N!拆成质因数相乘，只有2*5才会出现0，而2的个数远多于5，所以只要统计N以下的数中质因数5的总数就可以了。
　　而这个题目，就变成了解\frac{N}{5}+\frac{N}{5^2}+\frac{N}{5^3}+\dots=Q。
　　解法1：二分枚举N。N不会超过5*10^8，虽然比较大，但仍然可以接受。另外，N肯定是5的倍数，这就不用解释了。
　　解法2：已知5^{k_1}! 末尾有q_1个0，5^{k_2}! 末尾有q_2个0，证明(5^{k_{1}}+5^{k_{2}})! 的末尾有q_1+q_2个0。
　　[\frac{{5^{k_{1}}+5^{k_{1}}}}{5}] +[\frac{{5^{k_{1}}+5^{k_{1}}}}{25}]+\dots =[\frac{5^{k_{1}}}{5}] +[\frac{5^{k_{1}}}{25}]+\dots+[\frac{5^{k_{2}}}{5}] +[\frac{5^{k_{2}}}{25}]+\dots=q_1+q_2，得证。
　　设k_1 \ge k_2 \ge k_3 \ge k_4 \ge \dots \ge k_p，且不存在k_i=k_{i+1}=k_{i+2}=k_{i+3}=k_{i+4}，将N写成5^{k_{1}}+5^{k_{2}}+5^{k_{3}}+\dots的形式，则N!末尾0的个数为\frac{5^{k_{1}}-1}{4}+\frac{5^{k_{2}}-1}{4}+\frac{5^{k_{2}}-1}{4}+\dots。
　　可以逐个将k解出。之所以要求不能有5个一样的k，是因为如果有5个一样的k，就不能套用上面的那个等式了（去掉[]再加上[]的时候会出现不等）。如果某个Q导致出现了5个一样的k，那就是无解的。
　　Submit 1: WA on 3。不知道怎么错的，看不出来。晕……题目认为当Q=0时N=1而不是N=0。
　　Submit 2: WA on 1。特殊判断写错地方了……
　　Submit 3: AC。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

//AC
#include <iostream>
using namespace std;
 
const long power5[13]={1,5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625};
 
int main()
{
    long n(0),q,c(1),k(12);
    bool same;
    cin>>q;
    if (q==0)
    {
        cout<<1; return 0;
    }
    while (q)
    {
        same=true;
        for (;(power5[k]-1)/4>q;--k,same=false);
        if (same) ++c;
        else c=1;
        if (c>4) break;
        n+=power5[k]; q-=(power5[k]-1)/4;
    }
    if (c>4) cout<<"No solution";
    else cout<<n;
    return 0;
}