【codevs1553】互斥的数

2014年2月13日1,7920

题目描述 Description

有这样的一个集合,集合中的元素个数由给定的N决定,集合的元素为N个不同的正整数,一旦集合中的两个数x,y满足y = P*x,那么就认为x,y这两个数是互斥的,现在想知道给定的一个集合的最大子集满足两两之间不互斥。

输入描述 Input Description

输入有多组数据,每组第一行给定两个数N和P(1<=N<=10^5, 1<=P<=10^9)。接下来一行包含N个不同正整数ai(1<=ai<=10^9)。

输出描述 Output Description

输出一行表示最大的满足要求的子集的元素个数。

样例输入 Sample Input

4 2

1 2 3 4

样例输出 Sample Output

3

题解

每个数都可以看成是 a*p^b 当俩个数的a相同且b正好相差1,即一个数正好是另一个数的p倍,就会发生冲突

可以考虑一个问题,如果这列数中有 a*p^1,a*p^2…等,最多可以取几个呢。。

略微思考后发现应该从小到大取,比如有1,2,4,p=2

先取1,然后发现2与1冲突,2不取,再取4,像这样

所以得出一个算法,将一个数x不断除以p直到不整除,得到t,放入hash中

如果存在t,检验x是否为该位置的实际数字num[t]的p倍,如果是则舍弃x

不是则ans++,num[t]=x

大概这样。。。