【蓝桥备赛】求阶乘-Toy模板网

这篇具有很好参考价值的文章主要介绍了【蓝桥备赛】求阶乘。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接

求阶乘

个人想法

之前做过计算阶乘结果后面有几个0的题目，这里看到本题之后，很快就有思路了。想要得到阶乘结果有几个0，首先尾数后面的0，最小肯定是因为因子中存在10。然后，10如何得来呢？ 2 * 5 = 10。
在计算阶乘的过程中，以 1~5为例，有三个因子2（2、4），一个因子5，所以在阶乘过程中，2的个数肯定是远大于5的。
如此，我们这题主要就是计算参与阶乘的所有数中有几个5。
对于给定的 k ，我们可以通过从 5 开始挨个累加，但是如果遇上非常大的数，耗时可能会比较长。所以我们此处使用二分查找，查找可能满足题目输入K的答案。
但是为什么会出现不满足的情况呢？此处使用我列举的一堆草稿…
比如我要找到一个阶乘结果后缀有5个0的时候，是无法找到对应的数的。因为正常情况每遇到一个5的倍数，就会增加一个因子5，但是像25这种数，就包含2个因子5，当乘以25时，后缀一下子多了2个0。
【蓝桥备赛】求阶乘,# 蓝桥,java,开发语言,蓝桥杯,算法文章来源地址https://www.toymoban.com/news/detail-810792.html

参考代码

Java

import java.util.Scanner;

public class Main {
    static long k;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextLong();
        long l = 1L, r = (long) 1e19;
        while (l <= r) {
            long mid = (r - l) / 2 + l;
            if (check(mid) >= k) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (check(l) == k) System.out.println(l);
        else System.out.println(-1);
    }

    static long check(long n) {
        long cnt = 0;
        while (n > 0) {
            cnt += n / 5;
            n /= 5;
        }
        return cnt;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll k;

ll check(ll n)
{
    ll cnt = 0;
    while (n)
    {
        cnt += n / 5;
        n /= 5;
    }
    return cnt;
}

int main()
{
    cin >> k;
    ll l = 1, r = 5L * k;
    while (l <= r)  
    {
        ll mid = l + (r - l) / 2;
        if (check(mid) >= k)
            r = mid - 1;
        else
            l = mid + 1;
    }
    if(check(l) == k) cout << l;
    else cout << -1;
    return 0;
}