问题 6231 --兔兔的算术

6231: 兔兔的算术★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 50  解决: 19
[提交][状态][命题人:]

题目描述

给定一个n个元素的数组a1,a2,...,an和一个整数k，每次操作可以对数组内的任意一个元数加1。请你帮忙计算一下，至少要进行多少次操作之后，才能使a1*a2*...*an的乘积能被k整除。

输入

第一整数为T,表示有T (1≤T≤10000)组测试样例。
每组测试样例的第1行为整数n和k (2≤n≤1e5,2≤k≤5)，表示数组a的长度和整数k。
第2行为n个整数a1,a2...an (1≤ai≤10)。
测试数据保证所有的n之和不超过2e5。

输出

每组测试数据输出一个整数，表示乘积整除k时最少操作次数。
样例输入
Copy
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
样例输出
Copy
2
2
1
0
2
0
1
2
0
1
1
4
0
4
3

提示

在测试样例1中，需要对a2进行操作2次，操作后的数组a=[7,5]。数组元素的乘积为35，能整除5。
在测试样例4中，数组元素的乘积为120，能整除5。因此不需要操作。
在测试样例8中，需要对a2和a3各操作1次，操作后的数组a=[1,6,10]。数组元素的乘积为60，能整除4。

来源

 

[提交][状态]