Common Divisor

Solución 1

El enfoque naive sería probar por fuerza bruta cada par de números del arreglo y calcular el GCD máximo. Lamentablemente, esta solución da TLE en alrededor de la mitad de los casos de prueba.

Implementación

Complejidad temporal: $\mathcal{O}(N^2\log(\max(x_i)))$

C++JavaPython


#include <iostream>
using namespace std;
 
const int MAX_N = 2e5;
 
int arr[MAX_N];
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) { cin >> arr[i]; }
 
	int ans = 1;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) { ans = max(ans, gcd(arr[i], arr[j])); }
	}
	cout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class CommonDivisors {
	public static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
 
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader io = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(io.readLine());
		int[] arr = Arrays.stream(io.readLine().split(" "))
		                .mapToInt(Integer::parseInt)
		                .toArray();
		int ans = 1;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				ans = Math.max(ans, gcd(arr[i], arr[j]));
			}
		}
		System.out.println(ans);
	}
}


from math import gcd
 
n = int(input())
 
arr = list(map(int, input().split()))
 
ans = 1
for i in range(n - 1):
	for j in range(i + 1, n):
		ans = max(ans, gcd(arr[i], arr[j]))
 
print(ans)

Solución 2

Mantenemos un arreglo, $\texttt{cnt}$ , para guardar el conteo de divisores. Para cada valor del arreglo, hallamos sus divisores y, para cada $u$ entre esos divisores, incrementamos $\texttt{cnt}$ en uno. El GCD más grande compartido por dos elementos del arreglo será el mayor índice en nuestro conteo de divisores con un conteo mayor o igual que $2$ .

Implementación

Complejidad temporal: $\mathcal{O}(N\sqrt{\max(x_i)})$

C++JavaPython


#include <cmath>
#include <iostream>
using namespace std;
 
const int MAX_VAL = 1e6;
 
// divisors[i] = guarda el conteo de números que tienen a i como divisor
int divisors[MAX_VAL + 1];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
 
		const int up = (int)sqrt(a);
		for (int div = 1; div <= up; div++) {
			if (a % div == 0) {
				// el divisor y el cociente son ambos divisores de a
				divisors[div]++;
				// ¡cuidado de no contar dos veces!
				if (div != a / div) { divisors[a / div]++; }
			}
		}
	}
 
	for (int i = MAX_VAL; i >= 1; i--) {
		if (divisors[i] >= 2) {
			cout << i << endl;
			break;
		}
	}
}


import java.io.*;
import java.util.*;
 
public class CommonDivisors {
	public static final int MAX_VAL = 1000000;
 
	// divisors[i] = guarda el conteo de números que tienen a i como divisor
	public static int[] divisors = new int[MAX_VAL + 1];
 
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader io = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(io.readLine());
		int[] arr = Arrays.stream(io.readLine().split(" "))
		                .mapToInt(Integer::parseInt)
		                .toArray();
		for (int i = 0; i < n; i++) {
			int up = (int)Math.sqrt(arr[i]);
			for (int div = 1; div <= up; div++) {
				if (arr[i] % div == 0) {
					// el divisor y el cociente son ambos divisores de a
					divisors[div]++;
					// ¡cuidado de no contar dos veces!
					if (div != arr[i] / div) { divisors[arr[i] / div]++; }
				}
			}
		}
 
		for (int i = MAX_VAL; i >= 1; i--) {
			if (divisors[i] >= 2) {
				System.out.println(i);
				break;
			}
		}
	}
}


from math import sqrt
 
MAX_VAL = 1000000
divisors = [0] * (MAX_VAL + 1)
 
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	up = int(sqrt(a[i]))
	for div in range(1, up + 1):
		if a[i] % div == 0:
			# el divisor y el cociente son ambos divisores de a
			divisors[div] += 1
			# ¡cuidado de no contar dos veces!
			if div != a[i] // div:
				divisors[a[i] // div] += 1
 
for i in range(MAX_VAL, 0, -1):
	if divisors[i] >= 2:
		print(i)
		break

Solución 3

Dado un valor $x$ , podemos comprobar si un par tiene GCD igual a $x$ revisando todos los múltiplos de $x$ . Con esa información, recorremos todos los valores posibles de $x$ y comprobamos si es divisor de dos o más valores. Esto funciona en $\mathcal{O}(\max(x_i)\log(\max(x_i)))$ ya que

\sum_{i = 1}^{\max(x_i)} \max(x_i)/i \approx \max(x_i)\log(\max(x_i)).

Implementación

Complejidad temporal: $\mathcal{O}(\max(x_i)\log(\max(x_i)))$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_VAL = 1e6;
 
// occ_num[i] contiene el número de veces que i aparece en el arreglo
vector<int> occ_num(MAX_VAL + 1);
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		occ_num[x]++;
	}
 
	// recorremos todos los gcd posibles
	for (int gcd = MAX_VAL; gcd > 0; gcd--) {
		// ver cuántos números del arreglo tienen este número como divisor
		int div = 0;
		for (int j = gcd; j <= MAX_VAL; j += gcd) { div += occ_num[j]; }
		if (div >= 2) {
			cout << gcd << endl;
			break;
		}
	}
}


import java.io.*;
import java.util.*;
 
public class CommonDivisors {
	public static final int MAXX = 1000000;
 
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader io = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(io.readLine());
		int[] arr = Arrays.stream(io.readLine().split(" "))
		                .mapToInt(Integer::parseInt)
		                .toArray();
 
		int[] p = new int[MAXX + 1];
		Arrays.fill(p, 0);
 
		for (int i = 0; i < n; i++) { p[arr[i]]++; }
 
		for (int i = MAXX; i >= 1; i--) {
			int div = 0;
			for (int j = i; j <= MAXX; j += i) { div += p[j]; }
			if (div >= 2) {
				System.out.println(i);
				break;
			}
		}
	}
}


MAXX = int(1e6 + 5)
n = int(input())
arr = list(map(int, input().split()))
p = [0] * MAXX
 
for i in range(n):
	p[arr[i]] += 1
 
for i in range(MAXX, 0, -1):
	div = 0
	for j in range(i, MAXX, i):
		div += p[j]
	if div >= 2:
		print(i)
		break