def dup_deflate(f, K):
    """
    Map ``x**m`` to ``y`` in a polynomial in ``K[x]``.

    Examples
    ========

    >>> from sympy.polys.domains import ZZ
    >>> from sympy.polys.densebasic import dup_deflate

    >>> f = ZZ.map([1, 0, 0, 1, 0, 0, 1])

    >>> dup_deflate(f, ZZ)
    (3, [1, 1, 1])

    """
    if dup_degree(f) <= 0:
        return 1, f

    g = 0

    for i in range(len(f)):
        if not f[-i - 1]:
            continue

        g = igcd(g, i)

        if g == 1:
            return 1, f

    return g, f[::g]

def dmp_deflate(f, u, K):
    """Map `x_i**m_i` to `y_i` in a polynomial in `K[X]`. """
    if dmp_zero_p(f, u):
        return (1,)*(u+1), f

    F = dmp_to_dict(f, u)
    B = [0]*(u+1)

    for M in F.iterkeys():
        for i, m in enumerate(M):
            B[i] = igcd(B[i], m)

    for i, b in enumerate(B):
        if not b:
            B[i] = 1

    B = tuple(B)

    if all([ b == 1 for b in B ]):
        return B, f

    H = {}

    for A, coeff in F.iteritems():
        N = [ a // b for a, b in zip(A, B) ]
        H[tuple(N)] = coeff

    return B, dmp_from_dict(H, u, K)

def dmp_multi_deflate(polys, u, K):
    """
    Map ``x_i**m_i`` to ``y_i`` in a set of polynomials in ``K[X]``.

    Examples
    ========

    >>> from sympy.polys.domains import ZZ
    >>> from sympy.polys.densebasic import dmp_multi_deflate

    >>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]])
    >>> g = ZZ.map([[1, 0, 2], [], [3, 0, 4]])

    >>> dmp_multi_deflate((f, g), 1, ZZ)
    ((2, 1), ([[1, 0, 0, 2], [3, 0, 0, 4]], [[1, 0, 2], [3, 0, 4]]))

    """
    if not u:
        M, H = dup_multi_deflate(polys, K)
        return (M,), H

    F, B = [], [0]*(u + 1)

    for p in polys:
        f = dmp_to_dict(p, u)

        if not dmp_zero_p(p, u):
            for M in f.keys():
                for i, m in enumerate(M):
                    B[i] = igcd(B[i], m)

        F.append(f)

    for i, b in enumerate(B):
        if not b:
            B[i] = 1

    B = tuple(B)

    if all(b == 1 for b in B):
        return B, polys

    H = []

    for f in F:
        h = {}

        for A, coeff in f.items():
            N = [ a // b for a, b in zip(A, B) ]
            h[tuple(N)] = coeff

        H.append(dmp_from_dict(h, u, K))

    return B, tuple(H)

def dup_multi_deflate(polys, K):
    """Map `x**m` to `y` in a set of polynomials in `K[x]`. """
    G = 0

    for p in polys:
        if dup_degree(p) <= 0:
            return 1, polys

        g = 0

        for i in xrange(len(p)):
            if not p[-i-1]:
                continue

            g = igcd(g, i)

            if g == 1:
                return 1, polys

        G = igcd(G, g)

    return G, tuple([ p[::G] for p in polys ])

def dup_multi_deflate(polys, K):
    """
    Map ``x**m`` to ``y`` in a set of polynomials in ``K[x]``.

    Examples
    ========

    >>> from sympy.polys.domains import ZZ
    >>> from sympy.polys.densebasic import dup_multi_deflate

    >>> f = ZZ.map([1, 0, 2, 0, 3])
    >>> g = ZZ.map([4, 0, 0])

    >>> dup_multi_deflate((f, g), ZZ)
    (2, ([1, 2, 3], [4, 0]))

    """
    G = 0

    for p in polys:
        if dup_degree(p) <= 0:
            return 1, polys

        g = 0

        for i in range(len(p)):
            if not p[-i - 1]:
                continue

            g = igcd(g, i)

            if g == 1:
                return 1, polys

        G = igcd(G, g)

    return G, tuple([ p[::G] for p in polys ])

def dup_deflate(f, K):
    """Map `x**m` to `y` in a polynomial in `K[x]`. """
    if dup_degree(f) <= 0:
        return 1, f

    g = 0

    for i in xrange(len(f)):
        if not f[-i-1]:
            continue

        g = igcd(g, i)

        if g == 1:
            return 1, f

    return g, f[::g]

def dmp_deflate(f, u, K):
    """
    Map ``x_i**m_i`` to ``y_i`` in a polynomial in ``K[X]``.

    Examples
    ========

    >>> from sympy.polys.domains import ZZ
    >>> from sympy.polys.densebasic import dmp_deflate

    >>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]])

    >>> dmp_deflate(f, 1, ZZ)
    ((2, 3), [[1, 2], [3, 4]])

    """
    if dmp_zero_p(f, u):
        return (1,)*(u + 1), f

    F = dmp_to_dict(f, u)
    B = [0]*(u + 1)

    for M in F.keys():
        for i, m in enumerate(M):
            B[i] = igcd(B[i], m)

    for i, b in enumerate(B):
        if not b:
            B[i] = 1

    B = tuple(B)

    if all(b == 1 for b in B):
        return B, f

    H = {}

    for A, coeff in F.items():
        N = [ a // b for a, b in zip(A, B) ]
        H[tuple(N)] = coeff

    return B, dmp_from_dict(H, u, K)

 def update(k):
     # updates all of the info associated with k using
     # the com_dict: func_dicts, func_args, opt_subs
     # returns True if all values were updated, else None
     # SHARES com_dict, com_func, func_dicts, func_args,
     #        opt_subs, funcs, verbose
     for di in com_dict:
         # don't allow a sign to change
         if com_dict[di] > func_dicts[k][di]:
             return
     # remove it
     if Func is Add:
         take = min(func_dicts[k][i] for i in com_dict)
         com_func_take = Mul(take, from_dict(com_dict), evaluate=False)
     else:
         take = igcd(*[func_dicts[k][i] for i in com_dict])
         com_func_take = Pow(from_dict(com_dict), take, evaluate=False)
     for di in com_dict:
         func_dicts[k][di] -= take*com_dict[di]
     # compute the remaining expression
     rem = from_dict(func_dicts[k])
     # reject hollow change, e.g extracting x + 1 from x + 3
     if Func is Add and rem and rem.is_Integer and 1 in com_dict:
         return
     if verbose:
         print('\nfunc %s (%s) \ncontains %s \nas %s \nleaving %s' %
             (funcs[k], func_dicts[k], com_func, com_func_take, rem))
     # recompute the dict since some keys may now
     # have corresponding values of 0; one could
     # keep track of which ones went to zero but
     # this seems cleaner
     func_dicts[k] = as_dict(rem)
     # update associated info
     func_dicts[k][com_func] = take
     func_args[k] = set(func_dicts[k])
     # keep the constant separate from the remaining
     # part of the expression, e.g. 2*(a*b) rather than 2*a*b
     opt_subs[funcs[k]] = ufunc(rem, com_func_take)
     # everything was updated
     return True

def dmp_multi_deflate(polys, u, K):
    """Map `x_i**m_i` to `y_i` in a set of polynomials in `K[X]`. """
    if not u:
        M, H = dup_multi_deflate(polys, K)
        return (M,), H

    F, B = [], [0]*(u+1)

    for p in polys:
        f = dmp_to_dict(p, u)

        if not dmp_zero_p(p, u):
            for M in f.iterkeys():
                for i, m in enumerate(M):
                    B[i] = igcd(B[i], m)

        F.append(f)

    for i, b in enumerate(B):
        if not b:
            B[i] = 1

    B = tuple(B)

    if all([ b == 1 for b in B ]):
        return B, polys

    H = []

    for f in F:
        h = {}

        for A, coeff in f.iteritems():
            N = [ a // b for a, b in zip(A, B) ]
            h[tuple(N)] = coeff

        H.append(dmp_from_dict(h, u, K))

    return B, tuple(H)