题意：有N个数的集合，其中选出若干个数组成一个子集，要求这个子集中的任意两个数a,b都不能通过a=k*b得到，其中k是一个素数。求这个子集最大的size。

分析：集合中任意两数的关系是二者之间是否之差一个质因子，那么对于这种关系，本题要求的是N个点的最大独立集。|最大独立集| = 点数 - |二分图最大匹配|。

想到这步之后，就是如何建图的问题。

先预处理筛出一定范围内的素数。对于每个集合内的数a，检查其除去一个质因子后得到的数at是否在集合中出现，若出现则将a到at和at到a建边。

因为是双向建边，所以得到的最大匹配数是两倍，除以2即可。

#include
     
          using namespace std;    typedef long long LL;    const int MAXN = 50010;    const int MAXM = 1010*1010;    const int INF = 0x3f3f3f3f;    int N;    struct Node{        int x,y;    }p[MAXN],it[MAXN];    int v[MAXN];    struct Edge{        int v;        int next;    }edge[MAXM];        int nx, ny;    int cnt;    int t;    int dis;    int first[MAXN];    int xlink[MAXN], ylink[MAXN];     /*xlink[i]表示左集合顶点所匹配的右集合顶点序号，ylink[i]表示右集合i顶点匹配到的左集合顶点序号。*/    int dx[MAXN], dy[MAXN];     /*dx[i]表示左集合i顶点的距离编号，dy[i]表示右集合i顶点的距离编号*/    int vis[MAXN]; //寻找增广路的标记数组     void init(){        cnt = 0;        memset(first, -1, sizeof(first));        memset(xlink, -1, sizeof(xlink));        memset(ylink, -1, sizeof(ylink));    }        void AddEdge(int u, int v){        edge[cnt].v = v;        edge[cnt].next = first[u], first[u] = cnt++;    }        int bfs()    {        queue
      
        q;        dis = INF;        memset(dx, -1, sizeof(dx));        memset(dy, -1, sizeof(dy));        for(int i = 1; i <= nx; i++){            if(xlink[i] == -1){                q.push(i);                dx[i] = 0;            }        }        while(!q.empty()){            int u = q.front(); q.pop();            if(dx[u] > dis) break;            for(int e = first[u]; e != -1; e = edge[e].next){                int v = edge[e].v;                if(dy[v] == -1){                    dy[v] = dx[u] + 1;                    if(ylink[v] == -1) dis = dy[v];                    else{                        dx[ylink[v]] = dy[v]+1;                        q.push(ylink[v]);                    }                }            }        }        return dis != INF;    }        int find(int u){        for(int e = first[u]; e != -1; e = edge[e].next){            int v = edge[e].v;            if(!vis[v] && dy[v] == dx[u]+1){                vis[v] = 1;                if(ylink[v] != -1 && dy[v] == dis) continue;                if(ylink[v] == -1 || find(ylink[v])){                    xlink[u] = v, ylink[v] = u;                    return 1;                }            }        }        return 0;    }        int MaxMatch()    {        int ans = 0;        while(bfs()){            memset(vis, 0, sizeof(vis));            for(int i = 1; i <= nx; i++)                 if(xlink[i] == -1)                      ans += find(i);        }        return ans;    }    const int MAXV = 50005;    int prime[MAXV];    bool notprime[MAXV*10];    void pre()    {        int up  = MAXV *10;        memset(notprime,0,sizeof(notprime));        notprime[0] = notprime[1] = true;        memset(prime,0,sizeof(prime));        for(int i=2;i
       
        1) fac[sum++] = tmp,all++;        for(int i=0;i