问题2974--Madoka and Homura

2974: Madoka and Homura

时间限制: 5 Sec  内存限制: 128 MB
提交: 231  解决: 19
[状态] [讨论版] [提交] [命题人:]
题目描述
Madoka正在为一道难题而困扰,因此向她的朋友Homura请教,这个问题当然难不倒Homura,那么请问你能解决吗?
问题如下:

一个正整数数列对于正整数 x 被称为好的,当且仅当此数列可以被拆分为若干对,每对中一个数是另一个数的 x 倍。

换一种说法,一个数列 a 的长度 n 是一个偶数,并且这个数列存在一种排列方式,使得满足 1 <= i <= n/2 的每个正整数 i 符合 a2i-1 *x=a2i ,那么我们称数列 a 对于正整数 x 是棒的。

现在有一个数列 a 和一个正整数 x。请你帮助他让这个数列 a 对于 x 变成好的:将若干个正整数加入数列中。请问最少要加入几个正整数?

输入
每个测试包含多个测试用例。第一行包含一个整数 t (1 <= t <= 20000) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 n,x (1 <= n <= 2 * 10^5,1<= x<= 10^6)
下一行包含 n个整数 a1, a2, ...., an (1<= ai<= 10^5)
保证总和n在所有测试用例中不超过2 * 10^5
样例输入 Copy
4
4 4
1 16 4 4
6 2
1 2 2 2 4 7
5 3
5 2 3 5 15
9 10
10 10 10 20 1 100 200 2000 3
样例输出 Copy
0
2
3
3
提示
在第一个测试用例中,序列对于数字4来说已经很好了,因为你可以把它分成这样的对:(1, 4),(4, 16). 因此我们可以添加0个数字.
在第二个测试用例中,可以添加数字 1 和 4 到序列中,然后你可以划分所有整数成这样的对:(1,2),(1,2),(2,4),(7,14). 不可能添加小于2个整数。
来源/分类