首页 > 试题广场 >

公因数排序

[编程题]公因数排序

一种新的排序方法规定，如果任意两个具有大于 $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无公因数，不可交换，因此不能排序成功。

算法知识视频讲解

阿萨大厦

谁能解释下。。

2 6 5 4 7

2和4换下位置为嘛就是24567了。。。？

发表于 2025-05-29 15:49:03 回复(1)

提交观点

数论并查集排序

上传者：turnsoul

难度：

1条回答 12收藏 200浏览

公因数排序

扫一扫，把题目装进口袋