Pista 1: Una rama \(K\) es alcanzable si existe alguna rama inicial \(X\) con (2 \le X \le P) tal que (X \mid K).

En ese caso, el saltador que está en \(X\) puede saltar directamente a \(K\) porque \(K\) es un múltiplo de \(X\).

Pista 2: Para verificar si un número \(K\) tiene algún divisor \((\le P)\), basta revisar posibles divisores hasta \((\sqrt{K})\):

si \(K\) es compuesto, entonces tiene un divisor \((I \le \sqrt{K})\).
Por lo tanto, basta probar: \[ I = 2,3,\dots,\min\!\big(P,\lfloor \sqrt{K}\rfloor\big). \]

Solución

Se dan dos enteros \(P\) y \(Y\). Hay "saltadores" inicialmente en todas las ramas (2,3,\dots,P).
Desde una rama \(X\), un saltador puede saltar a cualquier múltiplo \((mX \le Y)\) con \((m \ge 2)\).
Se pide encontrar la rama más alta \(K\) con \((P < K \le Y)\) tal que ningún saltador pueda llegar a ella.
Si no existe, imprimir -1.

Criterio de seguridad

Una rama \(K\) es insegura si existe algún \(X\) en \(([2,P])\) tal que \((X \mid K)\).
Esto es suficiente porque el salto puede ser directo: al ser \(K\) múltiplo de \(X\), el saltador en \(X\) llega a \(K\) en un solo movimiento.

Por tanto: \[ K \text{ es segura } \iff \nexists\, X \in [2,P] \text{ tal que } X \mid K. \]

(Equivalente: \(K\) es segura si todos sus factores primos son \((> P)\).)

Búsqueda de la mejor rama

Como queremos la más alta, probamos candidatos de arriba hacia abajo:

• Para \((K = Y, Y-1, \dots, P+1)\):
  • Revisamos si existe algún divisor \[ I \in \{2,3,\dots,\min(P,\lfloor \sqrt{K}\rfloor)\} \] tal que \((K \bmod I = 0)\).
  • Si existe, entonces \((K)\) es insegura.
  • Si no existe ninguno, entonces \((K)\) es segura y esa es la respuesta (porque estamos bajando desde \(Y\)).

Si ningún candidato en \(((P,Y])\) resulta seguro, entonces la respuesta es -1.

Implementación (C++)

La_Rama_Imposible_de_Kobu.cpp

Complejidad

Para cada candidato \(K\) se prueban a lo más \((\min(P,\lfloor\sqrt{K}\rfloor))\) divisores.
Como \((K \le 10^9)\), se cumple \((\sqrt{K} \le 31623)\).

En el peor caso: \[ O\big((Y-P)\cdot \min(P,31623)\big) \] y la memoria es \((O(1))\).