CodeForces 275C k-Multiple Free Set（二分）
题目链接：CodeForces 275C k-Multiple Free Set
题目大意：给出n和k，然后给出元素个数为n的集合num，现在要从num集合中挑选出尽量多的元素组成新的集合，新的集合的要求是集合中不存在元素x ， y（x < y）使得x * k = y，输出最大的元素个数。
解题思路：将num数组排序，对应每个数值的num[i] * k进行二分搜索，如果搜索到，cnt--。
这里有两个坑点：
1、因为x < y，所以要考虑k = 1的情况。
2、数据
5 2 1 2 3 4 5，自己去发现问题吧。
#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>using namespace std;const int N = 100005;int n, cnt, vis[N];long long k, num[N];void search(long long c) {int l = -1, r = n;while (l < r) {int mid = (l + r) / 2;if (num[mid] < c) l = mid;else if (num[mid] > c) r = mid;else { if (c / k < num[mid]) {vis[mid] = 1;cnt--; }return; }if (l == r - 1) return;}}int main () {scanf("%d%lld", &n, &k);cnt = n;for (int i = 0; i < n; i++)scanf("%lld", &num[i]);memset(vis, 0, sizeof(vis));sort(num, num + n);if (k != 1)for (int i = 0; i < n; i++) {if (vis[i]) continue;search(num[i] * k);}printf("%d\n", cnt);return 0;}