Page 1 of 2

3304 - Super Pow

Posted: Sun Jun 21, 2015 4:29 pm
by ymondelo20

Re: 3304 - Super Pow

Posted: Tue Nov 17, 2015 12:04 pm
by isaac
La idea es precalcular los factoriales hasta 10^6 y luego exponenciacion modular.

Re: 3304 - Super Pow

Posted: Tue Dec 01, 2015 9:03 pm
by 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.

Re: 3304 - Super Pow

Posted: Thu Dec 03, 2015 6:09 pm
by 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.

Re: 3304 - Super Pow

Posted: Fri Dec 04, 2015 1:58 pm
by 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.

Re: 3304 - Super Pow

Posted: Sat Dec 05, 2015 12:44 am
by 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.

Re: 3304 - Super Pow

Posted: Mon Dec 07, 2015 1:46 am
by 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.

Re: 3304 - Super Pow

Posted: Sat Jan 09, 2016 8:32 pm
by 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.

Re: 3304 - Super Pow

Posted: Mon Jan 11, 2016 2:20 pm
by 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.

Re: 3304 - Super Pow

Posted: Thu Feb 25, 2016 1:22 pm
by ymondelo20
Disculpas por la demora, es que son muchas cosas :D
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.