сделать более эффективным

Question

Я кодирования в hackerrank и наткнулся на эту проблему суммирования степенных рядов: https://www.hackerrank.com/challenges/power-calculation

Мой код работает для небольших файлов и больших чисел. Что касается больших файлов, время истекает. Может ли кто-нибудь сделать его более эффективным.

Мой код: данные

z = [] 
def modexp(a, n, m): 
    bits = [] 
    while n: 
     bits.append(n%2) 
     n /= 2 
    solution = 1 
    bits.reverse() 
    for x in bits: 
     solution = (solution*solution)%m 
     if x: 
      solution = (solution*a)%m 
    return solution 


for _ in xrange(int(input())): 
    while True: 
      try: 
        x = raw_input() 
        sum =0 
        z = x.split(' ') 
        power = int(z[1]) 
        limit = int(z[0]) 
        for i in range(0,limit+1): 
         sum = sum%100 + modexp(i%100,power, pow(10,2)) 
        if sum < 10: 
         print '%02d' % sum 
        if sum > 10: 
         print sum%100 
      except: 
       break 

Sample - вход: выход

10 
487348 808701 
204397 738749 
814036 784709 
713222 692670 
890568 452450 
686541 933150 
935447 202322 
559883 847002 
468195 111274 
833627 238704 

Пример:

76 
13 
76 
75 
24 
51 
20 
54 
90 
42 

Answer 1

можно легко уменьшить количество оценок мощности, заметив, что его значений mod 100 имеют период 100. Таким образом, разлагается K = M*100+L от co mputing M=K/100; L=K%100;.

Тогда

• для k=0 к L мощности modexp(k%100,N,100) происходит M+1 раз,
• для k=L+1 к 99 это происходит M раз в сумме.

Таким образом, каждая сумма мощности может быть уменьшена до 99 энергетических вычислений

---

можно уменьшить усилие, чтобы вычислить полномочия еще больше, заметив, что увеличение силы одного и того же числа являются периодическими в двух последних цифры. Как правило, последовательность

1, a % m, a**2 % m, a**3 % m, a**4 % m, ... 

Периодически после некоторой точки, которая задается наивысшей кратностью простого фактора. Одна длина периода задается значением m в функции пользователя Euler.

Значение всего 100=2²·5²: phi(100)=(2-1)·2·(5-1)·5=40. Смещение перед заходом периода в самое большее 2, то отсюда следует, что для всех целых a

a**2 % 100 == a**42 % 100 = a**82 % 100 = ... 
a**3 % 100 == a**43 % 100 = a**83 % 100 = ... 

и так далее.

Это означает, что для N>41 можно уменьшить показатель до N=2+(N-2) % 40. (В самом деле, можно заменить 40 на 20, что восстановление.)

---

И как последнее замечание, что не будет иметь большого влияния на время выполнения операций, только на сложности кода:

Существует короче способ реализации modexp, этот алгоритм также является стандартным упражнением определить инварианты цикла:

def modexp(a, n, m): 
    solution = 1 
    apower = a 
    while n: 
     if (n%2): solution = (solution*apower) % m 
     n /= 2 
     apower = (apower*apower) % m 
    return solution