3304 - Super Pow

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?pid=3304

[isaac]

La idea es precalcular los factoriales hasta 10^6 y luego exponenciacion modular.

[ypizarroza]

Me parece admin que se deben revisar los juego de datos de este problema. Por aunque lo resolvi no creo que sea esa la solucion. Para resolver este tipo de problemas hay que aplicar los teoremas o bien de Fermat o Euler y no se esta teniendo en cuenta esto.

[isaac]

Brow no veo por ningun lado la utilizacion del teorema de Fermat. Este por lo general se utiliza para buscar el inverso multiplicativo, cosa que no hay que hacer en este problema porque en ningun momento hay que dividir. Es solamente potencia y mas potencia, todo moduleado.

[ypizarroza]

Si pero para resolver A^B mod M hay q aplicar esto A^phi(M) es congruente con 1 mod M. Y en la solucion usaste para generar los JD no lo tuviste en cuenta. A^B % M no es igual a (A%M)^(B%M) % M.

[humbertodiaz]

Saludos a todos. Puedo confirmar que los datos deben estar mal. Yosvany, me da mucha curiosidad sobre como supiste intentar esa solucion. Al menos ahora se por que el ejercicio parecia requerir alguna tecnica imposible. Calcular (A! ^ B!) mod P se puede hacer con el pequeño teorema de Fermat, pero añadir otro exponente factorial se vuelve problematico.

El problema se podria arreglar removiendo el factorial del ultimo exponente. Es decir, si se cambia la expresion que se debe calcular a (A! ^ (B! ^ C)) mod P.

[isaac]

OK, tienen toda la razon, gracias por hacermelo saber. Un error de mi parte. La unica solucion que le veo por el momento es desactivar el problema del problemset.

[humbertodiaz]

El ejercicio todavia sigue activo. Creo que deberiamos arreglarlo y rejuzgar todos los envios, por que no seria justo que algunas personas mantengan los puntos del ejercicio mientras esta sellado eternamente. Originalmente pense que el ejercicio no tiene una solucion eficiente. Sin embargo, encontre un algoritmo que debe funcionar. Tengo que implementarlo y probarlo para asegurar que no se me haya escapado algun detalle. Con eso se podrian crear datos nuevos para el ejercicio.

Edit: Ya complete una solucion correcta. La verifique con otra solucion mas lenta pero confiable. Tengo datos para reemplazar las pruebas incorrectas, pero la cantidad maxima de casos tendria que ser 10^5 (en vez de 10^3) para asegurar que se hagan suficientes pruebas.

[ymondelo20]

Hola Humberto,

Si les parece, me puedes enviar los nuevos juegos de datos para actualizarlo... y especificar los cambios que lleva el enunciado.

Saludos.

[ymondelo20]

Disculpas por la demora, es que son muchas cosas
Ya he actualizado los JD, con las versiones enviadas por Humberto.
Los envíos serán rejuzgados en los siguientes minutos; Humberto puedes probar tú mismo la solución correcta.

Saludos.