Faire la somme plus efficace série de puissance

Question

Je suis codage en HackerRank et suis tombé sur ce problème: https://www.hackerrank.com/challenges/power-calculation

Mon code fonctionne pour les petits fichiers et grands nombres. En ce qui concerne les gros fichiers, ça expire. Quelqu'un pourrait-il le rendre plus efficace.

Mon code:

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 

échantillon de données - Entrée:

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

Exemple de sortie:

76 
13 
76 
75 
24 
51 
20 
54 
90 
42 

Answer 1

On peut facilement réduire le nombre d'évaluations de puissance en observant que ses valeurs Le mod 100 a une période de 100. Ainsi, se décompose K = M*100+L par co mputing M=K/100; L=K%100;.

Puis

• pour k=0-L la puissance modexp(k%100,N,100) se produit M+1 fois,
• pour k=L+1 à 99 il se produit M fois la somme.

Ainsi, chaque somme d'énergie peut être réduite à 99 calculs de puissance

---

On peut réduire l'effort de calculer les puissances encore plus en observant que les puissances croissantes du même nombre sont périodiques dans les deux dernières chiffres. Généralement, la séquence

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

devient périodique après un certain point qui est donné par la multiplicité la plus élevée d'un facteur premier. Une longueur de période est donnée par la valeur de m dans la fonction totalisante d'Euler. La valeur de base de 100=2²·5² est phi(100)=(2-1)·2·(5-1)·5=40. Le décalage avant que les jeux de période en est au plus 2, il en résulte que pour tous les entiers a

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

et ainsi de suite.

Cela signifie que pour N>41 on peut réduire l'exposant à N=2+(N-2) % 40. (En effet, on peut remplacer 40 par 20 dans cette réduction.)

---

Et comme dernière remarque qui ne sera pas avoir beaucoup d'impact sur les temps en cours d'exécution, que la complexité du code:

Il y a un chemin plus court pour mettre en œuvre modexp, cet algorithme est également un exercice standard pour identifier les invariants de boucle:

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