Problema FINAL ANPA 08. Pirámides Limogochianas
Hola a todos!
Les presentamos uno de los problemas de la final del Abierto Nacional de Programación Ants 2008. Agradecemos a Darkmars por su aportación.
Historia
Como todos sabemos, los limogochis construyen pirámides meramente por ociosidad. Una pirámide limogochiana, es una pared de ladrillos de ancho uno y base l, los siguientes niveles se construyen poniendo un ladrillo entre cada ladrillo del nivel anterior. Por razones estéticas les impar.
Como la construcción no es totalmente inútil (podría ser que el muro sirviera para algún propósito inesperado), los limogochis se dan a la tarea de numerar cada ladrillo. Primero, numeran los ladrillos de la base del 1 a l (afortunadamente , en orden creciente). Cada ladrillo, de un nivel superior a la base, es marcado con la suma de los ladrillos que se encuentran justo debajo del ladrillo en cuestión.
Problema
Dada l,determinar el valor residuo rque deja el número escrito en la punta de la pirámide al dividirse entre m.
Entrada
La primera línea tiene un único valor entero nque indica el numero de casos de prueba. Cada caso de prueba consta de una línea con dos enteros (separados por un espacio) 0 < l< 50,000 y 0< m< 65,536 respectivamente. Los casos de prueba están separados por una línea en blanco.
Salida
El archivo consta de n líneas, cada línea con un único valor entero r que representa el residuo que deja el número de la punta de la pirámide limogochiana entre el número m.
