#P1244. 2023.04.20-暑期实习-第三题-元素乘积的因子数量
2023.04.20-暑期实习-第三题-元素乘积的因子数量
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
塔子哥是一位喜欢玩数字游戏的小朋友。有一天,他在网上看到了一个有趣的挑战:
给定一个仅包含 2 和 3 的数组,如何重新排列它,使得所有连续子数组的权值之和尽可能小?数组的权值定义为数组所有元素乘积的因子数量。
例如,数组 [2,3] 的权值为 4 ,因为 2∗3=6 有 4 个因子: 1、2、3、6 。
塔子哥觉得这个挑战很有意思,就决定试试看。他拿出了一些卡片,每张卡片上写着 2 或 3 ,并把它们排成了一个数组。然后,他开始思考如何重新排列这些卡片,使得所有连续子数组的权值之和最小。
他发现,这个问题并不简单,因为不同的排列方式会导致不同的结果。他想请你帮帮他,告诉他应该如何排列这些卡片,以及最小的权值之和是多少。
输入第一行为一个整数 n(1≤n≤1e5) ,表示数组的长度。
输入第二行为一个长度为 n 的数组,第 i 个整数为 ai 。
输出为一个正整数,代表重排后,所有连续子数组权值之和的最小值。
输入
2
2 3
输出
8
样例解释
无论是否重排,该数组的连续子数组权值之和都是 8 :
[2] 的权值为 2 。 [3] 的权值为 2 。 [2,3] 的权值为 4 。
n≤1e9 如何解决?
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.