给n个数， m个数对， 每个数对是两个下标加起来为奇数的两个数。每次操作可以使一个数对中的两个数同时除某个数， 除的这个数是这两个数的任意约数， 问这种操作最多可以做几次。n<100, m<100。
这个数据范围， 以及下标加起来为奇数...好明显的网络流暗示。
首先对每个数分解， 看它含有哪些素因子， 每个素因子的个数是多少， 因为只有100个数， 所以素因子的总数不是很多。
然后枚举每个素因子。对每个数对中的两个数连边， 如果下标是奇数， 源点就向这个数连边， 下标是偶数， 这个数向汇点连边。 权值为这个数含有这个素因子的个数。
然后跑很多遍网络流， 答案就是所有结果相加。
具体可以看代码
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
map <int, int> mp[], ma;
pll b[];
const int maxn = 2e4;
int q[maxn*], head[maxn*], dis[maxn/], s, t, num;
int vis[];
struct node
{
int to, nextt, c;
node(){}
node(int to, int nextt, int c):to(to), nextt(nextt), c(c){}
}e[maxn*];
void init() {
num = ;
mem1(head);
mem(vis);
}
void add(int u, int v, int c) {
e[num] = node(v, head[u], c); head[u] = num++;
e[num] = node(u, head[v], ); head[v] = num++;
}
int bfs() {
mem(dis);
dis[s] = ;
int st = , ed = ;
q[ed++] = s;
while(st<ed) {
int u = q[st++];
for(int i = head[u]; ~i; i = e[i].nextt) {
int v = e[i].to;
if(!dis[v]&&e[i].c) {
dis[v] = dis[u]+;
if(v == t)
return ;
q[ed++] = v;
}
}
}
return ;
}
int dfs(int u, int limit) {
if(u == t) {
return limit;
}
int cost = ;
for(int i = head[u]; ~i; i = e[i].nextt) {
int v = e[i].to;
if(e[i].c&&dis[v] == dis[u]+) {
int tmp = dfs(v, min(limit-cost, e[i].c));
if(tmp>) {
e[i].c -= tmp;
e[i^].c += tmp;
cost += tmp;
if(cost == limit)
break;
} else {
dis[v] = -;
}
}
}
return cost;
}
int dinic() {
int ans = ;
while(bfs()) {
ans += dfs(s, inf);
}
return ans;
}
int main()
{
int n, m, x;
cin>>n>>m;
for(int i = ; i<n; i++) {
scanf("%d", &x);
for(int j = ; j*j<=x; j++) {
if(x%j==) {
mp[i][j] = ; //mp是看第i个数含有素数j的个数
ma[j] = ; //ma是存储这n个数所有的素因子
}
while(x%j==) {
x/=j;
mp[i][j]++;
}
}
if(x>) {
mp[i][x] = ;
ma[x] = ;
}
}
for(int i = ; i<m; i++) {
cin>>b[i].fi>>b[i].se;
b[i].fi--, b[i].se--;
}
auto it = ma.begin();
int ans = ;
while(it != ma.end()) {
int pri = it->first; //枚举所有素因子
init();
s = n+, t = n+;
for(int i = ; i<m; i++) {
if(b[i].fi%==) {
add(b[i].fi, b[i].se, inf);
if(!vis[b[i].fi]) {
add(s, b[i].fi, mp[b[i].fi][pri]); //如果这个数之前没出现过， 那么就向源点或者汇点连边。
vis[b[i].fi] = ;
}
if(!vis[b[i].se]) {
add(b[i].se, t, mp[b[i].se][pri]);
vis[b[i].se] = ;
}
} else {
add(b[i].se, b[i].fi, inf);
if(!vis[b[i].fi]) {
add(b[i].fi, t, mp[b[i].fi][pri]);
vis[b[i].fi] = ;
}
if(!vis[b[i].se]) {
add(s, b[i].se, mp[b[i].se][pri]);
vis[b[i].se] = ;
}
}
}
int tmp = dinic();
ans += tmp;
it++;
}
cout<<ans<<endl; }