GCD On Blackboard

Solución

El problema pide hallar el máximo GCD posible de los $N-1$ números restantes tras quitar cualquiera de ellos. Probar de forma naive cada combinación da una complejidad de $\mathcal{O}(N^2 + N \log(\max a_i))$ , pues hay $N$ formas distintas de quitar un número y calcular el GCD toma $\mathcal{O}(N+\log(\max a_i))$ por caso.

Para acelerar esto, podemos calcular los GCD de cada prefijo y sufijo. Sea $l[i] = \gcd_{j=1}^{i} a[j]$ y $r[i] = \gcd_{j=i}^{N} a[j]$ . Entonces la respuesta es el máximo de $\gcd(l[i-1],r[i+1]),$ $i \in [1,N]$ .

Complejidad temporal:

\mathcal{O}(N+\log(\max a_i))

Demostración de la complejidad temporal

A primera vista, podría pensarse que hallar el GCD de un arreglo de enteros toma $\mathcal{O}(N\log(\max a_i))$ porque cada operación de GCD toma a lo sumo $\mathcal{O}(\log(\max a_i))$ . Sin embargo, como cada operación de GCD disminuye el máximo de los dos operandos al menos por un factor de 2, solo puede haber un total de $\mathcal{O}(\log (\max a_i))$ operaciones de GCD en lugar de $\mathcal{O}(N \log(\max a_i))$ (el GCD más pequeño posible es 1 por definición). Por eso la complejidad temporal total de este problema es $\mathcal{O}(N+\log(\max a_i))$ como se indicó antes.

Opcional

Este blog de Codeforces discute la complejidad temporal de hallar el GCD de un arreglo.

Implementación

C++PythonJava


#include <bits/stdc++.h>
using namespace std;
 
const int maxN = 1e5 + 5;
 
int arr[maxN];
int prefGcd[maxN];  // prefGcd[i] = GCD de a1,a2, ..., ai
int suffGcd[maxN];  // suffGcd[i] = GCD de ai, ai+1, ..., an
int N;
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> arr[i];
 
	prefGcd[0] = 0;
	suffGcd[N + 1] = 0;
 
	for (int i = 1; i <= N; ++i) { prefGcd[i] = gcd(prefGcd[i - 1], arr[i]); }
 
	for (int i = N; i >= 1; --i) { suffGcd[i] = gcd(suffGcd[i + 1], arr[i]); }
 
	int res = 0;
	for (int i = 1; i <= N; ++i) {
		res = max(res, gcd(prefGcd[i - 1], suffGcd[i + 1]));
	}
	cout << res << '\n';
}


from math import gcd
 
n = int(input())
arr = list(map(int, input().split()))
 
ans = 0
 
prefix_gcd = [0] * n
prefix_gcd[0] = arr[0]
 
suffix_gcd = [0] * n
suffix_gcd[n - 1] = arr[n - 1]
 
# prefix_gcd[i] = GCD de a[0], a[1], ..., a[i]
for i in range(1, n):
	prefix_gcd[i] = gcd(prefix_gcd[i - 1], arr[i])
 
# suffix_gcd[i] = GCD de a[n - 1], a[n - 2], ..., a[i]
for i in range(n - 2, -1, -1):
	suffix_gcd[i] = gcd(suffix_gcd[i + 1], arr[i])
 
# Calculamos la respuesta si reemplazamos un elemento con índice entre 1 y n - 2
for i in range(1, n - 1):
	ans = max(ans, gcd(prefix_gcd[i - 1], suffix_gcd[i + 1]))
 
# Calculamos la respuesta si reemplazamos el primer elemento del arreglo
ans = max(ans, suffix_gcd[1])
# Calculamos la respuesta si reemplazamos el último elemento del arreglo
ans = max(ans, prefix_gcd[n - 2])
 
print(ans)


import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int[] a = new int[n];
 
		for (int i = 0; i < n; i++) { a[i] = io.nextInt(); }
 
		int[] prefGCD = new int[n + 1];
		int[] suffGCD = new int[n + 1];
		for (int i = 1; i <= n; i++) { prefGCD[i] = gcd(prefGCD[i - 1], a[i - 1]); }
		for (int i = n - 1; i >= 0; i--) { suffGCD[i] = gcd(suffGCD[i + 1], a[i]); }
 
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int g = gcd(suffGCD[i + 1], prefGCD[i]);
			ans = Math.max(ans, g);
		}
		System.out.println(ans);
		io.close();
	}
 
	static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
 
	// CodeSnip{Kattio}
}