| Problem D: NP |
| Time Limit: 2 seconds |
Afortunadamente, para muchos de los problemas computacionalmente tratables existen algoritmos cuya complejidad es de orden polinomial. Es decir, que para cualquier instancia del problema existe una cota superior c(n^k), donde c y k son constantes para cualquier instancia, y n es el tamaño de la instancia de la entrada al problema. A todo este conjunto se le conoce como la clase P. Un ejemplo son los algoritmos de ordenamiento.
Sin embargo, existe otra clase mucho más compleja, la NP donde están todos aquellos problemas que no existe un algoritmo polinomial para su solución. Un ejemplo clásico perteneciente a esta clase es el de 3-satisfactibilidad. Curiosamente todos los problemas que se encuentran en esta categoría son isomorfos uno de otros, lo cual implica que si en algún momento alguien encuentra un algoritmo polinomial para su solución, encontraría automáticamente el de todos los demás; además de ganarse más de $1,000,000 de dólares y los premios más distinguidos en nuestro planeta tierra como el Turing o el Nobel.
Demostrar que P = NP es un problema abierto en el campo de la teoría de la Computación. Hasta ahora nadie lo ha podido demostrar o siquiera contradecir.
Los algoritmos de la clase NP son de orden exponencial y otros aún más difíciles de orden factorial. Para el primero la cota superior de la forma c(k^n), mientras que para el segundo es c(n!), donde c y k son constantes y n es el tamaño de la instancia de problema.
Tu tarea aquí no será resolver un problema que pertenezca a la clase NP, mucho menos demostrar que P = NP. Simplemente dados n, c y k enteros positivos menores a 10^9, encuentra el último dígito que resulta de c(k^n).
La primera línea de entrada corresponde a un número entero nc que representa el número de casos a procesar. Le siguen nc casos, cada uno de ellas en una línea distinta con los enteros positivos n, c, k. Para más detalle véase los ejemplos de entrada y salida.
Por cada caso de entrada imprime el último dígito que resulta de c(k^n).
Sample input |
Sample output |
|---|---|
3 |
6 0 2 |