圆度 - 题目详情

远端评测题

1000ms

1024MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

我们把一个数的 $6$ -roundness 值定义为它在 $6$ 进制下末尾 $0$ 的个数。

给你一个长度为 $n$ 的数列，要求你从中选出 $k$ 个数，使得这些选出的数的积的 $6$ -roundness 值最大。

第一行包括两个正整数 $n$ 和 $k$ 。

第二行包括 $n$ 个空白分隔的数 $a_1, a_2, \dots, a_n$ 。

输出一个整数，是选择 $k$ 个数并作积的最大 $6$ -roundness 值。

3 2
18 4 12

5 3
9 16 3 9 9

3 3
9 77 13

在第一个例子中，有三种选法。

$\{18, 4\}$ 的积是 $(200)_6$ ， $6$ -roundness 值是 $2$ ；

$\{4, 12\}$ 的积是 $(120)_6$ ， $6$ -roundness 值是 $1$ ；

$\{18, 12\}$ 的积是 $(1000)_6$ ， $6$ -roundness 值是 $3$ 。

第二个例子中选法 $\{9, 16, 9\}$ 的积是 $(10000)_6$ ， $6$ -roundness 值是 $4$ 。

第三个例子中所有的选法的积的 $6$ -roundness 值都是 $0$ 。

测试点编号	$n$	$k$	$a_i$
$1 \sim 2$	$\leq 200$	$\leq 100$	一定可以被表示为 $6$ 的幂次
$3$	^		在 $\{2, 3, 6\}$ 中取值
$4$	$= 10$	$= 5$	任意 $k$ 个 $a_i$ 之积不超过 $10^{18}$
$5$	$= 25$	$= 12$	只含有质因子 $2$ 或质因子 $3$
$6$	^		只含有质因子 $2$ 和质因子 $3$
$7$	^		无限制
$8$	$\leq 200$	$\leq 100$	^
$9$	^
$10$	^

对于 $100\%$ 的数据， $1 \leq n \leq 200$ ， $1 \leq k \leq 100$ ， $2 \leq a_i \leq 10^9$ 。