小道具：正整数を累乗表現（底,指数）にする

入力値（正整数）が累乗数ならば底と指数を求めます。累乗数でなければ指数は $1$ とします。

入力値が大きいと、pow で累乗根を求めるときに float 型変換で失敗するため、int 型で求める処理を追加しています。（もっと良い法方があるかと思います）

# 平方根（Python 3.8 以上は組み込みを使用）
try:
    from math import isqrt

    def isqrtex(x: int) -> tuple:
        q = isqrt(x)
        return (q, x - q * q)

except:

    def isqrtex(x: int) -> tuple:
        l, r, s = x.bit_length() >> 1, 0, 0
        for b in range(l, -1, -1):
            r <<= 1
            t = 1 << b
            u = s + t
            v = u << b
            if x < v:
                continue
            x -= v
            r |= 1
            s = u + t
        return (r, x)

    def isqrt(x: int) -> int:
        return isqrtex(x)[0]


# float 型指数部の範囲
perfect_power_float_bits = 0
try:
    for b in range(8, 24):
        s = 1 << b
        float(1 << (s - 1))
        perfect_power_float_bits = s
except:
    pass

# 以下をコメントアウトすると float 型の処理をスキップします
# perfect_power_float_bits = -1   # float型を使わない


# 累乗数表現を求める
def perfect_power(x: int) -> tuple:
    x = abs(x)
    if x < 4:
        return (x, 1)

    # float 型が使用可能か？
    b = x.bit_length()
    if b <= perfect_power_float_bits:
        for e in range(b, 1, -1):
            m = int(x ** (1 / e))
            if x == (m ** e):
                return (m, e)
            m += 1
            if x == (m ** e):
                return (m, e)
        return (x, 1)

    # 指数 e に対する底を探す関数
    def find(x, e):
        s = 1 << (((x.bit_length() + e - 1) // e) - 1)
        n = 1
        while s > 1:
            m = n + s
            t = x - (m ** e)
            if t == 0:
                return (m, e)
            if t > 0:
                n = m
            s >>= 1
        return (x, 1)

    # float 型が使用できない場合
    w = 0
    if (x & 1) == 0:      # 偶数の冪乗か？
        # x = (2m)^e = 2^e m^e
        e = (x & -x).bit_length() - 1
        if e == 1:        # 奇数の 2 倍か？
            return (x, 1)
        m = x >> e
        if m == 1:        # 2 の冪乗か？
            return (2, e)
        x = m
        w = e

    # x = (m^e)^(s=2^k)
    s = 1
    while True:
        q, r = isqrtex(x)
        if r != 0:
            break
        s <<= 1
        x = q

    b = x.bit_length()
    z = b * 1024 // 1623  # Log2(3) ≒ 1.5849625
    for k in range((z | 1), 2, -2):
        m, e = find(x, k)
        if e != 1:
            x = m
            s *= e
            break

    if w == 0:
        return (x, s)
    if w == s:
        return (x << 1, s)

    u, v = w, s
    while v:
        u, v = v, u % v
    return ((1 << (w // u)) * (x ** (s // u)), u)

実行結果

>>> perfect_power(1)
(1, 1)
>>> perfect_power(2)
(2, 1)
>>> perfect_power(3)
(3, 1)
>>> perfect_power(4)
(2, 2)
>>> perfect_power(5)
(5, 1)
>>> perfect_power(6)
(6, 1)
>>> perfect_power(7)
(7, 1)
>>> perfect_power(8)
(2, 3)
>>> perfect_power(9)
(3, 2)
>>> perfect_power(26)
(26, 1)
>>> perfect_power(27)
(3, 3)
>>> perfect_power(28)
(28, 1)
>>> x = 123**321
>>> x
72367033806371673149109894141163778628811792657571658906010558390395870363798401744095280686155507736404921657070284961721828960592977909542637098897697223102622628566787654091327825453991595140205701412961364188732408936197890553699715836951569999800431957769217006743321026257517932764164662319487914962533302741368207211189494615326552790667720411285474162636765168907211924134973374304496019635376665858559941735703924836467756917247995469583487467791524582153744522107597865277798136080074161485280424274076931083994487111719562249702540362855712911132265966235754355353516703339043001506118520760359577737869472018617942120590873170710805078696371738906375721785723
>>> perfect_power(x)
(123, 321)