Exponentiation.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Rust, Scala, ~~Swift~~, VB, Zig

Tu tarea consiste en calcular eficientemente los valores $a^b$ ~a^b~ módulo $10^9+7$ ~10^9+7~.

Ten en cuenta que en esta tarea asumimos que $0^0=1$ ~0^0=1~.

La primera línea de entrada contiene un número entero $n$ ~n~: el número de cálculos.

Después hay $n$ ~n~ líneas, cada una de las cuales contiene dos enteros $a$ ~a~ y $b$ ~b~.

Imprime cada valor $a^b$ ~a^b~ módulo $10^9+7$ ~10^9+7~.

Restricciones

81
256
921450052

Comments

1

victoredel commented on July 16, 2025, 4:17 a.m.

Resolveremos esto de manera recusiva. Si queremos encontrar $a^x$ ~a^x~, podemos hacerlo dividiendo en $a^\frac{x}{2} \times a^\frac{x}{2}$ ~a^\frac{x}{2} \times a^\frac{x}{2}~ si $x$ ~x~ es par, o $a^\frac{x-1}{2} \times a^\frac{x-1}{2} \times a$ si $x$ ~x~ es impar. La complejidad es $O(nlog(max(b))$ ~O(nlog(max(b))~.