「CODEVS1553」互斥的数
题目描述 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
题解
每个数都可以看成是 a*p^b 当俩个数的a相同且b正好相差1，即一个数正好是另一个数的p倍，就会发生冲突
可以考虑一个问题，如果这列数中有 a*p^1,a*p^2…等，最多可以取几个呢。。
略微思考后发现应该从小到大取，比如有1,2,4,p=2
先取1,然后发现2与1冲突,2不取，再取4，像这样
所以得出一个算法，将一个数x不断除以p直到不整除，得到t，放入hash中
如果存在t，检验x是否为该位置的实际数字num[t]的p倍，如果是则舍弃x
不是则ans++，num[t]=x
大概这样。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; int n,p,a[100001],ans; int num[1000008]; void insert(int x) { int t=x; while(t%p==0)t/=p; t=t%1000007; while(1){ if(!num[t]){num[t]=x;ans++;return;} else { if(x%num[t]==0) { if(x/num[t]!=p) { ans++; num[t]=x; } return; } else {t++;if(t==1000008)t=0;} } } } int main() { scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<=n;i++) insert(a[i]); printf("%d",ans); return 0; } |
Subscribe
计数器 9854583
OI 课件=>
OI 课件=>