Last Digit of A ^ B

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 64M

Author:

leo

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, Swift, VB

Nestor is doing his math homework, a subject in which he has had many operations that did in the past three days and is very tired. The task is that given two numbers A and B are want to find the last digit of $A ^ B$ ~A ^ B~. You must help Nestor with this task. Will be given two numbers: the base $A (0 < A < 20)$ ~A (0 < A < 20)~ and the index $B (0 \le B \le 2147483000)$ ~B (0 \le B \le 2147483000)~. You will find the last digit of the result of $A ^ B$ ~A ^ B~.

Input specification

The first line of the entry contains a number T, the number of test cases. T lines follow. For each test case, a line with A and B separated by a space.

Output specification

For each test case should print a line with the result.

Sample input

2
3 10
6 2

Sample output

9
6

Comments

4

thegirlnextdoor commented on Sept. 13, 2023, 3:33 p.m. ← edited →

.

-3

PedroPabloAB commented on May 19, 2021, 4:51 p.m.

Con recursión es más fácil, pero consume mucha memoria. Debe existir alguna manera de optimizarlo en cuanto a esto.

9

PedroPabloAB commented on March 15, 2021, 2:57 a.m.

Waho. Aniervs, muchas gracias por tu ayuda.

2

PedroPabloAB commented on March 14, 2021, 12:48 a.m.

Pueden darme una pista acerca de cómo resolver este ejercicio.

26

aniervs commented on March 15, 2021, 12:13 a.m.

El problema se puede refrasear como calcular $a^b\ \% 10$ ~a^b\ \% 10~; eso es lo mismo que $(a \ \% 10)^b\ \% 10$ ~(a \ \% 10)^b\ \% 10~. Ahora que tenemos $a \in [0, 10)$ ~a \in [0, 10)~, fácilmente (con fuerza bruta o a lápiz y papel) podemos sacar el ciclo de las potencias de cada número menor que 10, y con eso puedes calcular cualquier potencia rápidamente, por ejemplo: si $a\ \% 10 = 2$ ~a\ \% 10 = 2~, entonces las potencias de $a$ ~a~ lucen: $1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6, 2, \dots$ , y así sucesivamente.

Por otro lado, puedes usar un algoritmo básico llamado potenciación rápida. Sabemos que: $\displaystyle a^{2n} = (a^2)^n$ $$\displaystyle a^{2n} = (a^2)^n$$ $\displaystyle a^{2n+1} = (a^2)^n\cdot a$ $\displaystyle a^0 = 1$ $$\displaystyle a^0 = 1$$

Con esa formulación recursiva puedes calcular $a^{n}$ ~a^{n}~ a partir de $a^{\left\lfloor\frac n 2\right\rfloor}$ ; por tanto luego de $O(\log_2 n)$ ~O(\log_2 n)~ pasos hallas el resultado. Tener en cuenta que las operaciones aritméticas deben ser realizadas módulo $10$ ~10~.