算法笔记之高精度计算-计算乘法结果前后缀

本体的思路不难,主要是学习一些高精度计算的技巧。

题目描述

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

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

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

  1. 统计乘积中 后缀 0 的数目,并 移除 这些 0 ,将这个数目记为 C 。
    比方说,1000 中有 3 个后缀 0 ,546 中没有后缀 0 。
  2. 将乘积中剩余数字的位数记为 d 。如果 d > 10 ,那么将乘积表示为 <pre>...<suf> 的形式,其中 <pre> 表示乘积最 开始 的 5 个数位,<suf> 表示删除后缀 0 之后 结尾的 5 个数位。如果 d <= 10 ,我们不对它做修改。
    比方说,我们将 1234567654321 表示为 12345...54321 ,但是 1234567 仍然表示为 1234567 。
  3. 最后,将乘积表示为 字符串 "<pre>...<suf>eC" 。
    比方说,12345678987600000 被表示为 "12345...89876e5" 。
    请你返回一个字符串,表示 闭区间 [left, right] 中所有整数 乘积 的 缩写 。

解题思路

将原问题拆分成如下四个问题:

  • 计算前5位pre;
  • 计算后5位suf;
  • 计算结尾0的个数C;
  • 判断剩余数字的长度是否超过 10。

计算pre

可以通过log运算将乘法转换为加法,最后再转换回来,注意为了保证精度,需要使用BigDecimal进行运算。

计算suf

我们可以将每个数字的所有因子 2 和 5 去掉,然后将剩下的数字相乘,由于我们只取末 5 位,所以在乘法的过程中需要对 100000 取模。

由于可能会多去掉一些 2 或 5,在遍历 [left,right] 结束后还需要再重新乘上多去掉的 2 或 5。

计算C

由于 10=2⋅5,我们可以将所有整数分解质因子,那么分解出来的 2 的幂次之和,以及 5 的幂次之和,这两者的较小值就是最后乘积中能分解出来的 10 的个数。

判断长度是否超过10

结合计算C,去除尾部的0后,如果大于10000000000,则长度会超过10。

Java代码

import java.math.*;

class Solution {
    public String abbreviateProduct(int left, int right) {
        boolean flag = true; // 长度是否超过10位
        long suf = 1L;
        int c2 = 0;
        int c5 = 0;
        for(int i = left; i <= right; i++) {
            suf *= i;
            while(suf % 2 == 0) {
                c2++;
                suf /= 2;
            }

            while(suf % 5 == 0) {
                c5++;
                suf /= 5;
            }

            if(suf > 10_000_000_000L) {
                flag = false;
                suf %= 10_000_000_000L;
            }
        }

        int zero = Math.min(c2, c5);
        for(int i = 0; i < c2 - zero; i++) {
            suf *= 2;
            if(suf > 10_000_000_000L) {
                flag = false;
                suf %= 10_000_000_000L;
            }
        }

        for(int i = 0; i < c5 - zero; i++) {
            suf *= 5;
            if(suf > 10_000_000_000L) {
                flag = false;
                suf %= 10_000_000_000L;
            }
        }

        if(flag) {
            return String.valueOf(suf) + "e" + String.valueOf(zero);
        }


        // log运算,计算前5位,使用BigDecimal
        BigDecimal logSum = new BigDecimal(0.0d);
        for (int i = left; i <= right; i++) {
            logSum = logSum.add(new BigDecimal(Math.log10(i)));
        }
        // 减去末尾0的数量(10^zero)
        logSum = logSum.subtract(new BigDecimal(zero));
        // 取小数部分,计算前5位
        double decimal = logSum.remainder(BigDecimal.ONE).doubleValue();
        long pref = (long) (Math.pow(10, decimal) * 10000);
        

        String s1 = String.valueOf(pref);
        String s2 = String.format("%05d", suf % 100000);
        return s1 + "..." + s2 + "e" + String.valueOf(zero);
    }
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容