很显然的二分图。只不过建图麻烦，其实也不是很麻烦，暴力搞就行。
把因子单独拿出来建图。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int inf=0x3f3f3f3f; const int N=2e4+10,M=1e6+10; int n,m,a[N],cnt,s,t,h[N]; map<int,int> mp[N]; int head[N],nex[M],to[M],w[M],tot=1; vector<int> v[N]; inline void ade(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;} inline void add(int a,int b,int c){ade(a,b,c); ade(b,a,0);} inline int get(int id,int x){if(!mp[id][x]) mp[id][x]=++cnt; return mp[id][x];} inline int bfs(){ queue<int> q; q.push(s); memset(h,0,sizeof h); h[s]=1; while(q.size()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=nex[i]) if(w[i]&&!h[to[i]]) h[to[i]]=h[u]+1,q.push(to[i]); } return h[t]; } int dfs(int x,int f){ if(x==t) return f; int fl=0; for(int i=head[x];i&&f;i=nex[i]){ if(w[i]&&h[to[i]]==h[x]+1){ int mi=dfs(to[i],min(w[i],f)); w[i]-=mi,w[i^1]+=mi,fl+=mi,f-=mi; } } if(!fl) h[x]=-1; return fl; } inline int dinic(){ int res=0; while(bfs()) res+=dfs(s,inf); return res; } signed main(){ cin>>n>>m; t=N-5; cnt=n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ int now=a[i]; if(i&1){ add(s,i,inf); for(int j=2;j*j<=now;j++) if(now%j==0){ int tmp=0; while(now%j==0) tmp++,now/=j; add(i,get(i,j),tmp),v[i].push_back(j); } if(now>1) add(i,get(i,now),1),v[i].push_back(now); }else{ add(i,t,inf); for(int j=2;j*j<=now;j++) if(now%j==0){ int tmp=0; while(now%j==0) tmp++,now/=j; add(get(i,j),i,tmp),v[i].push_back(j); } if(now>1) add(get(i,now),i,1),v[i].push_back(now); } } for(int i=1,x,y;i<=m;i++){ cin>>x>>y; if(x%2==0) swap(x,y); for(auto j:v[x]) if(mp[y][j]) add(get(x,j),get(y,j),inf); } cout<<dinic(); return 0; }