6600: 【优先队列】美团2023秋招-小美的游戏

金币值:1 时间限制:10.000 s 内存限制:128 M
正确:25 提交:50 正确率:50.00% 命题人:
点赞量:0 收藏量:0 题目类型:程序 知识点: 数学 优先队列 美团

题目描述

小美有一个长度为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]