题目链接：

题意：给定n个数，找到一个最大的集合使得集合中不存在任意两个数a和b，使得b=a*k(k为素数)。

思路：对于每个数x定义f(x),若x=p1^e1*………pt^et。f(x)=e1+e2+……et。那么可知，若两个数a和b满足b=a*k(k为素数)，则f(a)和f(b)的奇偶性必然不同。据此建立二分图，设最大匹配为x，则 答案为n-x。

#include 
     
      #include 
      
       #include 
       
        #define max(x,y) ((x)>(y)?(x):(y))#define i64 long long#define u32 unsigned intusing namespace std;  int C,Num=0;  const i64 MAX=500005;bool tag[MAX];int prime[MAX/10],cnt;int p[MAX];  void init(){    int i,j;    for(i=2;i<710;i++) if(!tag[i])    {        prime[cnt++]=i;        for(j=i+i;j<710;j+=i) tag[j]=1;    }    for(i=2;i
        
         ='0'&&c<='9');c=getchar());    x=c-'0';    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';} int main(){    init();    for(scanf("%d",&C);C--;)    {        read(n);        int i,j,k,t;        memset(b,0,sizeof(b));        for(i=1;i<=n;i++)        {            read(a[i]);            b[a[i]]=i;        }        for(i=1;i<=n;i++) head[i]=-1;        e=0;        int pr[25],prNum;        for(i=1;i<=n;i++)        {            t=a[i];            prNum=0;            for(j=0;j
         
          <=t;j++) if(t%prime[j]==0)            {                pr[++prNum]=prime[j];                while(t%prime[j]==0) t/=prime[j];            }            if(t>1) pr[++prNum]=t;            for(j=1;j<=prNum;j++)            {                k=a[i]/pr[j];                if(!b[k]) continue;                if(p[a[i]]&1) Add(b[a[i]],b[k]);                else Add(b[k],b[a[i]]);             }        }        printf("Case %d: %d\n",++Num,n-MaxMatch());    }    return 0;}