如果能在 $T(n)$ 时间内求出 $c_1$，则可以在 $T(n)+T(\frac n2)+T(\frac n3)+\cdots$ 的时间内解决整个问题。

不妨设 $a_i\ge b_j$，我们想对每个 $a_i$，找到最小的 $b_j$ 使得 $\gcd(i,j)=1$。整体二分，问题转化为判定是否存在 $b_j\le M$ 且 $\gcd(i,j)=1$。莫比乌斯反演可以得到这样的数的个数为 $\sum_{d\mid i}cnt(d)\cdot \mu(d)$，其中 $cnt(d)$ 表示 $\le M$ 的 $b_j$ 中，是 $d$ 的倍数的 $j$ 的个数，于是可以在 $O(\sum_{i=1}^n d(i))=O(n\log n)$ 的时间内完成判定。因此，求出 $c_1$ 的时间复杂度为 $O(n\log^2 n)$，总时间复杂度 $O(n\log ^3n)$。