<p>You are given an integer array <code>nums</code>, and you can perform the following operation <strong>any</strong> number of times on <code>nums</code>:</p>

<ul>
	<li>Swap the positions of two elements <code>nums[i]</code> and <code>nums[j]</code> if <code>gcd(nums[i], nums[j]) &gt; 1</code> where <code>gcd(nums[i], nums[j])</code> is the <strong>greatest common divisor</strong> of <code>nums[i]</code> and <code>nums[j]</code>.</li>
</ul>

<p>Return <code>true</code> <em>if it is possible to sort </em><code>nums</code><em> in <strong>non-decreasing</strong> order using the above swap method, or </em><code>false</code><em> otherwise.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,21,3]
<strong>Output:</strong> true
<strong>Explanation:</strong> We can sort [7,21,3] by performing the following operations:
- Swap 7 and 21 because gcd(7,21) = 7. nums = [<u><strong>21</strong></u>,<u><strong>7</strong></u>,3]
- Swap 21 and 3 because gcd(21,3) = 3. nums = [<u><strong>3</strong></u>,7,<u><strong>21</strong></u>]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,6,2]
<strong>Output:</strong> false
<strong>Explanation:</strong> It is impossible to sort the array because 5 cannot be swapped with any other element.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,5,9,3,15]
<strong>Output:</strong> true
We can sort [10,5,9,3,15] by performing the following operations:
- Swap 10 and 15 because gcd(10,15) = 5. nums = [<u><strong>15</strong></u>,5,9,3,<u><strong>10</strong></u>]
- Swap 15 and 3 because gcd(15,3) = 3. nums = [<u><strong>3</strong></u>,5,9,<u><strong>15</strong></u>,10]
- Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,<u><strong>10</strong></u>,<u><strong>15</strong></u>]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>2 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def gcdSort(self, nums: List[int]) -> bool:
        # any number of times:
        #   swap i, j if nums[i], nums[j] have gcd > 1
        # return True iff we can sort in non-decreasing order

        # transitive?
        # if gcd(a, b) > 1 and gcd(b, c) > 1 then does gcd(a, c) > 1?
        #     a = 2, b = 6, c = 3 -> so NO
        
        # but groups can be transitively swapped if all members in the group share a prime factor

        # we can reorder groups probably if there are members that share a prime factor

        # such as a bunch of things divis by 3, like {powers of three} and {powers of 2} along with a 6
        #  we can put the 6 at the end, then swap anything at the end
        #
        # t1 t2 ... tk p1 p2 ... pk' 6
        # can do insertion sort: swap 6 with any, then swap 6 with adjacent so 6 bubbles back up to new end
        
        # HOKAY. So we want to know if the current largest can be swapped into position

        # if largest, M, and current end, x, share factors then yes
        
        # otherwise if there exists C | gcd(M,C) > 1 and gcd(x,C) > 1 then we can use C to facilitate the swap
        
        # otherwise is there a "swap chain" where we swap x with A, then A with B, then B with C, then C with M?
        # this swapping changes the primes at the end with another set that has some intersection
        # e.g. swap 2 with 6, then 6 with 15, then 15 with 35, etc. so that if we have e.g. 2 at the end and
        #      31 is the largest remaining

        # ACTUALLY: this is a huge insight: if the max remaining is a prime, it has gcd == 1 with anything else so we
        # return false

        # for M, x
        # if we can form a swap chain that moves any C into the last position where C and X have gcd > 1 then we're golden
        #
        #    swap chain: start with primes of x
        #        find other primes, BFS, such that there exists gcd(x, y) > 1 and prime1 | x and prime2 | y
        #        that means we can move prime2 into the last position
        #        keep going until we find a prime of M

        # neat... but also too complicated??

        # [5 2 10 2] -> [10 2 5 2] -> [2 2 5 10]   done

        # so is this really just a question if all the numbers are reachable from each other?
        # aka find all groups where the numbers can reach each other, we can sort them and put them in place
        # if we find any violations of the sorting criteria then return False

        # if gcd(a, b) > 1 and gcd(b, c) > 1 and gcd(c, d) > 1
        #
        # we can swap a, b    and b, c     and c,  d
        #   a b c d
        #
        #   can we move a past b, c:
        #       past b, yes
        #   b a c d
        #    can we move a past c? only if gcd(a, c) > 1

        # but we don't need to swap adj

        ##### let's get back to the swap chain idea
        # swap x with A, then A with B, ...., eventually the last intermediate with M
        # that means we need to find gcd(x,A) > 1 and gcd(A, B) > 1 ... gcd(lastIntermediate, M) > 1
        

        # transitive: if we can swap a with b, b with c, c with d then we can eventually swap a with d

        #### what I'm missing: the theory of sorting if we can only swap certain values with each other
        # if there are multiple sorting chains like that, does one give us an answer while the other does not?


        # if we moved M into position, M was at the END of the sorting chain
        # so x, A, B, C, .. last are still a chain
        



        # let's get back to an earlier insight: that if there's even one number common to a bunch we can get an arb. perm
        # so we can permute all the divis-by-twos
        # and permute all the divis-by-threes

        # if there's even one number divisible by 2 and 3 i.e. 6
        # then all of those can be mutually permuted

        # but what if there's a bunch divis by 2, ONE of the 2s is divis by 3 as well (e.g. 6)
        # and there's a bunch of divis by fives
        # and ONE divis by 15

        # such that we have t1 ... tm     and    f1....fn      and gcd(ti, fj) > 1
        #  can we arbitrarily order t1...tm f1..fn?
        #      if perm is done already, yes
        #      otherwise some t1...tm needs to be in a fn slot
        #      so swap we have ...t....ti... f1....f...fj...
        #                      ...t....ti... f1....fj..f....    # can permute f values freely
        #  basically we can m  ...t....fj... f1....ti..f....    # can swap fj, ti by assertion
        #               if we moved ti to the end first, then fj gets swapped to just before f1
        # and thus we'd have ...t.....fj f1....ti..f.....
        #                    ...ti....fj f1....t...f.....
        # so if we start with any t1....tm and f1....fm
        #      and any one of those can be swapped
        #      then we can
        #          > permute the t1..tm to be sorted
        #          > permute the f1..fn to be sorted
        #     then with the common ti,tj we showed how we can do a complicated
        #     swap sequence that moves a ti anywhere among the f1..fn sequence
        #            > move the ti we need to the end, the fj to where it should go
        #            > swap ti with fj so fj is part of the "remaining block of {f}" and t to move with ti
        #            > then permute the remaining {t} and {f}
        # At the end the swappable ti, fj will be at some arb position though, well I guess at the front
        # this isn't too bad though, let's say the sorted order has some pattern like
        #
        #         t t f t f f f t t f t f f f t f
        # what we just showed is that we can swap the t, f values to get any pattern
        # then we can sort among the pattern
        # what if we had {t} and {f} and there's a swap chain from ONE t to ONE f via others?
        #  e.g. t* A B C D E F G f*
        #       t* A B C D E F f* G
        #       t* A B C D E G f* F
        #       t* A B C D F G f* E
        #       t* A B C E F G f* D
        #       ..
        #       t* B C D E F G f* A
        #       A B C D E F G f* t*     # therefore the swap chain cyclically permutes positions
        #
        # so for any swap chain we can cyclically permute it... DUH okay that's pretty straighforward actually
        # so we can "rotate the ring" of values to put any one of them last
        # and thus as long as any chain exists among the remaining numbers from max to the end then we're good to go
        #
        # the value that has to move is known, it's whatever is currently in the way at that position
        # the value that has to get moved there is also known
        # so in that sense there's no ambiguity and thus "only one way"
        #    there may be many actual indices, but the only important part is that the intermediate indices are all
        #    still around at the end
        #
        # wait....
        #   so we can form "rings" of numbers we can permute
        #   above we had t* A ... f* and could permute so we had A...f* t*
        #    then A looks a lot like the old t*; we can do B...f* A t*
        #
        # if we can move any member of a chain to the end, then we can use the chain to move any earlier chain element to the end

        # therefore for any t*, if it's swappable with A, B, ... and any of those can reach the end, then t* can be put at the end

        # [15 5 9 3 10]
        #            2
        #  3    3 3
        #  5  5      5

        #  2 5 9 3 10
        #  2 5 3 9 10  > no ability to permute 3s and 5s, can't do it
        #
        #  15 9 3 81 28 4 2 35 49
        #   3 3 3  3
        #   5               5
        #                   7  7
        #
        #                   49 35
        #
        # final insight??
        #    with the whole t, f stuff
        #    we can get any permutation of t, f if there's even one number in common
        #       then we can use t perms to get any permutation of of s (divis by seven) values if there's another t divis by 7
        # because t, s with 7 | t means we can order t and s with respect to each other
        # so we can start with t, f, s
        # arb. permute t and s so we get the right permutation of {t|s} {f}
        #  then disentangle the {t|s} later

        # so FINALLY this is a sketch proof, I think, that we can get connected components by distinct prime factors
        # then we can sort within these factor clusters
        # and then iterate from back to front
        #   take the original position to its factor cluster; we know we can get any permutation of its cluster
        #   so put the largest one into position and pop from the sorted values for that factor cluster
        
        def distinctPrimes(n: int) -> list[int]:
            primes = []
            r = n
            for d in chain([2], range(3, int(sqrt(n))+1, 2)):
                if r % d == 0:
                    primes.append(d)
                    r //= d
                    while r % d == 0: r //= d
                    if r == 1: break
            else:
                primes.append(r) # didn't break --> r > 1 --> r is the last prime, the only greater than sqrt(n)

            return primes

        parent = defaultdict(lambda: -1)
        
        def find(p: int) -> int:
            if parent[p] < 0: return p

            parent[p] = find(parent[p])
            return parent[p]

        def union(p1: int, p2: int) -> None:
            p1 = find(p1)
            p2 = find(p2)

            if p1 == p2: return

            # union by rank
            if parent[p2] < parent[p1]: p1, p2 = p2, p1

            parent[p1] += parent[p2]
            parent[p2] = p1

        # union the factor groups
        for n in nums:
            for p1, p2 in pairwise(distinctPrimes(n)):
                union(p1, p2)

        # group by factor groups
        groups = defaultdict(list)
        roots = [0]*len(nums)
        for i, n in enumerate(nums):
            for p in distinctPrimes(n):
                r = find(p)
                groups[r].append(n)
                roots[i] = r
                break # just need first distinct, TODO can make this faster by getting just the first prime factor

        for vals in groups.values(): vals.sort()

        nxt = math.inf
        for i in range(len(nums)-1, -1, -1):
            # next position to sort is position i
            # i belongs to the factor group with root r
            # so if placing the largest of r into position keeps the array sorted then good
            # otherwise we have a violation and we can't sort
            r = roots[i]
            v = groups[r].pop()
            if v > nxt: return False # should have put v later, but we couldn't -> can't sort
            nxt = v

        return True
2550