Превышен лимит времени в SPOJ с использованием python

Question

Я пытаюсь решить эту проблему на SPOJ, https://www.spoj.com/problems/LASTDIG/, я уверен, что код правильный, но когда я отправляю его на сайт, он показывает, лимит времени превышен,

Код решения проблемы:

t=int(input()) #for test cases
for i in range(0,t):
         x,y=input().split() #for  two seperate input
         a=int(x)
         b=int(y)
         if 0<=a<=20 and 0<=b<=2147483000:   #conditions for  input
                 z=x**y
                 c=str(z)
                 print(c[-1]) #finally to print the last digit of the number

Я подозреваю, что программа слишком проста и требует времени для больших входов? Итак, может ли кто-нибудь предложить, как улучшить решение, или мне нужно выбрать другой язык, например C ++?

Answer 1

Это не python, из-за которого вы получаете TLE, это связано с подходом, который вы применяете для этого вопроса. Вы можете решить этот вопрос, используя метод под названием Двоичное возведение в степень . Прочтите об этом из здесь и попробуйте сами написать код решения. Если вы застряли, вы можете обратиться к моему решению:

# calculates (x ^ y) % m using binary exponentiation 
def binpow(x, y, m) :
    x = x % m
    ans = 1
    while y > 0 :
        if y % 2 == 1 :
            ans = (ans * x) % m
        x = (x * x) % m
        y = y >> 1
    return ans

for _ in range(int(input())) :
    a, b = map(int, input().split())
    print(binpow(a, b, 10))