Orac & LCM

Solución: factorización prima

Para cada primo, el segundo menor exponente del primo que aparece en alguno de los números de la entrada es el exponente de este primo que aparecerá en la respuesta final.

¡Aquí hay una solución corta que logra esto sin calcular explícitamente ninguna factorización prima!

Implementación

Complejidad temporal: $\mathcal{O}(n \log x)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
ll a, b;
// a stores minimum exponents (gcd of all numbers seen so far)
// b stores second minimum exponents
int n;
 
void red() {  // restore invariant mentioned above
	ll g = __gcd(a, b);
	tie(a, b) = make_pair(g, a / g * b);  // a/g*b = lcm(a,b)
}
 
int main() {
	cin >> n >> a >> b;
	red();
	for (int i = 2; i < n; i++) {
		ll x;
		cin >> x;
		b = __gcd(b, x);
		red();
	}
	cout << b << endl;
}


import java.io.*;
import java.util.*;
 
public class oraclcm {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] nums = new int[N];
 
		for (int i = 0; i < N; i++) { nums[i] = Integer.parseInt(st.nextToken()); }
 
		long gcd = gcd(nums[0], nums[1]);
		long ret = nums[0] / gcd * nums[1];
		for (int i = 2; i < N; gcd = gcd(gcd, nums[i]), i++) {
			ret = gcd(ret, lcm(nums[i], gcd));
		}
		System.out.println(ret);
	}
 
	static long lcm(long a, long b) { return a / gcd(a, b) * b; }
 
	static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
}


import math
 
"""
    a stores minimum exponents (gcd of all numbers seen so far)
    b stores second minimum exponents
"""
 
 
def red():  # restore invariant mentioned above
	global a, b
	g = math.gcd(a, b)
	a, b = g, a // g * b  # a / g * b = lcm(a, b)
 
 
n = int(input())
arr = list(map(int, input().split()))
a, b = arr[0], arr[1]
red()
 
for i in range(2, n):
	b = math.gcd(b, arr[i])
	red()
 
print(b)

Si es difícil entender qué hace exactamente este código a primera vista, un buen primer paso es simular el código en el caso en que cada $a_i$ es una potencia del mismo primo (digamos, $2^k$ ). Si el algoritmo funciona para este caso, entonces también funcionará en el caso general, ya que las contribuciones de distintos primos se calculan de forma independiente y se multiplican.

Otra forma de pensar esto:

Para un $j$ fijo,

\gcd_{0\le i<j}\left[\text{lcm}(a_i,a_j)\right]=\text{lcm}(a_j,\gcd_{0\le i<j}(a_i)),

y podemos actualizar $\gcd_{0\le i<j}(a_i)$ cuando $j$ aumenta en uno. Tomar el GCD de los resultados para cada $j$ da la respuesta.