6600: 【优先队列】美团2023秋招-小美的游戏
金币值:
1
时间限制:10.000 s
内存限制:128 M
正确:25
提交:50
正确率:50.00% 命题人:
题目描述
小美有一个长度为n的数组,她最多可以进行k次操作,每次操作如下:
1. 选择两个整数i, j,1 <= i < j <= n
2. 选择两个整数x, y,使得xy = aiaj
3. 将ai替换为x,将aj替换为y
她希望最多进行k次操作之后,最后数组中的元素的总和尽可能大。
输入格式
一行两个整数n, k,表示数组的长度和操作的次数。
一行n个整数 a1,a2,...,an,表示数组的元素。
1 <= k < n <= 10^5
1 <= ai <= 10^5
输出格式
输出一个整数,表示最后数组中的元素的总和的最大值,由于答案可能很大,你只需要输出答案对10^9+7取模的结果。
输入样例 复制
5 2
1 2 3 4 5
输出样例 复制
65
提示
第一次操作后,数组变为 [1, 2, 12, 1, 5]
第二次操作,数组变为 [1, 2, 60, 1, 1]