因为网络流的题一直都做得很烂，所以写一发这个题。
第一眼感觉可以暴力 \(O(n ^ 2)\) 连边，然后我去为什么是价值总和不小于 \(0\)？我的最小费用最大流班子都准备好了？？？
哦（看了一下下题解），这个配对相当于是流量，然后如果我们固定流量的话，最大价值和是有单调性的。很好感性理解，流量越大即『限制越小』，更有可能选到价值高的，所以有单调性。然后就可以直接二分流量（即要求的答案），判定最大价值和是否不小于 \(0\)。
仔细想了想发现好像直接连边假掉了，不是很能做。。。
然后是这样的，就是我们要求 \(\frac{a_i}{a_j}\) 是质数对吧，我们要求质数，直接把 \(a_i, a_j\) 分解质因数，就是 \(\alpha_1 ^ {p_1}\alpha_2 ^ {p_2}\dots\alpha_n ^ {p_n}\) 的形式，那么相除就相当于 \(p\) 做减法，还要求减完是质数，那么有且仅有一个质数的指数为 \(1\)。形式化地说就是 \(\sum\limits_{k = 1} ^ n (p_{i, k} - p_{j, k}) = 1\)。
一开始写了绝对值，但$a_j \mid a_i$，所以 $p_{i, k}$ 一定 $\geq p_{j, k}$。
所以如果满足这个条件，\(\sum p_i\) 和 \(\sum p_j\) 的奇偶性一定不同，所以可以根据分解完指数和和的奇偶性分成两部分，然后就是二分图连边了！
连边的话就价值是 \(c_i \times c_j\)，流量是 \(1\)，然后二分出来的限制就很套路地建两个虚拟源点分别连边，价值 \(0\)，流量 \(mid\) 就好了！
为什么没有代码？因为 gm 开新题了。先把口胡的这玩意放上来。
标签：连边,数字,质数,Solution,流量,alpha,价值,配对,sum From： https://www.cnblogs.com/liuzimingc/p/17991084/number-matching