https://codeforces.com/problemset/problem/2131/H
题解
先探索一下只找一个 pair 怎么做。
对于 \(a_i>1\) 的平凡情况，我们想寻找 \(\sum [\gcd(a_i,a_j)=1]\)，来判断是否存在和它互质的。直接套用莫比乌斯反演：
\[\sum [\gcd(a_i,a_j)=1]=\sum_j\sum_{d|a_i,a_j}\mu(d)=\sum_{d|a_i}\mu(d)\sum_j[d|a_j]
\]
而我们直接预处理 \(f(d)=\sum_j[d|a_j]\)，就可以在很快的时间对于每个 ai 都求出和它互质的数的个数。
接下来是一个图论问题，把数字看作点，互质关系看作边，那么就是要找到两个匹配。这是一件很简单的事情。