given a non-negative integer n, return a pair (a,b) such that n = a * a * b
        where b is a square-free integer.

        If n is a perfect square, then a is its square root and b is one.

def isqrt(n):
    ''' given a non-negative integer n, return a pair (a,b) such that n = a * a * b
        where b is a square-free integer.

        If n is a perfect square, then a is its square root and b is one.
    '''
    # TODO: replace with a more efficient implementation

    if n == 0:
        return n, 1
    if n < 0:
        raise ValueError('math domain error')

    a, b, c = 1, n, 1

    def divisors():
        yield 2
        yield 3
        k = 5
        while k * k <= b:
            yield k
            k += 2
            yield k
            k += 4
            
    for k in divisors():
        d, m = divmod(b, k * k)
        while m == 0:
            a *= k
            b = d
            d, m = divmod(b, k * k)
        if b % k == 0:
            b //= k
            c *= k

        k += 1
    return a, b*c