首页 > 试题广场 >

公因数排序

[编程题]公因数排序

一种新的排序方法规定，如果任意两个具有大于 $1$ 的公因数，则它们可以交换位置。想知道对于给定的数列 $a[i]$ ，能否通过该方法将其排为升序？

第一行一个正整数，表示测试数据组数；对于每组测试数据：
第一行一个正整数，表示数列中数字的个数；
第二行个整数，表示数列中的每个数字。

对于每组测试数据，如果可以排序成功，输出；如果不能，输出(均不包含引号)。

示例1

输入

1
5
2 6 5 4 7

Yes

4和6具有公因数2，可交换，交换后数列为2 4 5 6 7升序，排序成功。

示例2

1
4
1 3 2 4

No

升序为1 2 3 4，但2和3无公因数，不可交换，因此不能排序成功。

算法知识视频讲解

丨阿伟丨

发表于 2025-09-16 13:59:38

题目链接公因数排序题目描述一种新的排序方法规定，如果任意两个数具有大于 1 的公因数（即），则它们可以交换位置。给定一个数列，判断能否通过这种交换方法将其排为升序。思路分析这是一个典型的连通性问题，可以用并查集 (Disjoint Set Union, DSU) 来解决。核心思想展开全文

数论并查集排序

上传者：turnsoul

难度：

1条回答 12收藏 201浏览

公因数排序

扫一扫，把题目装进口袋