CodeVS/1553 2015年2月3日 (二) 18:43云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
互斥的数	★☆☆☆☆	答案正确	100	2015-2-3 18:41:18	无

题意

给n个数，删除最少的数，剩下的不存在a,b使得a=P*b；

题解

• 先排个序（直接扔到set里），如果找到一串a,P*a,P*P*a...，*a，就去掉n/2个数。

代码

1553.cpp代码已折叠 展开折叠内容

#include<iostream> #include<set> #include<cstdio> #define foreach(i,a) for(typeof((a).begin()) i=(a).begin();i!=(a).end();++i) using namespace std; set<int> s; int n,P,ans; int main() { scanf("%d%d",&n,&P); for(int i=1,a;i<=n;++i) { scanf("%d",&a); s.insert(a); } ans=s.size(); foreach(i,s) { int count=1; while(s.count(P*(*i))) { s.erase(P*(*i)); ++count; } ans-=count/2; } printf("%d",ans); return 0; }