783
cf 168 k-Multiple Free Set bin_search
一開始寫的是逆序的，WA了，改成正序AC，想來沒有道理，細看後才發現是改了當前值，讓二分序列不再有序……o(╯□╰)o，正序隻能是僥幸罷了
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define INF 1E9
using namespace std;
int q[100010];
int abs(int a){return a>0?a:-a;}
int bin(int l,int r,long long x)
{
int mid;
if(x>abs(q[r]))return -1;
while(l<r)
{
mid=l+((r-l)>>1);
if(abs(q[mid])<x)l=mid+1;
else r=mid;
}
if(q[l]==x)return l;
else return -1;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
int i;
for(i=0;i<n;i++)
scanf("%d",&q[i]);
sort(q,q+n);
int ans=0;
for(i=n-1;i>=0;i--)
{
if(q[i]<0)continue;
ans++;
if(q[i]%k==0)
{
r=bin(0,i-1,q[i]/k);
if(r!=-1) q[r]=-q[r];//一開始這是-1
}
}
printf("%d\n",ans);
}
最後更新：2017-04-04 07:03:51