Link do Problema

Luogu CF1884D, Codeforces 1884D

Tradução do Problema

Dada uma sequência \(a\) de comprimento \(n\), um par \((i, j)\) com \(1 \leq i < j \leq n\) é considerado válido se não existir nenhum índice \(k\) (de 1 a \(n\)) tal que \(a_k\) divide \(a_i\) e \(a_k\) divide \(a_j\) simultaneamente. Calcule o número de pares válidos. As restrições são \(1 \leq a_i \leq n \leq 10^6\).

Formato de Entrada

Cada teste contém múltiplos casos. A primeira linha indica o número de casos \(t\) (\(1 \leq t \leq 2 \times 10^4\)). A descrição dos casos segue:

• Primeira linha: inteiro \(n\) (\(1 \leq n \leq 10^6\))
• Segunda linha: \(n\) inteiros \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\))

A soma de \(n\) em todos os casos não excede \(10^6\).

Formato de Saída

Para cada caso, imprima o número de pares válidos.

Exemplo de Entrada/Saída

Entrada:
6
4
2 4 4 4
4
2 3 4 4
9
6 8 9 4 6 8 9 4 9
9
7 7 4 4 9 9 6 2 9
18
10 18 18 15 14 4 5 6 8 9 10 12 15 16 18 17 13 11
21
12 19 19 18 18 12 2 18 19 12 12 3 12 12 12 18 19 16 18 19 12

Saída:
0
3
26
26
124
82

Abordagem de Solução

Um par \((i, j)\) é inválido se existir \(a_k\) tal que \(a_k\) divide \(\gcd(a_i, a_j)\). Definimos:

• \(freq[x]\): frequência do número \(x\) no array
• \(contagemMultiplos[i]\): quantidade de pares onde \(\gcd(a_i, a_j)\) é múltiplo de \(i\)
• \(valido[i]\): indica se \(i\) não é múltiplo de nenhum elemento do array

Usamos a função de Möbius para aplicar inclusão-exclusão e calcular pares válidos. Passos:

1. Pré-calcular a função de Möbius
2. Para cada caso:
   • Calcular frequências e marcar números presentes
   • Marcar múltiplos de números presentes como inválidos
   • Calcular \(contagemMultiplos[i]\) para cada \(i\)
   • Combinar resultados usando Möbius e contadores de validade

Código

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000010;
vector<long long> mobius(MAX);
vector<int> primes;
vector<bool> isPrime(MAX, true);

void precalcularMobius() {
    mobius[1] = 1;
    for (int i = 2; i < MAX; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            mobius[i] = -1;
        }
        for (int p : primes) {
            if (i * p >= MAX) break;
            isPrime[i * p] = false;
            if (i % p == 0) {
                mobius[i * p] = 0;
                break;
            } else {
                mobius[i * p] = -mobius[i];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    precalcularMobius();
    int casos;
    cin >> casos;
    while (casos--) {
        int n;
        cin >> n;
        vector<long long> freq(n + 1, 0);
        vector<bool> presente(n + 1, false);
        vector<bool> valido(n + 1, true);
        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;
            freq[num]++;
            presente[num] = true;
        }
        for (int i = 1; i <= n; i++) {
            if (presente[i]) {
                for (int j = i; j <= n; j += i) {
                    valido[j] = false;
                }
            }
        }
        vector<long long> contagemMultiplos(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            long long total = 0;
            for (int j = i; j <= n; j += i) {
                total += freq[j];
            }
            contagemMultiplos[i] = total * (total - 1) / 2;
        }
        long long resposta = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * i <= n; j++) {
                resposta += contagemMultiplos[i * j] * mobius[j] * valido[i];
            }
        }
        cout << resposta << '\n';
    }
    return 0;
}