题目理解

给定一个长度为 $n$ 的数组 $a$，元素范围 $1 \le a_i \le m$。
需要找到四个互不相同的下标 $p, q, r, s$，使得：

$$\gcd(a_p, a_q) = 1 \quad \text{且} \quad \gcd(a_r, a_s) = 1 $$

如果不存在，输出 $0$；否则输出任意一组解。

---

核心思路

这个问题等价于：在数组中找到两对互质的数对，且四个下标互不相同。

一个重要的观察：
如果数组中存在至少两个与 $1$ 互质的数（即任意两个数都互质），我们可以直接取它们作为一对，另外两个作为另一对。
但更一般的情况，我们考虑用“度数”来度量每个数与其他数互质的数量。

---

第一步：预处理 Möbius 函数

设 $\mu$ 为 Möbius 函数。
对于任意整数 $x$，与 $x$ 互质的数的个数可以用容斥原理计算：

$$\text{cnt\_coprime}(x) = \sum_{d|x} \mu(d) \cdot f(d) $$

其中 $f(d)$ 表示数组中能被 $d$ 整除的数的个数。

---

第二步：计算每个数的互质数量

先统计每个值出现的次数 mp[x]。
然后对每个 $j$，计算 mul[j] = 数组中能被 $j$ 整除的数的个数：

$$\text{mul}[j] = \sum_{k=1}^{\lfloor m/j \rfloor} \text{mp}[j \cdot k] $$

然后对每个 $a_i$，计算与其互质的元素个数：

$$\text{deg}[i] = \sum_{d|a_i} \mu(d) \cdot \text{mul}[d] $$

注意：这个计数包括 $a_i$ 本身（因为 $\gcd(a_i, a_i) = a_i$，不一定为 $1$），所以如果 $a_i=1$，需要额外减 $1$（因为 $1$ 与自身互质，但这里我们要求的是其他元素）。

实际上，$\deg[i]$ 表示数组中有多少个数（包括自己）与 $a_i$ 互质。
我们要的是“其他元素”，所以如果 $a_i=1$，$\deg[i]$ 会多算自己一次，要减去 $1$。

---

第三步：贪心选择一对

我们的目标是找到四个互不相同的下标分成两对，每对互质。

步骤：

1. 找到 $\deg$ 最大的下标 $u$（即与最多数互质的元素）。
   如果 $\deg[u] = 0$，说明没有元素与其他任何数互质（除了自己），则无解。

2. 将 $u$ 作为第一对的第一个元素。
   在剩余元素中，找到第一个与 $a_u$ 互质的元素 $v$。
   这就是第一对 $(u, v)$。

3. 从 $\deg$ 中去除 $u$ 和 $v$ 的影响：
   对所有与 $u$ 互质的元素，$\deg$ 减 $1$；同样对与 $v$ 互质的元素，$\deg$ 减 $1$（因为 $u$ 和 $v$ 已被使用）。

4. 在剩余元素中，再次找到 $\deg$ 最大的元素 $u'$。
   如果 $\deg[u'] = 0$，说明剩余元素中无法找到互质对，输出 $0$。

5. 找到第一个与 $a_{u'}$ 互质的剩余元素 $v'$，作为第二对 $(u', v')$。

6. 输出两对下标（注意转为 $1$-based）。

---

第四步：正确性分析

为什么贪心可行？

• 第一次选择 $\deg$ 最大的 $u$，是为了最大化找到匹配的概率。
• 如果存在至少两对互质对，那么去掉一对后，剩余部分仍然存在至少一对互质对（因为总共至少有两对）。
• $\deg$ 的变化只是减去已经使用的元素，不会破坏剩余元素的互质关系。

实际上，这个算法是基于这样一个事实：
如果存在两个不相交的互质对，那么最大度数的元素一定可以匹配到某个元素形成一对，并且去掉它们后，剩下的元素中仍存在另一对。

---

第五步：复杂度

• 预处理 Möbius 函数：$O(m \log \log m)$
• 计算 mul：$O(m \log m)$
• 计算每个 $\deg$：$O(n \sqrt{a_i})$ 或 $O(n \log a_i)$（枚举约数）
• 贪心选择：$O(n \log n)$ 或 $O(n)$

总复杂度 $O(m \log m + n \sqrt{m})$，在 $m \le 10^6$、总 $n \le 2\times10^5$ 下可行。

---

最终代码（C++，标程逻辑）

#include <bits/stdc++.h>
using i64 = long long;
constexpr int V = 1e6 + 10;

std::array<int, V> mu, comp;
std::vector<int> primes;

void solve() {
    int n, m = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        m = std::max(m, a[i]);
    }
    
    std::vector<int> mul(m + 1), deg(n), mp(m + 1);
    for (int i = 0; i < n; ++i) mp[a[i]]++;
    
    for (int j = 1; j <= m; ++j) {
        for (int x = j; x <= m; x += j) {
            mul[j] += mp[x];
        }
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j * j <= a[i]; ++j) {
            if (a[i] % j == 0) {
                deg[i] += mu[j] * mul[j];
                if (j * j < a[i]) {
                    deg[i] += mu[a[i] / j] * mul[a[i] / j];
                }
            }
        }
        if (a[i] == 1) --deg[i];
    }
    
    std::array<int, 4> ans;
    int u = 0, v = 0, mind = INT32_MAX;
    
    // 第一对
    for (int i = 1; i < n; ++i) {
        if (deg[i] > deg[u]) u = i;
    }
    if (!deg[u]) {
        std::cout << "0\n";
        return;
    }
    deg[u] = 0;
    for (int i = 0; i < n; ++i) {
        if (i == u) continue;
        if (std::gcd(a[i], a[u]) == 1) {
            --deg[i];
            if (mind > deg[i]) {
                mind = deg[i];
                v = i;
            }
        }
    }
    ans[0] = u; ans[1] = v;
    deg[v] = 0;
    
    // 去除与 v 互质的元素的影响
    for (int i = 0; i < n; ++i) {
        if (i == u || i == v) continue;
        if (std::gcd(a[i], a[v]) == 1) {
            --deg[i];
        }
    }
    
    // 第二对
    u = 0;
    for (int i = 1; i < n; ++i) {
        if (deg[i] > deg[u]) u = i;
    }
    if (!deg[u]) {
        std::cout << "0\n";
        return;
    }
    v = -1;
    for (int i = 0; i < n; ++i) {
        if (i == u || !deg[i]) continue;
        if (std::gcd(a[i], a[u]) == 1) {
            v = i;
            break;
        }
    }
    ans[2] = u; ans[3] = v;
    
    for (int i = 0; i < 4; ++i) {
        std::cout << ans[i] + 1 << " \n"[i == 3];
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    std::cin >> T;
    
    // 预处理 Möbius 函数
    mu[1] = 1;
    for (int i = 2; i < V; ++i) {
        if (!comp[i]) {
            primes.emplace_back(i);
            mu[i] = -1;
        }
        for (auto p : primes) {
            int q = i * p;
            if (q >= V) break;
            comp[q] = true;
            if (i % p == 0) {
                mu[q] = 0;
                break;
            } else {
                mu[q] = -mu[i];
            }
        }
    }
    
    while (T--) solve();
    return 0;
}