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}.
Sample Input
Input
6 2
2 3 6 5 4 10
Output
3
Hint
In the sample input one of the possible maximum 2-multiple free subsets is {4, 5,
6}.
题意:给定集合, 就出不存在y = k*x的子集。
贪心:从小到大选过去,如果选到,则他的k *x 不能选,用set标记下来
代码:
#include <stdio.h> #include <string.h> #include <set> #include <algorithm> using namespace std; int n, k, i, j; long long num[100005], ans; set<long long> save; int main() { ans = 0; scanf("%d%d", &n, &k); for (i = 0; i < n; i ++) { scanf("%lld", &num[i]); } sort(num, num + n); for (i = 0; i < n; i ++) { if (save.count(num[i]) == 0) { ans ++; save.insert(num[i] * k); } } printf("%lld\n", ans); return 0; }
查看本栏目更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索set
, 贪心法 最小圈基问题
, 贪心
, where
is
codeforces 贪心、codeforces 766c、codeforces758c、codeforces 94c、codeforces 762c,以便于您获取更多的相关知识。