3022. 计算n!右端0的个数(II)

献上两种方法
方法一：复杂度O(nlog(n))

include

using namespace std;
int T;

void solve()
{
int n;
cin>>n;
int ret=0;
for(int i=1;i<=n;i++)
{
int tmp=i;
while(tmp%5==0)
{
tmp/=5;
ret++;
}
}
cout<<ret<<endl;
}
int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

方法二：复杂度O(log(n))

include

using namespace std;
int T;

void solve()
{
int n;
cin>>n;
int ret=0;
int m=5;
while(n>=m)
{
ret+=n/m;
m*=5;
}
cout<<ret<<endl;
}
int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

原理：只要找n!这个数能分解为
2^k5^m另一个数

min(k,m) 就是答案

因为可以合成位10^min(k,m)

而k肯定>m，因为2的倍数在n!中很多

只要找5^m*另一个数 这个m

一种方法就是枚举1-n 找每个数中有5的几次方，累加起来

第二种，直接n/5，找1-n中5的倍数有几个
而25这种数，一个数就能贡献两个

因此，第二次n/25，找1-n中25的倍数有几个。
这些数在第一轮已经贡献过一次了，这次只需要每个贡献一个5

再找n/125

以此类推

include

int main()
{
int a,b;
scanf(“%d”,&a);
for(b=0;b<a;b++)
{
printf(“case #%d:\n”,b);
int n;
scanf(“%d”,&n);
printf(“%d\n”,n/5+n/25+n/125+n/625);
}
}

既然是大整数，当然用python做最简单啦！

def jiecheng(v):
    ans = 1;i = v;
    while i >= 1:
        ans = ans*i
        i = i-1
    return ans

n = int(input())
i = 0
while i < n:
    v = int(input());cnt = 0;
    ans = jiecheng(v)
    ans = str(ans);j = len(ans)-1
    while ans[j] == '0':
        cnt = cnt+1
        j=j-1
    print("case #{}:".format(i))
    print(cnt)
    i = i + 1

这里数阶乘 $n!$ 右侧的零，注意到 $n!=a∗10^b$，其中 $a$ 是 $n!$ 去掉右侧 0 的部分。这说明 $n!$ 可以分解出 $n$ 个 10 相乘。又因为只有 2 和 5 两个质数相乘才能得到 10，所以原问题等价于求 $n!$ 可以分解出多少个 2 或 5，取其中较小的为答案（多余的 2 或 5 不能拼出 10）。

因为 $n!$ 质因数分解后，2 出现的次数恒大于等于 5 出现的次数，所以只需要求 $n!$ 质因数分解后有多少个 5，这就是答案。因为阶乘数可能很大，求出它的值不现实，所以我们必须寻找其它方法。幸运的是，我们不需要得到 $n!$ 的值而只需要它所有的因数里 5 的个数。

此外，由于阶乘的特性，如果定义 $f(n)$ 为 $n!$ 右侧零的个数，$g(x)$ 为 $x$ 的质因数中 5 的个数，那么满足
$$
f(n）= \begin{cases}
0 & n < 5 \
f(n−1)+g(n) & n \ge 5
\end{cases}
$$
根据这个式子可以方便地推出从 $n\in[1,1000]$ 的所有对应答案，只需要打一张表。下面是按上述思路结论直接写出的代码：

#include <iostream>

int g(int n) {
    int ret = 0;
    while (n % 5 == 0) {
        n /= 5;
        ++ret;
    }
    return ret;
}

int f(int n) {
    if (n < 5)
        return 0;
    else
        return f(n - 1) + g(n);
}

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; ++i) {
        int n;
        scanf("%d", &n);
        printf("case #%d:\n%d\n", i, f(n));
    }
}

打表也很简单，结果大概是这样：

f(0) = 0        f(1) = 0        f(2) = 0
f(3) = 0        f(4) = 0        f(5) = 1
f(6) = 1        f(7) = 1        f(8) = 1
f(9) = 1        f(10) = 2       f(11) = 2
f(12) = 2       f(13) = 2       f(14) = 3
f(15) = 3       f(16) = 3       f(17) = 3
f(18) = 3       f(19) = 3       f(20) = 4
f(21) = 4       f(22) = 4       f(23) = 4
f(24) = 4       f(25) = 6       f(26) = 6
f(27) = 6       f(28) = 6       f(29) = 7
f(30) = 7       f(31) = 7       f(32) = 7
f(33) = 7       f(34) = 7       f(35) = 8
f(36) = 8       f(37) = 8       f(38) = 8
f(39) = 8       f(40) = 9       f(41) = 9
f(42) = 9       f(43) = 9       f(44) = 10
f(45) = 10      f(46) = 10      f(47) = 10
f(48) = 10      f(49) = 10      f(50) = 12
...

来了兴趣，用 Rust 写一下上面的代码，其实也没有什么花样。

fn g(mut x: u32) -> u32 {
    let mut ret = 0;
    while x % 5 == 0 {
        x /= 5;
        ret += 1;
    }
    ret
}

fn f(n: u32) -> u32 {
    if n < 5 {
        0
    } else {
        f(n - 1) + g(n)
    }
}

至于复杂度的优化，我递归式都给出来了，$O(g(n))=O(\log n)$，写一个递推效率就很高啦。

列几个一找规律在一顿猛操作就好了（脸黑）

include

include

using namespace std;

int main()
{
int T;
cin>>T;
int t;
for(t = 0; t < T; t++)
{
int N;
cin>>N;
int n, cont = 0;
for(n = 1; n <= N; n++)
{
int temp = n;
while(temp%10 == 0)
{
cont++;
temp /= 10;
}
while(temp%5 == 0)
{
cont++;
temp /= 5;
}
}
printf(“case #%d:\n%d\n”, t, cont);
}
return 0;
}