link：https://codeforces.com/contest/1630/problem/F
给你一个由 \(n\) 个顶点组成的无向图，编号从 \(1\) 到 \(n\) ，其中顶点 \(i\) 的值为 \(a_i\) ，所有值 \(a_i\) 都是不同的。如果 \(a_u\) 整除 \(a_v\) ，则两个顶点 \(u\) 和 \(v\) 之间存在一条边。当删除一个顶点时，也就删除了与之相连的所有边。
问最少删几个点使得得到的是二分图。
\(1\leq n\leq 5\times 10^4\).
首先整除是个偏序关系，它比DAG的性质来得强：如果 \(a|b,b|c\) 则必有 \(a|c\)，翻译过来就是如果有边 \(u\to v,v\to w\) 则必有 \(u\to w\)，这样就出现了一个三元环。
换言之如果把无向边改成有向边（例如大的连小的），如果要得到二分图，那么不能有长度 \(\geq 2\) 的链，即每条链最长是 \(1\)，也就是说每个点要么只有入度，要么只有出度，此时也一定是二分图。
那么就能把点分成两类，拆点：\(u\) 表示 \(u\) 只有出度，\(u'\) 表示只有入度，\((u,u')\) 连一条无向边表示两个事件不能同时发生。如果原图有 \(u\to v\) 的边，则 \(u,v\) 明显也不能同时有出度（这意味着 \(v\) 有入度），因此有 \((u,v)\) 的边，类似地会有 \((u',v'),(u',v)\) 这些边
这样得到了一张新的二分图，图上任意一条边表示两端的事件不能同时发生，如果要保留最多的点，相当于求最大独立集，即求最大的点集 \(V'\subset V\)， 使得 \(V'\) 内任意两个点之间无边。
而注意到 这张二分图是可以变成偏序集的：
\(ans=n-\) 留下的最多点
留下的最多点=这张图的最大独立集=补图的最长链，补图的边数太多了，而根据Dilworth定理，偏序集上的最长链=补图的最小边覆盖，因此图的最大独立集=最小边覆盖，对这张DAG求个最小路径覆盖=拆点后点数-最小割。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef pair<int,int> pii;template<class T>
struct Dinic{//ind from 0 to n-1struct Edge{int to;T cap;Edge(int to,T cap):to(to),cap(cap){}};int n;vector<Edge> E;vector<vector<int>> G;vector<int> cur,h;Dinic(int n=0){init(n);}void init(int n){this->n=n;E.clear();cur.resize(n);h.resize(n);G.assign(n,{});}void addEdge(int u,int v,T c){G[u].push_back(E.size());E.emplace_back(v,c);G[v].push_back(E.size());E.emplace_back(u,0);}bool bfs(int s,int t){h.assign(n,-1);queue<int> que;h[s]=0;que.push(s);while(!que.empty()){const int u=que.front();que.pop();for(auto i:G[u]){auto [v,c]=E[i];if(c>0&&h[v]==-1){h[v]=h[u]+1;if(v==t)return true;que.push(v);}}}return false;}T dfs(int u,int t,T f){if(u==t)return f;auto r=f;for(int &i=cur[u];i<(int)G[u].size();i++){const int j=G[u][i];auto [v,c]=E[j];if(c>0&&h[v]==h[u]+1){auto a=dfs(v,t,std::min(r,c));E[j].cap-=a;E[j^1].cap+=a;r-=a;if(r==0)return f;}}return f-r;}T work(int s,int t){T ans=0;while(bfs(s,t)){cur.assign(n,0);ans+=dfs(s,t,std::numeric_limits<T>::max());}return ans;}
};
int main(){fastio;constexpr int N=5e4;constexpr int INF=std::numeric_limits<int>::max();int tc;cin>>tc;vector<vector<int>> divisor(N+5);rep(i,1,N)for(int j=i+i;j<=N;j+=i)divisor[j].push_back(i);while(tc--){int n;cin>>n;vector<pii> E;auto work=[&](int n)->int{int st=2*n,ed=2*n+1;Dinic<int> flow(ed+1);for(auto [u,v]:E)flow.addEdge(u,v+n,1);rep(i,0,n-1){flow.addEdge(st,i,1);flow.addEdge(i+n,ed,1);}return n-flow.work(st,ed);};set<int> S;map<int,int> idx;rep(i,0,n-1){int x;cin>>x;S.insert(x);idx[x]=i;E.push_back({idx[x]+n,idx[x]});}for(auto u:S){for(auto v:divisor[u])if(S.contains(v)){E.push_back({idx[u],idx[v]});E.push_back({idx[u]+n,idx[v]+n});E.push_back({idx[u]+n,idx[v]});}}cout<<n-work(n<<1)<<endl;}return 0;
}
