Número con menor factor primo

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 32M

Author:

FrankHG

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Encontrar el N-ésimo entero positivo más pequeño cuyo menor factor primo es $P$ ~P~, o declare que el resultado es mayor que $10^9$ ~10^9~.

Entrada

La primera y única línea de la entrada contiene los enteros $N$ ~N~ y $P$ ~P~ separados por espacio $(1 \le N, P \le 10^9)$ ~(1 \le N, P \le 10^9)~. $P$ ~P~ siempre será primo.

Salida

Imprimir una simple línea con el resultado esperado, o cero si el resultado excede a $10^9$ ~10^9~.

Ejemplo #1 de Entrada

1 2

Ejemplo #1 de Salida

Ejemplo #2 de Entrada

2 3

Ejemplo #2 de Salida

Ejemplo #3 de Entrada

1000 1000003

Ejemplo #3 de Salida

Comments

1

Osnielfc_07 commented on Jan. 17, 2021, 2:41 a.m. ← edited →

.

0

Osnielfc_07 commented on Jan. 17, 2021, 2:41 a.m. ← edit 3 →

*

0

josue commented on March 15, 2020, 10:53 p.m. ← edited →

lo q hice fue iterar por los múltiplos de p mayores o iguales q p^2,con un arreglo de primos revisaba hasta la raíz verificando q p fuera el menor primo q lo divide

0

josue commented on March 15, 2020, 9:54 p.m.

a mi lo único q se me ocurrió fue una fb optimization pero me dio AC

-4

Primervirgen commented on March 15, 2020, 10:10 p.m.

Podrías explicarla?

10

aniervs commented on March 15, 2020, 4:16 p.m. ← edit 3 →

A ver, originalmente el problema tenía como tiempo límite 10 segundos, supongo que fue un error, la solución esperada entra en un segundo. La idea es hacer dos soluciones, una cuando $P$ ~P~ es pequeño, y otra cuando $P$ ~P~ es grande. La solución cuando $P$ ~P~ es pequeño: podemos hacer búsqueda binaria a la respuesta: si $f(x)$ ~f(x)~ es la cantidad de números menores o iguales que $x$ ~x~ cuyos factores primos son mayores o iguales que $P$ ~P~, es obvio que $f$ ~f~ es no decreciente, por lo que podemos hacer búsqueda binaria para encontrar el primer $x: f(x) \ge N$ ~x: f(x) \ge N~; ahora, dado un $x$ ~x~, cómo computar $f(x)$ ~f(x)~, podemos restarle a $x$ ~x~ la cantidad de números que son múltiplos de algún primo menor que $P$ ~P~, y esta cantidad se puede calcular con principio de inclusión-exclusión con los primos menores que $P$ ~P~; si $\pi(x)$ ~\pi(x)~ es la cantidad de primos menores o iguales que $x$ ~x~, entonces podemos implementar esta idea en tiempo $O(2^{\pi(P)}\cdot \pi(P) + 2^{\pi(P)}\cdot \log \frac{10^9}{P})$ . Esta solución funciona en tiempo para $P \le 82$ ~P \le 82~, ya que $\pi(82) = 22$ ~\pi(82) = 22~. Ahora la otra solución es cuando $P > 82$ ~P > 82~. Primero notemos que queremos hallar un número de la forma $P\cdot x \le 10^9$ ~P\cdot x \le 10^9~, tal que el menor primo que divide a $x$ ~x~ es mayor o igual que $P$ ~P~; entonces $x \le \frac{10^9}{P}$ ~x \le \frac{10^9}{P}~, y por tanto $x \le \frac{10^9}{83} \rightarrow x < 1.25 \cdot 10^7$ ; entonces con una criba hasta $1.25 \cdot 10^7$ ~1.25 \cdot 10^7~ podemos computar el menor primo que divide a cada número, y luego iteramos por $x \in [1, \frac{10^9}{P}]$ ~x \in [1, \frac{10^9}{P}]~ y contamos cuáles no son divisibles por primos menores que $P$ ~P~, la complejidad en tiempo está dominada por cómo hacemos la criba, esta podemos hacerla en tiempo lineal, por lo que es $O(\frac{10^9}{P})$ ~O(\frac{10^9}{P})~. Lo que si creo que está muy restringida es la memoria límite, en mi solución tuve que hacer algunas optimizaciones en memoria, por lo demás todo bien.