Problema número 262

Ada, Babbage y Bernouilli

Tiempo máximo: 2,000 sMemoria máxima: 4096 KiB
Ada, Babbage y Bernouilli

En 1815 nacía Ada Byron, conocida después como Ada Lovelace, quién estaba destinada a convertirse en la primera programadora de la historia. Amiga de Charles Babbage, siguió con interés los trabajos de éste relacionados con su máquina analítica, que hoy se considera un hito en la historia de la computación.

Con la ayuda de Babbage, estudió y mejoró algunas de sus ideas, centrándose en lo que hoy llamaríamos software, mientras que Babbage se preocupaba principalmente por el hardware. Fue Ada quien describió el primer algoritmo pensado específicamente para ser ejecutado por un "ordenador", por lo que se la reconoce como la primera programadora.

El algoritmo estaba dedicado a calcular los números de Bernouilli y la propia Ada fue consciente de la necesidad de bifurcación de la máquina analítica. Expresado en términos modernos, el primer algoritmo necesitaba condiciones y bucles.

Los números de Bernouilli son una secuencia de números racionales que tienen conexiones muy interesantes con teoría de números. Su cálculo es complejo, por lo que a pesar de que han pasado muchos años desde que Ada "programó" cómo obtenerlos, nos conformaremos con uno de sus usos, el cálculo de la fórmula de Faulhaber, o suma de los n primeros números elevados a un valor constante p:

1p + 2p + 3p + …  + np

Entrada

El programa leerá de la entrada estándar múltiples casos de prueba, cada uno en una línea. Un caso de prueba se compondrá de dos números, n y p, entre 1 y 100 ambos incluídos.

La entrada terminará cuando n = p = 0.

Salida

Por cada caso de prueba, el programa escribirá el resultado de la expresión anterior, es decir la suma de los n primeros números naturales elevados a p. Dado que el resultado puede ser muy alto, se dará módulo 46.337*.

Entrada de ejemplo

1 1
2 2
3 3
4 3
100 100
0 0

Salida de ejemplo

1
5
36
100
17171
1 Ten cuidado con los desbordamientos en los cálculos intermedios; si a o b son muy grandes, la suma o la multiplicación podría ocasionar desbordamiento, y es preferible calcular el módulo primero para reducirlos. Recuerda que el módulo de la suma es igual al módulo de la suma de los módulos, y lo mismo ocurre con el producto:

(a + b) % k = ((a % k) + (b % k)) % k
(a × b) % k = ((a % k) × (b % k)) % k