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

Li Dao

献上两种方法
方法一:复杂度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

以此类推

Fifnmar

第二个方法qio棒!

10175101226

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);
}
}

13627999316

既然是大整数,当然用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
Fifnmar

这里数阶乘 $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)$,写一个递推效率就很高啦。

Saitama
#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int N;
    cin >> N;
    int ans = 0;
    for(int i = N; i >= 5; i--)
    {
        int t = i;
        while(t % 5 == 0)
        {
            ans++;
            t /= 5;
        }
    }
    cout << ans << endl;
}

int main()
{
    int T;
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        printf("case #%d:\n", i);
        solve();
    }
    return 0;
}
10195101455

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

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;
}

你当前正在回复 博客/题目
存在问题!