本文主要是介绍LeetCode 2117. 一个区间内所有数乘积的缩写 数学，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

LeetCode 2117. 一个区间内所有数乘积的缩写

题目描述

给你两个正整数 left 和 right，满足 left <= right。请你计算 闭区间 [left, right] 中所有整数的 乘积。

由于乘积可能非常大，你需要将它按照以下步骤 缩写：

• 统计乘积中 后缀 0 的数目，将这个数目记为 C。
  比方说，1000 中有 3 个后缀 0，546 中没有后缀 0。
• 将乘积中剩余数字的位数记为 d。如果 d > 10，那么将乘积表示为 <pre>...<suf> 的形式，其中 <pre> 表示乘积最 开始 的 5 个数位，<suf> 表示删除后缀 0 之后 结尾的 5 个数位。如果 d <= 10，我们不对它做修改。
  比方说，我们将 1234567654321 表示为 12345...54321，但是 1234567 仍然表示为 1234567。
• 最后，将乘积表示为 字符串 "<pre>...<suf>eC"。
  比方说，12345678987600000 被表示为 "12345...89876e5"。

请你返回一个字符串，表示 闭区间 [left, right] 中所有整数 乘积 的 缩写。

样例

输入：left = 1, right = 4
输出："24e0"
解释：
乘积为 1 × 2 × 3 × 4 = 24 。
由于没有后缀 0，所以 24 保持不变，缩写的结尾为 "e0"。
因为乘积的结果是 2 位数，小于 10，所欲我们不进一步将它缩写。
所以，最终将乘积表示为 "24e0"。


输入：left = 2, right = 11
输出："399168e2"
解释：
乘积为 39916800 。
有 2 个后缀 0，删除后得到 399168。缩写的结尾为 "e2"。
删除后缀 0 后是 6 位数，不需要进一步缩写。
所以，最终将乘积表示为 "399168e2"。

输入：left = 999998, right = 1000000
输出："99999...00002e6"
解释：
上图展示了如何得到乘积的缩写 "99999...00002e6"。
- 总共有 6 个后缀 0。缩写的结尾为 "e6"。
- 开头 5 个数位是 99999。
- 删除后缀 0 后结尾 5 个数字为 00002。


输入：left = 256, right = 65535
输出："23510...78528e16317"
解释：
乘积是一个非常大的数字：
- 总共有 16317 个后缀 0。缩写结尾为 "e16317"。
- 开头 5 个数字为 23510。
- 删除后缀 0 后，结尾 5 个数字为 78528。
所以，乘积的缩写为 "23510...78528e16317"。

限制

• 1 <= left <= right <= 10^6

算法

(数学) \(O(n)\)

本题要求的分为三部分，第一部分求后缀 0 的个数，第二部分求低 5 位，第三部分求高 5 位。

1. 第一部分：一个数末尾0的个数\(min(cnt_5, cnt_2)\)，对于阶乘的质因子个数，有勒让德定理：

   在正数 \(n !\) 的素因子标准分解式中, 素数 \(p\) 的指数记作 \(L_{p}(n !)\) , 则 \(L_{p}(n !)=\sum_{k \geq 1}\left[\frac{n}{p^{k}}\right]\).

   

   即\(right\) 阶乘中因数 \(5\) 的个数减去 \(left - 1\) 阶乘中因数 \(5\) 的个数，与 \(right\) 阶乘中因数 \(2\) 的个数减去 \(left - 1\) 阶乘中因数 \(2\) 的个数取最小值后，就是区间后缀 0 的个数 \(C\)。

2. 第二部分：从 \(left\) 累乘到 \(right\)，过程中，对乘数总共进行 \(C\)次扣除因数 \(2\) 和因数 \(5\)，并对结果进行 \(100000\) 取余。

3. 第三部分:

   • 设 \(P=a_{1} a_{2} a_{3} \ldots a_{n}\) ，则\(\lg P=\lg a_{1}+\lg a_{2}+\lg a_{3}+\cdots+\lg a_{n}\) 。

   • 即\(P\)的位数\(S=\lg P\) ，则 \(P=10^{S}\) 。此时将 \(S\) 分为整数部分\(S_{1}\) 和小数部分 \(S_{2}\) ，则 \(P=10^{S_{1}} \cdot 10^{S_{2}}\) 。\(10^{S_{1}}\)代表后面的0个数，\(P\)真正有效非后缀0的是\(10^{S_{2}}\)。

   • \(P\) 的高五位就是 \(P\) 不断除以 10 直到最终只剩下五位，此时高五位相当于 \(10^{S_{2}+4}= 10^{S - floor(s) + 4}\) 。

4. 求解第三部分过程中，如果发现 \(S_1 < 10 + C\)，则说明 \(d\) 小于等于 10 位，此时可以暴力求解第二部分的结果。

时间复杂度

• 求解第一部分的时间复杂度为 \(O(log n)\)。
• 求解第二部分的时间复杂度为 \(O(n)\)。
• 求解第三部分的时间复杂度也为 \(O(n)\)。
• 故总时间复杂度为 \(O(n)\)。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#define LL long long

class Solution {
private:
    int calc(int x, int p) {
        int res = 0;
        while (x) {
            res += x / p;
            x /= p;
        }

        return res;
    }

    string brute_force(int zero, int left, int right) {
        LL res = 1;
        int cnt2 = zero, cnt5 = zero;
        for (int i = left; i <= right; i++) {
            int x = i;
            while (x % 2 == 0 && cnt2 > 0) {
                x /= 2;
                cnt2--;
            }

            while (x % 5 == 0 && cnt5 > 0) {
                x /= 5;
                cnt5--;
            }

            res *= x;
        }

        char ans[30];
        sprintf(ans, "%llde%d", res, zero);
        return ans;
    }

public:
    string abbreviateProduct(int left, int right) {
        int zero = min(calc(right, 5) - calc(left - 1, 5),
            calc(right, 2) - calc(left - 1, 2));

        int low = 1;
        int cnt2 = zero, cnt5 = zero;
        for (int i = left; i <= right; i++) {
            int x = i;
            while (x % 2 == 0 && cnt2 > 0) {
                x /= 2;
                cnt2--;
            }

            while (x % 5 == 0 && cnt5 > 0) {
                x /= 5;
                cnt5--;
            }

            low = (LL)(low) * x % 100000;
        }

        long double s = 0;
        for (int i = left; i <= right; i++)
            s += log10(i);

        if (s <= 10 + zero)
            return brute_force(zero, left, right);

        int high = pow(10, s - floor(s) + 4);

        char ans[30];
        sprintf(ans, "%d...%05de%d", high, low, zero);
        return ans;
    }
};

这篇关于LeetCode 2117. 一个区间内所有数乘积的缩写 数学的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！