[二分]codeforces 274A k-Multiple Free Set
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.
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.
On the only line of the output print the size of the largest k-multiple free subset of {a1, a2, ..., an}.
6 2
2 3 6 5 4 10
3
In the sample input one of the possible maximum 2-multiple free subsets is {4, 5, 6}.
题意:给你n个数，找出在这n个数中最多有多少个x使得所选出的数中比x大的数不是x的k倍
注意：先选择所有的数，若x的k倍在原序列存在，则看x的k倍的k倍是否存在，若存在则删去x的k倍，因为这样就可以选x和x的k倍的k倍，若x的k倍的k倍不存在，则删x的k倍
排序后二分查找，k和a[i]最大是1e9，所以要注意k*k*a[i]是否小于1e18，为防止溢出可用if(k*a[i]<=(1e18)/k)
自己的测试数据：
2 1000000000
1000000000 1000000000
4 2
2 3 4 8
5 1
1 2 3 4 5
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int amn=1e5+5; 5 const ll inf=1e18; 6 7 int n,k,mid; 8 ll a[amn]; 9 10 ll fd(ll b){ 11 int l=1,r=n; 12 mid=(l+r)/2; 13 while(l<r){ 14 if(a[mid]<b)l=mid+1; 15 else if(a[mid]>b) r=mid-1; 16 else break; 17 mid=(l+r)/2; 18 } 19 return a[mid]; 20 } 21 22 int main(){ 23 ios::sync_with_stdio(0); 24 cin>>n>>k; 25 for(int i=1;i<=n;i++){ 26 cin>>a[i]; 27 } 28 sort(a+1,a+1+n); 29 int ans=n,pos,jg,jg1; 30 if(k!=1) 31 for(int i=1;i<n;i++){ 32 if(!a[i])continue; 33 jg=fd(k*a[i]); 34 if(k*a[i]==jg){ 35 pos=mid; 36 if(k*a[i]<=inf/k){ 37 jg1=fd(k*k*a[i]); 38 if(k*k*a[i]==jg1){ 39 a[pos]=0; 40 } 41 else a[i]=0; 42 } 43 else a[i]=0; 44 ans--; 45 } 46 } 47 printf("%d\n",ans); 48 }
查看8道真题和解析
