Prime Independen 素数拆分+二分图匹配+最大独立集

A set of integers is called prime independent if none of its member is a prime multiple of another member. An integer a is said to be a prime multiple of b if,

a = b x k (where k is a prime [1])

So, 6 is a prime multiple of 2, but 8 is not. And for example, {2, 8, 17} is prime independent but {2, 8, 16}&nbs***bsp;{3, 6} are not.

Now, given a set of distinct positive integers, calculate the largest prime independent subset.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with an integer N (1 ≤ N ≤ 40000) denoting the size of the set. Next line contains N integers separated by a single space. Each of these Nintegers are distinct and between 1 and 500000 inclusive.

Output

For each case, print the case number and the size of the largest prime independent subset.

Sample Input

2 4 8 16 32

2 3 4 6 9

1 2 3

Sample Output

Case 1: 3

Case 2: 3

Case 3: 2

Note

1. An integer is said to be a prime if it's divisible by exactly two distinct integers. First few prime numbers are 2, 3, 5, 7, 11, 13, ...

2. Dataset is huge, use faster I/O methods.

题目大意：给你n个数，定义：如果两个数 a,b 满足a*k=b 且k为素数，这时说 b为a的素数倍，求n个数中最多可以选出多少个数，使得两两互不为素数倍。

题目思路：

思路很简单，最大独立集的裸题，我们a 与b 如果有关系我们就建一条双向边，这里说一下，怎么建图：

首先我们把 n个数质因子分解，存储它的每一个质因子。最后对质因子进行判断，如果当前数/质因子这个数存在，就建立一条边。最后判断即可。

~~这个题把我wa飞了，最后质因子分解不对。~~

AC：

#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#pragma GCC optimize(2)
typedef long long ll;
const int mod=998244353;
const int maxn=5e5+5;
const ll INF=10000000000000005;
using namespace std;
ll n,m,p,lm;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int prime[maxn];
bool vis[maxn];
int num[maxn];
int dR[maxn],dL[maxn];//增广路距离
int nR[maxn],nL[maxn];//左右标记
int used[maxn];//使用标记
int pos[maxn];
int head[maxn];
ll cnt=0,dis;
int save[40005];
struct node{
    int e,next;
}edge[maxn];
void addedge(int u,int v)
{
    edge[cnt]=node{v,head[u]};
    head[u]=cnt++;
}
bool judge()//寻找最短增广路
{
    queue<int>q;
    memset(dL,-1,sizeof(dL));
    memset(dR,-1,sizeof(dR));
    for(int i=1;i<=n;i++)
    {
        if(nL[i]==-1){
            q.push(i);
            dL[i]=0;
        }
    }
    dis=INF;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        if(dL[u]>dis) break;
        for(int i=head[u];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            if(dR[e]==-1)//保证增广路不相交
            {
                dR[e]=dL[u]+1;
                if(nR[e]==-1) dis=dR[e];
                else{
                    dL[nR[e]]=dR[e]+1;
                    q.push(nR[e]);
                }
            }
        }
    }
    return dis!=INF;
}
bool Find(int x)
{
    for(int i=head[x];~i;i=edge[i].next)
    {
        int e=edge[i].e;
        if(dR[e]==dL[x]+1&&!used[e])
        {
            used[e]=1;
            if(nR[e]!=-1&&dis==dR[e]) continue;//优化
            if(nR[e]==-1||Find(nR[e]))
            {
                nR[e]=x;
                nL[x]=e;
                return true;
            }
        }
    }
    return false;
}
ll MaxMatch()
{
    int res=0;
    while(judge())
    {
        memset(used,0,sizeof(used));
        for(int i=1;i<=n;i++)
            if(nL[i]==-1&&Find(i)) res++;
    }
    return res/2;
}
void restart()
{
    vis[1]=true;
    for(int i=2;i<500005;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            for(int k=2*i;k<500005;k+=i)
                vis[k]=true;
        }
    }
}
int main()
{
    restart();
    int cas=0;
    int T;scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        memset(nR,-1,sizeof(nR));
        memset(nL,-1,sizeof(nL));
        memset(pos,0,sizeof(pos));
        memset(head,-1,sizeof(head));
        scanf("%lld",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            pos[num[i]]=i;
        }
        for(int i=1;i<=n;i++)
        {
            int x=num[i];
            int cot=0;
            for(int k=1;prime[k]*prime[k]<=x;k++)
            {
                int f=0;
                while(x%prime[k]==0)
                {
                    f=1;
                    x/=prime[k];
                }
                if(f) save[++cot]=prime[k];
            }
            if(x>1) save[++cot]=x;
            for(int k=1;k<=cot;k++)
            {
                int y=num[i]/save[k];
                if(pos[y])
                {
                    addedge(i,pos[y]);
                    addedge(pos[y],i);
                }
            }
        }
        int res=MaxMatch();
        res=n-res;
        printf("Case %d: %d\n",++cas,res);
    }
    return 0;
}
/***
4 2 2 1
0 2 10
2 3  20
0 2 5
2 3 14
***/

总结：幸运的是：他把我的HK模板给Hack了，又把我的HK模板优化了一次，写了三个小时，不亏！