[Pregunta de programación] Juego de adivinanzas

Límite de tiempo: 1 segundo

Límite de espacio: 32768K

Esta pregunta es difícil.

Primero utilizamos la idea de programación dinámica

Primero analizamos que dp[i] representa el número legal del primer número i

Cuando el i -ésimo número es Cuando se trata de números primos, no hay nada divisible excepto 1, por lo que puedes elegir Y o N en esta posición, entonces dp[i] = dp[i-1]

Cuando el El i-ésimo número no es un número primo La potencia de, como 6 y 10, entonces su situación en realidad está determinada por el número anterior. Para 6, si 2 y 3 son YY, entonces 6 debe ser Y. En otros casos, 6 debe ser N, entonces dp[i] = dp[i-1]

Cuando el i-ésimo número es una potencia de un número primo, es decir, números como 2, 4, 8, y 16, la situación es complicada. Supongamos que ahora hay 2, 4 y 8. ¿Cuántas situaciones hay? Podemos descubrir las reglas mediante un análisis cuidadoso.

YYY, YNN, NNN, YYN son solo estas cuatro situaciones.

Para los tres casos de 2, 4

YN, YY y NN

Descubrimos que en realidad existen reglas: primero, pueden o no ser ambas, y luego de. de izquierda a derecha Agregue Y:

YNN, YYN.

Entonces, para esta situación, trazamos la regla de que si hay n potencias, hay n 1 situaciones factibles.

Después del análisis, podemos obtener el método de cálculo para 12:

Los tres números 2, 4 y 8 son potencias, y hay 4 posibilidades

<. p>Existen tres posibilidades para las potencias de los dos números 3 y 9

Existen dos posibilidades para el 5, 7 y 11 respectivamente

Los demás números están determinados por otros números

p>

Entonces el resultado final es 4 3 2 2 2

Entonces lo pensamos y finalmente se trata de encontrar el número de números primos y las potencias de los números primos.

?