题目链接

公因数排序

题目描述

一种新的排序方法规定，如果任意两个数 具有大于 1 的公因数（即 ），则它们可以交换位置。

给定一个数列，判断能否通过这种交换方法将其排为升序。

思路分析

这是一个典型的连通性问题，可以用并查集 (Disjoint Set Union, DSU) 来解决。

核心思想

“可以交换”定义了一种关系。如果数字 可以和 交换， 可以和 交换，那么 就属于同一个“连通块”或“等价类”。在这个块内的所有数字，都可以通过一系列交换，被移动到块内数字占据的任何一个初始位置上。

因此，问题可以转化为：对于原数组中的每一个数 ，它需要移动到的目标位置上的数（即排序后数组的 ），是否和它在同一个连通块内？ 如果对所有的 这个条件都成立，那么数组就可以被成功排序，否则就不能。

构建连通块

两个数可以交换的条件是它们的最大公因数 (GCD) 大于 1，这等价于它们共享至少一个大于 1 的质因数。

基于这个性质，我们可以构建连通关系：

  1. 一个数 和它的所有质因数 都是连通的。
  2. 如果数 和数 都拥有共同的质因数 ，那么 和 连通， 和 也连通。根据并查集的传递性， 和 也属于同一个连通块。

这启发我们使用并查集来维护这些连通关系。我们可以将每个数字和它的质因数看作并查集中的节点。对于数组中的每一个数 ，我们找到它的所有质因数 ，然后将 与这些质因数在并查集中合并（unite(x, p_1), unite(x, p_2), ...）。

算法步骤

  1. 预处理：为了快速分解质因数，我们可以使用线性筛（Sieve of Eratosthenes）预处理出 到 范围内所有数的最小质因数（Smallest Prime Factor, SPF）。这一步的时间复杂度大约是 。

  2. 构建并查集：

    • 对于输入的数组 中的每一个数 （）：
    • 利用预处理好的 SPF 数组，找到 的所有不同质因数 。
    • 将 和它的每一个质因数 在并查集中进行合并。

  3. 处理特殊值 0：

    • 数字 无法与任何数交换，因为它没有大于 1 的质因数。
    • 数字 比较特殊，。所以只要 ， 就可以和 交换。这意味着如果数组中存在 ，它将把所有大于 的数字所在的连通块全部合并成一个大的连通块。

  4. 检验：

    • 将原数组 复制并排序，得到目标数组 。
    • 遍历数组，比较 和 。如果对于任意的 ，find(a[i]) != find(b[i])，即它们不属于同一个连通块，那么排序无法完成，输出 No。
    • 如果遍历完成，所有对应元素都在同一个连通块内，则输出 Yes。

这个算法结合了数论和数据结构，能够高效地解决本题。

代码

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAX_VAL = 1000001;
int spf[MAX_VAL];
int parent[MAX_VAL];

void sieve() {
    iota(spf, spf + MAX_VAL, 0);
    for (int i = 2; i * i < MAX_VAL; ++i) {
        if (spf[i] == i) { // i is prime
            for (int j = i * i; j < MAX_VAL; j += i) {
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i] = a[i];
    }

    sort(b.begin(), b.end());

    iota(parent, parent + MAX_VAL, 0);

    for (int x : a) {
        if (x <= 1) continue;
        int temp = x;
        while (temp > 1) {
            int p = spf[temp];
            unite_sets(x, p);
            while (temp % p == 0) {
                temp /= p;
            }
        }
    }

    bool possible = true;
    for (int i = 0; i < n; ++i) {
        if (find_set(a[i]) != find_set(b[i])) {
            possible = false;
            break;
        }
    }

    if (possible) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    sieve();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
    private static final int MAX_VAL = 1000001;
    private static int[] spf = new int[MAX_VAL];
    private static int[] parent = new int[MAX_VAL];

    private static void sieve() {
        for (int i = 0; i < MAX_VAL; i++) {
            spf[i] = i;
        }
        for (int i = 2; i * i < MAX_VAL; i++) {
            if (spf[i] == i) { // i is prime
                for (int j = i * i; j < MAX_VAL; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
    }

    private static int findSet(int v) {
        if (v == parent[v]) {
            return v;
        }
        return parent[v] = findSet(parent[v]);
    }

    private static void uniteSets(int a, int b) {
        a = findSet(a);
        b = findSet(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            b[i] = a[i];
        }

        Arrays.sort(b);

        for (int i = 0; i < MAX_VAL; i++) {
            parent[i] = i;
        }

        for (int x : a) {
            if (x <= 1) continue;
            int temp = x;
            while (temp > 1) {
                int p = spf[temp];
                uniteSets(x, p);
                while (temp % p == 0) {
                    temp /= p;
                }
            }
        }

        boolean possible = true;
        for (int i = 0; i < n; i++) {
            if (findSet(a[i]) != findSet(b[i])) {
                possible = false;
                break;
            }
        }

        if (possible) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    public static void main(String[] args) {
        sieve();
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys

# It's better to use fast I/O in competitive programming
# but following user preference for standard input()
# def input(): return sys.stdin.readline().rstrip()

MAX_VAL = 1000001
spf = list(range(MAX_VAL))
parent = []

def sieve():
    global spf
    i = 2
    while i * i < MAX_VAL:
        if spf[i] == i:  # i is prime
            for j in range(i * i, MAX_VAL, i):
                if spf[j] == j:
                    spf[j] = i
        i += 1

def find_set(v):
    if v == parent[v]:
        return v
    parent[v] = find_set(parent[v])
    return parent[v]

def unite_sets(a, b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        parent[b] = a

def solve():
    global parent
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted(a)
    
    parent = list(range(MAX_VAL))

    for x in a:
        if x <= 1:
            continue
        temp = x
        while temp > 1:
            p = spf[temp]
            unite_sets(x, p)
            while temp % p == 0:
                temp //= p

    possible = True
    for i in range(n):
        if find_set(a[i]) != find_set(b[i]):
            possible = False
            break

    if possible:
        print("Yes")
    else:
        print("No")

def main():
    sieve()
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：线性筛 + 并查集

  • 时间复杂度：。

    • 线性筛预处理所有数的最小质因数，时间复杂度为 。
    • 对于每组测试数据，遍历数组 构建并查集。对每个数 进行质因数分解，复杂度为 。总共为 。
    • 最后的检验步骤，并查集的 find 操作近乎 ，总共为 。
    • 是测试数据组数， 是数组长度。

  • 空间复杂度：。

    • 需要一个数组 spf 来存储最小质因数，以及一个数组 parent 来维护并查集，大小都与数值上限 相关。