本体的思路不难,主要是学习一些高精度计算的技巧。
题目描述
给你两个正整数 left 和 right ,满足 left <= right 。请你计算 闭区间 [left, right] 中所有整数的 乘积 。
由于乘积可能非常大,你需要将它按照以下步骤 缩写 :
- 统计乘积中 后缀 0 的数目,并 移除 这些 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] 中所有整数 乘积 的 缩写 。
解题思路
将原问题拆分成如下四个问题:
- 计算前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);
}
}