互斥的数（codevs 1553）

题目描述 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

/*

  改了两个小时，把int改成long long 就对了，我晕……

  做法：由于对于每个数，和它互斥的数只有一个，所以可以找到和它互斥的数，然后建一条边，

        建边式统计入度，这样很多点就会成为一条链。对于每条链，如果它有tot个节点，我们

        最多能取 (tot-1)/2 个点，统计总点数。

*/

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<vector>

#define ll long long

#define M 100010

using namespace std;

ll n,p,a[M],in[M],tot;

vector<ll> grap[M];

void dfs(int x)

{

    tot++;

    for(ll i=;i<grap[x].size();i++)

      dfs(grap[x][i]);

}

int main()

{

    cin>>n>>p;

    for(ll i=;i<=n;i++)

      cin>>a[i];

    sort(a+,a+n+);

    for(ll i=;i<=n;i++)

    {

        if(a[i]*p>1e9)continue;

        ll pos=lower_bound(a+i+,a+n+,a[i]*p)-a;

        if(pos>i&&pos<=n&&a[i]*p==a[pos])

          grap[i].push_back(pos),in[pos]++;

    }

    ll ans=;

    for(ll i=;i<=n;i++)

      if(!in[i])

      {

          tot=;dfs(i);

          ans+=(tot+)/;

      }

    cout<<ans;

    return ;

}

/*

  另一种做法 hash

*/

#include<iostream>

#include<algorithm>

#include<cstdio>

#define mod 1358717

#define M 100010

#define ll long long

using namespace std;

ll head[mod+],a[M],n,m,cnt;

struct node

{

    ll v,pre;

};node e[M];

void add(ll x,ll v)

{

    ++cnt;

    e[cnt].v=v;

    e[cnt].pre=head[x];

    head[x]=cnt;

}

bool find(ll x,ll v)

{

    for(ll i=head[x];i;i=e[i].pre)

      if(e[i].v==v)return true;

    return false;

}

int main()

{

    cin>>n>>m;

    for(ll i=;i<=n;i++)

      cin>>a[i];

    sort(a+,a+n+);

    ll ans=;

    for(ll i=;i<=n;i++)

    {

        if(find(a[i]%mod,a[i]))continue;

        ll v=a[i]*m;

        if(v<=1e9)add(v%mod,v);

        ++ans;

    }

    cout<<ans;

    return ;

}