El origen del ajedrez P65001

Según la leyenda que le contó Beremiz al califa de Bagdad, el ajedrez se debe a un joven brahmán, el cual lo inventó para distraer y alegrar a un rey. Como premio, el rey concedió un deseo al brahmán, el cual “solamente” pidió un grano de trigo por la primera casilla del tablero, dos granos por la segunda casilla, cuatro por la tercera, ocho por la cuarta, …, y así sucesivamente hasta la casilla número 64. El rey se rió al oir el deseo, y lo concedió inmediatamente. Después consultó cuánto trigo era con sus sabios matemáticos, los cuales llegaron a la conclusión de que era más del que podría producir la India entera en más de un siglo. El final de la leyenda cuenta que el brahmán liberó al rey de su promesa imposible de cumplir, y éste a cambio le nombró su primer ministro.

Entrada

La entrada consiste en diversos casos, cada uno con el número de casillas c de un juego, y un número deseado de granos de trigo g. Se cumple 2 ≤ c ≤ 10⁹ y 1 ≤ g ≤ 2⁶⁴ − 1.

Salida

Para cada caso, escribid una línea con la mínima x entera estrictamente positiva tal que si el brahmán pide 1 grano por la primera casilla, x granos por la segunda, x² granos por la tercera, x³ granos por la cuarta, etcétera, la suma total será por lo menos de g granos.

Observación

Se puede resolver este problema usando el tipo unsigned long long, si se vigilan los posibles desbordamientos antes de que se produzcan.