【CodeForces】275C - k-Multiple Free Set（STL）

点击打开题目

C. k-Multiple Free Set

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A k-multiple free set is a set of integers where there is no pair of integers where one is equal to another integer multiplied by k. That is, there are no two integers x and y (x < y) from the set, such that y = x·k.

You're given a set of n distinct positive integers. Your task is to find the size of it's largest k-multiple free subset.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 109). The next line contains a list of n distinct positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

All the numbers in the lines are separated by single spaces.

Output

On the only line of the output print the size of the largest k-multiple free subset of {a1, a2, ..., an}.

Examples

input

6 2
2 3 6 5 4 10

output

3

Note

In the sample input one of the possible maximum 2-multiple free subsets is {4, 5, 6}.

依次往后查 num [ i ] 的 m 次方，最后留下来的数的个数为 ( ant + 1 ) >> 1 ，用一个数组记录一下就行了。

这里要注意两点：

①That is, there are no two integers x and y (x < y) from the set, such that y = x·k.这是题目的要求，也就是说如果 k = 1 的时候，数组里的数并不冲突，输出数组长度 n 。

②我这个代码得用VC++提交，用GUNC++就输出奇怪的数字，样例都过不去，不明白为啥。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
	__int64 n,k;
	__int64 num[100000+11];
	bool used[100000+11];
	int ans;
	while (~scanf ("%I64d %I64d",&n,&k))
	{
		ans = 0;
		memset (used,false,sizeof (used));
		for (int i = 0 ; i < n ; i++)
			scanf ("%I64d",&num[i]);
		if (k == 1)		//注意这个特判，坑啊 
		{
			printf ("%I64d\n",n);
			continue;
		}
		sort (num , num + n);
		num[n] = -1;
		for (int i = 0 ; i < n ; i++)
		{
			if (used[i])
				continue;
			int ant = 1;
			__int64 t = num[i] * k;
			while (1)
			{
				int pos = lower_bound(num , num + n , t) - num;
				if (num[pos] == t)
				{
					used[pos] = true;
					t *= k;
					ant++;
				}
				else
				{
					ans += (ant + 1) >> 1;
					break;
				}
			}
		}
		printf ("%I64d\n",ans);
	}
	return 0;
}