摘要

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

题意

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

题解

  • 先排个序(直接扔到set里),如果找到一串a,P*a,P*P*a...,P^n*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;
}

著作权声明[编辑]

关于[编辑]