Skip to Content
CTRL K

Div Game

Análisis oficial 

Explicación

Podemos factorizar NN en primos como N=p1e1⋅p2e2⋯pkekN = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}. Para lograr el máximo número de operaciones, para cada primo pip_i, debemos elegir primero z=pi1z = p_i^1, luego z=pi2z = p_i^2 y así sucesivamente.

A medida que factorizamos y hallamos el exponente de cada primo, podemos decrementar el exponente en 11, luego en 22, y así sucesivamente, mientras el exponente se mantenga no negativo. Cada vez que decrementamos el exponente, podemos sumar 11 a la respuesta.

Implementación

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

#include <iostream>
using namespace std;
 
int main() {
	long long n;
	cin >> n;
 
	int ans = 0;
	// factorizar n en primos
	for (long long p = 2; p * p <= n; p++) {
		int exponent = 0;
		while (n % p == 0) {
			exponent++;
			n /= p;
		}
		// decrementamos el exponente en i cada vez
		for (int i = 1; exponent - i >= 0; i++) {
			exponent -= i;
			ans++;
		}
	}
	if (n > 1) { ans++; }
 
	cout << ans << endl;
}
import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		long n = io.nextLong();
 
		int ans = 0;
		// factorizar n en primos
		for (long p = 2; p * p <= n; p++) {
			int exponent = 0;
			while (n % p == 0) {
				exponent++;
				n /= p;
			}
			// decrementamos el exponente en i cada vez
			for (int i = 1; exponent - i >= 0; i++) {
				exponent -= i;
				ans++;
			}
		}
		if (n > 1) { ans++; }
 
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
n = int(input())
 
ans = 0
# factorización prima de n
for p in range(2, int(n**0.5)):
	e = 0
	while n % p == 0:
		n /= p
		e += 1
	# aquí p^e divide a n
	i = 1
	# tomamos p^1 luego p^2 y así hasta que e < i
	while e >= i:
		e -= i
		ans += 1
		i += 1
 
ans += n > 1  # si n > 1 entonces es un factor primo con e = 1
 
print(ans)
Fundamentos