CodeForces-498C的数论网络流问题，如何巧妙运用数组与操作？

本文共计1270个文字，预计阅读时间需要6分钟。

题目：给定一个长度为 \( n \) 的数组以及一个点集 \( m \)，每次操作可以将相邻的两个点值相同且以一个公约数 \( k \) 相等的点值同时除以 \( k \)。问最多可以进行多少次操作？

题意：给定一个数组 \( \{a_1, a_2, \ldots, a_n\} \) 和一个点集 \( \{(a, b)\} \)，每次操作可以将相邻的两个点 \( a \) 和 \( b \) 的值相同且以一个公约数 \( k \) 相等的点值同时除以 \( k \)。求最多可以进行多少次操作。

「CodeForces-498C」Array and Operations
给定n个点和m个边集，每次操作可以将相连边的两个点值同时除以一个公约数，问最大操作次数

题意

给定一个长为$n$的数组，以及$m$对下标为$(a,b)$的点对，且满足下标a+b为奇数（即奇数点只与偶数点匹配），每次操作可以将同一组的两个数同时除以一个公约数，问最多能进行多少次操作。

解法

显然题目所给的是一个二分图。

对于每个质因数分开考虑。对于奇数点，向源点连接一个容量为该因子个数的边；对于偶数点，则向汇点建立一个容量为因子数的边；对于有边相连的点对，建立容量为$inf$的边。