D. 图G
不难，主要考察计数。
首先有个结论：\(\gcd(a, b)\) 是 \(c\) 的倍数，当且仅当 \(a,b\) 均是 \(c\) 的倍数。
所以原条件可以改成：对 \(\forall 1 \leq i < j \leq n\)，\(a_{i}\) 与 \(a_{j}\) 均为 \(b_{i} \times b_{j}\) 倍数的 \((i, j)\) 计数。
固定每个端点，统计另一个端点的做法是很困难的，注意到 \(b_{i} \leq 1000\)，而原序列中每一对 \((a_{i}, b_{i})\) 的顺序并不重要，于是我们可以考虑对不同取值的 \(b_{i}\) 计数。
注意到，若对于某个 \(i\)，\(b_{i} \nmid a_{i}\)，则原条件显然不成立。故我们可以直接舍弃掉这样的 \((a_{i}, b_{i})\)。
对于 “\(a_{i}\) 与 \(a_{j}\) 均为 \(b_{i} \times b_{j}\) 倍数” 这个条件，若均有 \(b_{i} \mid a_{i}\)，\(b_{j} \mid a_{j}\) 存在，则可以进一步将条件改写为：\(c_{i} = a_{i} / b_{i}\) 是 \(b_{j}\) 的倍数 且 \(c_{j} = a_{j} / b_{j}\) 是 \(b_{i}\) 的倍数。
预处理一个桶 \(cnt_{u,v}\)：在原序列中，满足 \(b_{i} = u\)，且 \(c_{i} = a_{i} / b_{i}\) 是 \(v\) 的倍数，这样的 \((a_{i}, b_{i})\) 个数。其中 \(u, v \leq 1000\)。这个桶可以在 \(O(1000*n)\) 的复杂度中预处理出来，常数很小，可以做到。
考虑枚举 \(b_{i}, b_{j}\)。我们不实际枚举 \(i\) 和 \(j\)，而是直接枚举 \(b_{i}\) 与 \(b_{j}\) 的值，复杂度 \(O(1000 * 1000)\)。设枚举的两个变量分别为 \(b_{i} = u\)，\(b_{j} = v\)。根据变式的要求，对于 \(u\)，我们应该找到 \(c_{i}\) 是 \(v\) 的倍数的 \((a_{i}, u)\) 的数量，显然就是 \(cnt_{u, v}\)；同理对于 \(v\)，合法的 \((a_{j}, v)\) 的数量就是 \(cnt_{v, u}\)。所以此时的贡献就是 \(cnt_{u, v} * cnt_{v, u}\)。注意当 \(u = v\) 时，不能选同一位置上的 \(u, v\)，此时贡献是 \(\frac{cnt_{u, u} * (cnt_{u, u} - 1)}{2}\)。枚举每对 \((u, v)\) 计数即可。
code