GitBook

这里写图片描述

要求y=x*k不与x同在同一集合的集合元素最大数 则可考虑把有k倍关系的删除一个 那么因为大数有可能还是其他小的数k倍数 所以优先把较大的数删除

二分查找在这里可用作搜索x的k倍数存不存在 从而使查找的时间复杂度降为O(logn)

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100200],flag[100200];
int main() {
	int n,k;
	while(scanf("%d %d",&n,&k)!=EOF) {
		for(int i=0; i<n; i++)
			scanf("%d",&a[i]);
		sort(a,a+n);
		memset(flag,0,sizeof(flag));
		int res=n;
		for(int i=0; i<n; i++) {
			if(!flag[i]) {
				__int64 t=(__int64)a[i]*k;
				if(a[n-1]<t)
					continue;
				int l=i+1,r=n-1;
				while(l<=r) {
					int mid=(l+r)/2;
					if(a[mid]>t)
						r=mid-1;
					else if(a[mid]<t)
						l=mid+1;
					else {
						flag[mid]=1;
						res--;
						break;
					}
				}
			}
		}
		printf("%d\n",res);
	}
	return 0;
}

题目地址:【CodeForces】[274A]k-Multiple Free Set