计算具有质因数分解的子序列的最大乘积

TypeScript Hard math

任务 «计算具有质因数分解的子序列的最大乘积»

给定一个整数序列 a1, a2, ..., an。需要找出长度为 k 的子序列（不一定是连续的）的最大乘积，其中 k 是给定的。允许将元素分解为其质因数，但每个元素最多只能分解一次。也就是说，对于每个元素，要么直接取用整个元素，要么将其替换为它的一个质因数（如果该元素不是质数），然后才用于乘积。如果元素是质数，则只能整体取用或不取。要求输出最大可能的乘积对 10^9+7 取模的结果。

输入格式

第一行包含两个整数 n 和 k（1 ≤ k ≤ n ≤ 1000）。第二行包含 n 个整数 a_i（2 ≤ a_i ≤ 10^9）。

输出格式

输出一个整数——对 10^9+7 取模后的最大乘积。

main.ts