You are viewing a single comment's thread. Return to all comments →
def gcd(a, b): while b != 0: t = b b = a % t a = t return a p, q = input().split() p = int(p) q = int(q) n = p*q phi = (p-1)*(q-1) bmin = -1 lis = set() for e in range(2, phi): mini = 0 if gcd(e, phi) != 1: continue for m in range(n): c = (m ** e)%n if c == m: mini += 1 if bmin != -1 and mini > bmin: break if bmin == -1 or bmin > mini: bmin = mini lis.clear() lis.add(e) elif bmin == mini: lis.add(e) print(sum(lis) % (10 ** 9 + 7))
Can someone explain where can the code be optimized? It gets a timeout on all but the 1st test case
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #182: RSA encryption
You are viewing a single comment's thread. Return to all comments →
Can someone explain where can the code be optimized? It gets a timeout on all but the 1st test case