Skip to Content
CTRL K

Maximum of GCDs

Pista 1

¿Podemos acotar superiormente la cantidad de veces que cambia el GCD al extender un único subarreglo?

Respuesta a la pista 1

Nótese que el GCD solo puede disminuir a medida que agregamos más elementos, y siempre quitará algún factor del GCD actual. El menor factor que podemos quitar es 22, y ai≤109a_i \leq 10^9, así que el GCD solo puede cambiar a lo sumo log2(109)≈30log_2(10^9) \approx 30 veces.

Solución

Explicación

Como sabemos que cuanto más grande es el subarreglo, el GCD nunca aumenta, podemos crear una lista de tablas hash (hashmaps) donde \texttt{max\\_size}_{i, \text{gcd}} = el tamaño máximo del subarreglo que termina en ii con GCD gcd\text{gcd}.

Luego, podemos hacer actualizaciones en tiempo O(log⁡N)\mathcal{O}(\log N) extendiendo los subarreglos que terminaban en el índice i−1i - 1 hasta el índice ii.

La respuesta para longitud len\texttt{len} será el máximo gcd\text{gcd} para el cual \texttt{max\\_size}_{i, \text{gcd}} = \texttt{len}

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N\log N)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		cin >> n;
 
		// max_size[i][gcd] = max size of subarray ending at i with GCD gcd
		vector<map<int, int>> max_size(n);
		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			max_size[i][a[i]] = 1;
		}
 
		for (int i = 1; i < n; i++) {
			// extend subarrays
			for (auto [gcd, size] : max_size[i - 1]) {
				int new_gcd = __gcd(gcd, a[i]);
				max_size[i][new_gcd] = max(max_size[i][new_gcd], size + 1);
			}
		}
 
		vector<int> ans(n + 1);
		for (int i = 0; i < n; i++) {
			for (auto [gcd, size] : max_size[i]) { ans[size] = max(ans[size], gcd); }
		}
 
		for (int i = 1; i <= n; i++) { cout << ans[i] << (i == n ? "\n" : " "); }
	}
}
import math
from collections import defaultdict
 
for _ in range(int(input())):
	n = int(input())
 
	# max_size[i][gcd] = max size of subarray ending at i with GCD gcd
	max_size = [defaultdict(int) for _ in range(n)]
	a = list(map(int, input().split()))
 
	for i in range(n):
		max_size[i][a[i]] = 1
 
	for i in range(1, n):
		# extend subarrays
		for gcd, size in max_size[i - 1].items():
			new_gcd = math.gcd(gcd, a[i])
			max_size[i][new_gcd] = max(max_size[i][new_gcd], size + 1)
 
	ans = [0] * (n + 1)
	for i in range(n):
		for gcd, size in max_size[i].items():
			ans[size] = max(ans[size], gcd)
 
	for i in range(1, n + 1):
		print(ans[i], end=" " if i < n else "\n")
Fundamentos