首页 > 试题广场 >

小美的游戏

[编程题]小美的游戏
  • 热度指数：1340 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小美有一个长度为 n 的数组，她最多可以进行 k 次操作，每次操作如下：
1. 选择两个整数 i, j(1 \leq i < j \leq n)
2. 选择两个整数 x, y，使得 x \times y = a_i \times a_j
3. 将 a_i 替换为 x，将 a_j 替换为 y

她希望最多进行 k 次操作之后，最后数组中的元素的总和尽可能大。

输入描述:
一行两个整数 n, k，表示数组的长度和操作的次数。
一行 n 个整数 a_1, a_2, \cdots, a_n，表示数组的元素。
1 \leq k < n \leq 10^5
1 \leq a_i \leq 10^5


输出描述:
输出一个整数，表示最后数组中的元素的总和的最大值，由于答案可能很大，你只需要输出答案对 10^9 + 7 取模的结果。
示例1

输入

5 2
1 2 3 4 5

输出

65

说明

第一次操作后，数组变为 [1, 2, 12, 1, 5]
第二次操作，数组变为 [1, 2, 60, 1, 1]
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

来自：2023年美团秋招编程...
难度：
0条回答 1736浏览

热门推荐

相关试题

小美的游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号