Suma de los Factores Primos - TopCoder

Question

Recientemente en Topcoder, me enfrenté a un problema que declaró lo siguiente: "Usted tiene un documento de texto, con un solo personaje ya escrito en él. Se le permite realizar sólo dos de las operaciones de copiar todo el texto (cuentan como 1 paso), o pegar cualquier cosa que esté en el portapapeles (cuentan como 1 paso). Al pegar lo que hay en el portapapeles el texto original en el documento de texto se anexa con que en el portapapeles. Copia overrites lo que hay en el cliboard. Es necesario encontrar el mínimo número de pasos necesarios para imprimir 'n' caracteres en el documento de texto. Por Ejemplo, para generar 9 caracteres a Copiar el único personaje que ya presente, Pegar (2 caracteres), pegar (3 caracteres), copiar (3 caracteres copiados), pegar (6 caracteres), pegar (9 caracteres). Así, el número total de pasos requerido es de 6, que es (3+3 suma de los factores primos de 9).

Alguien puede decir, ¿cómo es este problema se relaciona a la suma de los factores primos de n'?

Gracias!

Answer 1

En cada paso, el número de caracteres copiados pegar a continuación, un número arbitrario de veces que tiene que ser un divisor de a $n$(porque no importa cuántas veces nos pegar a continuación, el importe que resulte de los personajes será un múltiplo del número de caracteres copiados). Así que vamos a $\xrightarrow{a}$ quiere decir que me copie los caracteres en el buffer y luego me pegarlos $a-1$ veces, multiplicando el número real de caracteres en el búfer $a$ $a$ pasos.

Así que vamos a decir que he aplicado este algoritmo: $$\xrightarrow{a_1}\xrightarrow{a_2}\xrightarrow{a_3}\cdots\xrightarrow{a_n}$$ Podemos notar que la $\xrightarrow{\,a}\xrightarrow{\,b}$ $\xrightarrow{ab}$ hacer la misma cosa. Está claro que si $a,b\ge2$,el primer algoritmo es mejor o equivalente, equivalente iff $a=b=2$. Si en realidad hay un $\xrightarrow{4\,}$, se puede reemplazar por un par de $\xrightarrow{2\,}$ sin cambiar de eficiencia o de resultado. Entonces, si alguna de las $a_i$ es factorizable, que el algoritmo no es el óptimo. Para cada algoritmo óptimo es equivalente a la que tiene todos los $a_i$ prime. Finalmente:

$$a_1+a_2+a_3+\cdots+a_n=\text{Sum of prime factors}$$