← 返回题目列表

Codeforces · 1731/A

A. 乔伊拿钱

中文机器翻译题面 查看原题

乔伊缺钱。他的朋友钱德勒想借给乔伊一些钱,但不能直接给他,因为乔伊太骄傲了,无法接受。于是,为了欺骗他,钱德勒请乔伊玩一个游戏。

在这个游戏中,钱德勒给了乔伊一个正整数数组 $$$a_1, a_2, \dots, a_n$$$ ($$$n \geq 2$$$) ($$$a_i \ge 1$$$)。

Joey 可以对数组执行任意多次以下操作:

1. 取两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i < j \le n)$$$。
2. 选择两个整数 $$$x$$$ 和 $$$y$$$ ($$$x, y \ge 1$$$),使得 $$$x \cdot y = a_i \cdot a_j$$$。
3. 将 $$$a_i$$$ 替换为 $$$x$$$,将 $$$a_j$$$ 替换为 $$$y$$$。

最终,Joey 将获得等于最终数组元素之和的钱。

找出 Joey 可以获得的最大金额 $$$\mathrm{ans}$$$,但打印 $$$2022 \cdot \mathrm{ans}$$$。为什么要乘以$$$2022$$$?因为我们再也见不到它了!

保证数组$$$a$$$所有元素的乘积不超过$$$10^{12}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 4000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 50$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — 数组本身。

保证所有 $$$a_i$$$ 的乘积不超过 $$$10^{12}$$$ (即 $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n \le 10^{12}$$$)。

输出

对于每个测试用例,打印 Joey 可以获得的最大金额乘以 $$$2022$$$。

示例

输入 #1

3
3
2 3 2
2
1 3
3
1000000 1000000 1

输出 #1

28308
8088
2022000000004044

注意

在第一个测试用例中,Joey 可以执行以下操作:

1. 他选择 $$$i = 1$$$ 和 $$$j = 2$$$ (因此他有 $$$a[i] \cdot a[j] = 6$$$),选择 $$$x = 6$$$ 和 $$$y = 1$$$ 并使得 $$$a[i] = 6$$$ 和 $$$a[j] = 1$$$。 $$$$$$[2, 3, 2] \xrightarrow[x = 6,\; y = 1]{i = 1,\; j = 2} [6, 1, 2]$$$$$$
2. 他选择 $$$i = 1$$$ 和 $$$j = 3$$$ (因此他有 $$$a[i] \cdot a[j] = 12$$$),选择 $$$x = 12$$$ 和 $$$y = 1$$$ 并使得 $$$a[i] = 12$$$ 和 $$$a[j] = 1$$$。 $$$$$$[6, 1, 2] \xrightarrow[x = 12,\; y = 1]{i = 1,\; j = 3} [12, 1, 1]$$$$$$