3017. 计算n!右端0的个数(I)

Fifnmar

我之前的想法是,只有到 5 的时候才多一个零。不过经同学指正是不对的。感谢!

这里数阶乘 $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, 25]$ 的所有对应答案,只需要打一张表。下面是按上述思路结论直接写出的代码:

#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)
    }
}
星子

居然是最右端的零的个数,不是等号右端零的个数QAQ

YZAZJL

include

include

using namespace std;

int main()
{
int n;
cin >> n;
int i;
for(i = 0; i < n; i++){
int num;
int cnt;
cin >> num;
if(num >= 1 && num < 5){
cnt = 0;
}
if(num >= 5 && num < 10){
cnt = 1;
}
if(num >= 10 && num < 15){
cnt = 2;
}
if(num >= 15 && num < 20){
cnt = 3;
}
if(num == 20){
cnt = 4;
}
cout << “case #” << i << “:” << endl;
cout << cnt << endl;
}
return 0;
}

ALICE

include

include

void FactorialZeros(int n){
int b;
b=n/5;
printf(“%d\n”,b);
}
int main()
{
int N,n;
scanf(“%d”,&N);
int i;
int a[N];
for(i=0;i<N;i++){
scanf(“%d”,&a[i]);}
for(i=0;i<N;i++){
printf(“case #%d:\n”,i);
FactorialZeros(a[i]);}
}

Fifnmar

归纳可知只有到5 的时候才会多一个零。

#include <cstdio>

inline unsigned get_uint() {
    unsigned ans = 0;
    char ch = getchar();
    while (ch < '0' || '9' < ch)
        ch = getchar();
    while ('0' <= ch && ch <= '9') {
        ans = ans * 10 + ch - '0';
        ch = getchar();
    }
    return ans;
}

int main() {
    unsigned n = get_uint();
    for (int i = 0; i < n; ++i)
        printf("case #%i:\n%i\n", i, get_uint() / 5);
}
你当前正在回复 博客/题目
存在问题!