← 返回题目列表

Codeforces · 1883/C

C. 覆盆子

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

给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和一个数字 $$$k$$$ ($$$2 \leq k \leq 5$$$)。在一项操作中,您可以执行以下操作:

- 选择一个索引 $$$1 \leq i \leq n$$$,
- 设置$$$a_i = a_i + 1$$$。

求使数组 $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n$$$ 中所有数字的乘积能被 $$$k$$$ 整除所需的最少运算次数。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq 5$$$) — 数组 $$$a$$$ 的大小和数字 $$$k$$$。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出使数组中所有数字的乘积可被 $$$k$$$ 整除所需的最少操作数。

示例

输入 #1

15
2 5
7 3
3 3
7 4 1
5 2
9 7 7 3 9
5 5
5 4 1 2 3
7 4
9 5 1 5 9 5 1
3 4
6 3 6
3 4
6 1 5
3 4
1 5 9
4 4
1 4 1 1
3 4
3 5 3
4 5
8 9 9 3
2 5
1 6
2 5
10 10
4 5
1 6 1 1
2 5
7 7

输出 #1

2
2
1
0
2
0
1
2
0
1
1
4
0
4
3

注意

在第一个测试用例中,我们需要选择索引 $$$i = 2$$$ 两次。之后,数组将是 $$$a = [7, 5]$$$。数组中所有数字的乘积为 $$$35$$$。

在第四个测试用例中,数组中数字的乘积是$$$120$$$,它已经可以被$$$5$$$整除,因此不需要任何操作。

在第八个测试用例中,我们可以通过以任意顺序选择 $$$i = 2$$$ 和 $$$i = 3$$$ 来执行两个操作。之后,数组将是 $$$a = [1, 6, 10]$$$。数组中数字的乘积是 $$$60$$$。