Counting Coprime Pairs

Explicación

Un enfoque de fuerza bruta verificaría cada par $(i, j)$ y calcularía $\gcd(a_i, a_j)$. Esto toma tiempo $\mathcal{O}(N^2 \log A)$, que es demasiado lento para $N$ grandes.

En lugar de verificar directamente si $\gcd(x, y) = 1$, contamos pares agrupándolos según su gcd.

¿Cómo agruparlos?

Sea:

• count[d] = número de elementos del arreglo divisibles por $d$.
• pairs[d] = número de pares cuyo gcd es exactamente $d$.

Si count[d] elementos son divisibles por $d$, entonces el número de pares no ordenados entre ellos es:

Sin embargo, esto cuenta pares cuyo gcd es $d$, $2d$, $3d$ y así sucesivamente.

Así que debemos restar los pares sobrecontados.

Paso 1: Contar múltiplos

Para cada $d$ de $1$ a $\text{maxVal}$, iteramos sobre sus múltiplos:

count[d] += freq[multiple]

Después de este bucle, count[d] guarda cuántos números son divisibles por $d$.

Este preprocesamiento corre en tiempo armónico:

Paso 2: Inclusión-exclusión sobre el GCD

Ahora calculamos pairs[d] desde el $d$ más grande hacia $1$.

Para un $d$ fijo:

1. Empezamos con todos los pares divisibles por $d$:

   $$\text{total} = \binom{\text{count}[d]}{2}$$

2. Restamos los pares ya asignados a múltiplos de $d$:

   $$\text{pairs}[d] = \text{total} - \sum_{k \ge 2} \text{pairs}[k \cdot d]$$

¿Por qué funciona esto?

• Cada par con gcd igual a algún múltiplo $k d$ se incluyó en total.
• Como procesamos en orden decreciente de $d$, todos los pairs[k*d] ya están calculados.
• Restarlos deja solo los pares cuyo gcd es exactamente $d$.

Esto es inclusión-exclusión clásica sobre divisores.

Se nos pide contar pares que son coprimos, es decir, gcd(x, y) = 1. Así que la respuesta es pairs[1].

Implementación

Complejidad temporal: $\mathcal{O}(A \log A + N)$,

#include <bits/stdc++.h>
using namespace std;
 
const int MAXA = 1e6 + 5;
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
 
	vector<int> freq(MAXA, 0);
	int maxVal = 0;
 
	int x;
	for (int i = 0; i < n; ++i) {
		cin >> x;
		freq[x]++;
		maxVal = max(maxVal, x);
	}
 
	vector<long long> count(maxVal + 1, 0);
	vector<long long> pairs(maxVal + 1, 0);
 
	for (int d = 1; d <= maxVal; ++d)
		for (int mult = d; mult <= maxVal; mult += d) count[d] += freq[mult];
 
	// Inclusion - Exclusion Principle
	for (int d = maxVal; d >= 1; --d) {
		long long total = count[d] * (count[d] - 1) / 2;
 
		for (int mult = 2 * d; mult <= maxVal; mult += d) total -= pairs[mult];
 
		pairs[d] = total;
	}
 
	cout << pairs[1] << '\n';
	return 0;
}