class Solution {
public:
string abbreviateProduct(int left, int right) {
}
};
2117. 一个区间内所有数乘积的缩写
给你两个正整数 left 和 right ，满足 left <= right 。请你计算 闭区间 [left, right] 中所有整数的 乘积 。
由于乘积可能非常大，你需要将它按照以下步骤 缩写 ：
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] 中所有整数 乘积 的 缩写 。
示例 1：
输入：left = 1, right = 4 输出："24e0" 解释： 乘积为 1 × 2 × 3 × 4 = 24 。 由于没有后缀 0 ，所以 24 保持不变，缩写的结尾为 "e0" 。 因为乘积的结果是 2 位数，小于 10 ，所欲我们不进一步将它缩写。 所以，最终将乘积表示为 "24e0" 。
示例 2：
输入：left = 2, right = 11 输出："399168e2" 解释：乘积为 39916800 。 有 2 个后缀 0 ，删除后得到 399168 。缩写的结尾为 "e2" 。 删除后缀 0 后是 6 位数，不需要进一步缩写。 所以，最终将乘积表示为 "399168e2" 。
示例 3：
输入：left = 371, right = 375 输出："7219856259e3" 解释：乘积为 7219856259000 。
提示：
1 <= left <= right <= 104原站题解
golang 解法, 执行用时: 72 ms, 内存消耗: 6.7 MB, 提交时间: 2023-09-04 15:54:41
// 拆分成4个子问题
var lim, _ = new(big.Int).SetString(strings.Repeat("9", 200), 10)
var div, _ = new(big.Int).SetString("1"+strings.Repeat("0", 100), 10)
func abbreviateProduct(left, right int) string {
cnt2, cnt5, suf, mul := 0, 0, 1, 1
update := func(x int) {
suf = suf * x % 1e5
if mul != -1 {
mul *= x
if mul >= 1e10 { // 长度超过 10
mul = -1
}
}
}
pre := big.NewInt(1)
for i := left; i <= right; i++ {
pre.Mul(pre, big.NewInt(int64(i)))
if pre.Cmp(lim) > 0 { // 超过一定位数就截断
pre.Quo(pre, div)
}
x := i
tz := bits.TrailingZeros(uint(x)) // 因子 2 的个数
cnt2 += tz
x >>= tz
for ; x%5 == 0; x /= 5 {
cnt5++ // 因子 5 的个数
}
update(x)
}
cnt10 := min(cnt2, cnt5)
for i := cnt10; i < cnt2; i++ {
update(2) // 补上多拆出来的 2
}
for i := cnt10; i < cnt5; i++ {
update(5) // 补上多拆出来的 5
}
if mul != -1 { // 不需要缩写
return fmt.Sprintf("%de%d", mul, cnt10)
}
return fmt.Sprintf("%s...%05de%d", pre.String()[:5], suf, cnt10)
}
func min(a, b int) int { if a > b { return b }; return a }
golang 解法, 执行用时: 260 ms, 内存消耗: 7.8 MB, 提交时间: 2023-09-04 15:53:12
// 暴力
func abbreviateProduct(left, right int) string {
s := new(big.Int).MulRange(int64(left), int64(right)).String()
tz := len(s)
s = strings.TrimRight(s, "0")
tz -= len(s)
if len(s) > 10 {
return fmt.Sprintf("%s...%se%d", s[:5], s[len(s)-5:], tz)
}
return fmt.Sprintf("%se%d", s, tz)
}