Java教程

高精度乘法

本文主要是介绍高精度乘法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

[https://leetcode-cn.com/problems/abbreviating-the-product-of-a-range/](力扣 2117)

\[p = \prod_{i = left}^{right}{i} \]

1.p 末尾 0 的个数 等价于 p 的因数分解中 2 的个数 与 5 的个数,两者较小值
2.p 最高 五位数:

  • 设 k 为 p 的位数, \(k = \lfloor\log_{10}p\rfloor + 1\)
  • 设 x 为 p 的最高五位,\(x = \frac{p}{10^{k - 5}}\)
  • 两边对 10 取对数,\(\log_{10}{x} = \log_{10}{p} - (k - 5) = \log_{10}{p} - \lfloor\log_{10}p\rfloor + 4\)
  • \(log_{10}p = log_{10}left + log_{10}{(left + 1)} + ... log_{10}{right}\)
class Solution {

public:
    string abbreviateProduct(int left, int right) {
        int two = 0, five = 0;
        for (int i = left; i <= right; ++ i) {
            int t = i;
            while (t % 2 == 0) t /= 2, ++ two;
            while (t % 5 == 0) t /= 5, ++ five;
        }
        int cnt = min(two, five);
        two = five = cnt;
        long long back = 1, back2 = 1;
        int f = 0;
        for (int i = left; i <= right; ++ i) {
            int t = i;
            while (two > 0 && t % 2 == 0) t /= 2, -- two;
            while (five > 0 && t % 5 == 0) t /= 5, -- five;
            back = (back * t) % 100000;
            if (!f) {
                back2 = back2 * t;
                if (back2 >= 10000000000LL) f = 1;
            }
        }
        string ret = "";
        if (!f) {
            ret = to_string(back2) + "e" + to_string(cnt);
            
            return ret;
        }
        double e = 0;
        for (int i = left; i <= right; ++ i) e += log10(i);
        long long hight = pow(10, e - (long long) e + 4);
        char buffer[20] = {0};
        snprintf(buffer, 20, "%05lld", back);
        ret = to_string(hight) + "..." + string(buffer) + "e" + to_string(cnt); 

        return ret;
    
    }
};
这篇关于高精度乘法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!