要求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
",res);
}
return 0;
}