首页 > 代码库 > codevs——1553 互斥的数
codevs——1553 互斥的数
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题解
题目描述 Description
有这样的一个集合，集合中的元素个数由给定的N决定，集合的元素为N个不同的正整数，一旦集合中的两个数x,y满足y = P*x，那么就认为x,y这两个数是互斥的，现在想知道给定的一个集合的最大子集满足两两之间不互斥。
输入描述 Input Description
输入有多组数据，每组第一行给定两个数N和P（1<=N<=10^5, 1<=P<=10^9）。接下来一行包含N个不同正整数ai（1<=ai<=10^9）。
输出描述 Output Description
输出一行表示最大的满足要求的子集的元素个数。
样例输入 Sample Input
4 2
1 2 3 4
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
分类标签 Tags 点此展开
哈希表 线性结构
代码
#include<map>#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;map<int,bool>q;int n,p,a,b[1000000],sum;int main(){ scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) { scanf("%d",&b[i]); } sort(b+1,b+1+n); for(int i=1;i<=n;i++) { if(!q[b[i]]) { sum++; q[b[i]*p]=1; } } printf("%d",sum); return 0;}
codevs——1553 互斥的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。