Codeforces 498C Array and Operations 题解

题意

给一个n个数的序列，若干关系，关系是指可以对给的两个位置的数同时除以一个不为1的数，要求结果也为整数，除以一次记做一次操作，对于给定的关系，一定是一个奇数位置的数和一个偶数位置的数的，同一个关系可以进行多次操作，问最多可以操作多少次

思路

网络流，进行操作除以的数肯定是两个数的公因数，为保证次数最多，就是每一次除以它们的一个公共质因子，那么对于每一个可能会被除的质因数建二分图，如果一个关系的两个数有这个公共质因子，就在二分图连边，奇数位置连向偶数位置，流量为它们可以一起除以多少次这个质因子，然后源点和所有奇数位置连边，流量为该数可以除以多少次这个质因子，偶数位置和汇点连边，流量同理，每一次的最大流加起来就是答案

代码

#include <cstdio> #include <cmath> #include <set> #include <queue> #include <algorithm> using namespace std; #define INF 1000000001 set<int> s; priority_queue<int,vector<int>,greater<int> > pq; int a[102]; int x[101],y[101]; int n,m,g,ans,e,num,cnt1,cnt2,xx,yy,temp; int cnt[102]; int gcd(int x,int y) { if(x%y==0) return y; if(y%x==0) return x; if(x>y) return gcd(y,x%y); else return gcd(x,y%x); } typedef struct edge { int to; int cap; int rev; }edge; vector<edge> v[102]; bool used[102]; void addedge(int from,int to,int cap) { edge temp; temp.to=to; temp.cap=cap; temp.rev=v[to].size(); v[from].push_back(temp); temp.to=from; temp.cap=0; temp.rev=v[from].size()-1; v[to].push_back(temp); return; } int dfs(int s,int t,int f) { int d; if(s==t) return f; used[s]=true; for(int i=0;i<v[s].size();i++) { if(used[v[s][i].to]==false&&v[s][i].cap>0) { d=dfs(v[s][i].to,t,min(f,v[s][i].cap)); if(d>0) { v[s][i].cap-=d; v[v[s][i].to][v[s][i].rev].cap+=d; return d; } } } return 0; } int maxflow(int s,int t) { int flow=0; while(1) { for(int i=0;i<=n+1;i++) used[i]=false; int f=dfs(s,t,INF); if(f==0) return flow; flow+=f; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); ans=0; for(int i=0;i<m;i++) { scanf("%d%d",&x[i],&y[i]); if(x[i]%2==0) swap(x[i],y[i]); g=gcd(a[x[i]],a[y[i]]); e=sqrt(g); //printf("e:%d g:%d\n",e,g); for(int j=2;j<=e;j++) if(g%j==0) { if(s.find(j)==s.end()) { s.insert(j); pq.push(j); //printf("%d ",j); } while(g%j==0) g/=j; e=sqrt(g); } if(g!=1&&s.find(g)==s.end()) { s.insert(g); pq.push(g); //printf("%d ",g); } //printf("\n"); } while(!pq.empty()) { num=pq.top(); pq.pop(); for(int i=0;i<m;i++) { cnt1=0; cnt2=0; xx=a[x[i]]; yy=a[y[i]]; while(xx%num==0) { cnt1++; xx/=num; } while(yy%num==0) { cnt2++; yy/=num; } if(cnt1!=0&&cnt2!=0) addedge(x[i],y[i],min(cnt1,cnt2)); } for(int i=1;i<=n;i++) { temp=a[i]; while(temp%num==0) { temp/=num; cnt[i]++; } } for(int i=1;i<=n;i+=2) if(cnt[i]!=0) addedge(0,i,cnt[i]); for(int i=2;i<=n;i+=2) if(cnt[i]!=0) addedge(i,n+1,cnt[i]); /*for(int i=0;i<=n+1;i++) for(int j=0;j<v[i].size();j++) printf("x:%d y:%d cap:%d\n",i,v[i][j].to,v[i][j].cap);*/ ans+=maxflow(0,n+1); for(int i=0;i<=n+1;i++) v[i].clear(); for(int i=0;i<=n+1;i++) cnt[i]=0; } printf("%d\n",ans); return 0; }