from math import *

# Square
def Sqr(a):
    return a * a

# Fill the table of powers for a^b <= 10^18, b >= 5 (5702 entries)
# The pow function is used to avoid overflow, but exact powers are stored
Powers= {}
a= 2
while pow(a, 5) <= 1.e18:
    a_b= a * Sqr(Sqr(a))
    b= 5
    while pow(a, b) <= 1.e18:
        Powers[a_b]= (a, b)
        a_b*= a
        b+= 1
    a+= 1

# Returns (a, b) such that a^b = n, or None
def IsPower(n):
    # Test small powers
    # For safety, floor(n^(1/b)) and floor(n^(1/b)) + 1 are tried
    a= int(floor(pow(n, 0.5)))
    if Sqr(a) == n:
        return (a, 2)
    a+= 1
    if Sqr(a) == n:
        return (a, 2)

    a= int(floor(pow(n, 1. / 3)))
    if a * Sqr(a) == n:
        return (a, 3)
    a+= 1
    if a * Sqr(a) == n:
        return (a, 3)

    a= int(floor(pow(n, 0.25)))
    if Sqr(Sqr(a)) == n:
        return (a, 4)
    a+= 1
    if Sqr(Sqr(a)) == n:
        return (a, 4)

    # Lookup large powers
    if n in Powers:
        return Powers[n]

print IsPower(125)
print IsPower(94143178827)
print IsPower(42)
print IsPower(6436343)

(5, 3)
(3, 23)
None
(23, 5)