一道很好的构造题，受益匪浅。
链接：F-命运的抉择_2024牛客寒假算法基础集训营6 (nowcoder.com)
题意：
题解 （并查集 + 思维）：
首先将存在1的情况特判掉，我们的数组的元素都是>= 2的，我们发现所有的数字都是<= 1e6的所以我们可以根据筛法快速质因数分解，对于任意两个数
都满足一定存在相同的质因子, 我们依次处理一下数组中每一个数字的质因数，将它们的并查集数组初始化，然后再依次将每个数的质因数合并在一起，这样有交集的质因数就会全部合在一个位置上，然后我们取第一个数的其中一个质因数，拿到它的祖先，再去数组中遍历一遍，找到和同祖先的点我们就标记为Ture, 最后如果数量是n就是无解，否则就是有解。
代码：
#include <bits/stdc++.h>
#define ff first
#define ss second
// #define int long long
using namespace std;
using PII = pair<int, int>;
using ll = long long;
constexpr int N = 1e6 + 10, mod = 1e9 + 7;
constexpr int inf = 0x3f3f3f3f;
int n, m;
int a[N];
int q[N], cnt, p[N];
bool st[N], si[N];
int z[N];
int find(int x) {if(x != z[x]) z[x] = find(z[x]); return z[x];
}
void solve() {scanf("%d",&n);for(int i = 1; i <= n; i ++ ) { scanf("%d",&a[i]);if(a[i] < a[1]) swap(a[1], a[i]); }if(a[1] == 1) {printf("%d %d\n",1,n-1);cout << 1 << endl; for(int i = 2; i <= n; i ++ ) printf("%d ", a[i]);printf("\n"); return; }for(int i = 1; i <= n; i ++ ) {int x = a[i]; si[i] = 0; while(x > 1) {int t = p[x]; z[t] = t; while(x % t == 0) x /= t; }}for(int i = 1; i <= n; i ++ ) {int x = a[i]; int r = -1; while(x > 1) {int t = p[x];if(r == -1) r = t; else z[find(t)] = find(r); while(x % t == 0) x /= t; }}int x = a[1], aim; int t = p[x]; aim = find(t); for(int i = 1; i <= n; i ++ ) {int x = a[i];bool flag = 0; while(x > 1) {int t = p[x]; if(find(t) == aim) {flag = 1; break; }while(x % t == 0) x /= t; }if(flag) si[i] = 1; }cnt = 0; for(int i = 1; i <= n; i ++ ) if(si[i]) cnt++;if(cnt == n) puts("-1 -1");else {printf("%d %d\n", cnt, n - cnt); for(int i = 1; i <= n; i ++ ) if(si[i]) printf("%d ", a[i]); printf("\n"); for(int i = 1; i <= n; i ++ ) if(!si[i]) printf("%d ", a[i]); printf("\n"); }
}
signed main() {for(int i = 2; i <= 1e6; i ++ ) {if(!st[i]) q[cnt ++] = i, p[i] = i; for(int j = 0; q[j] <= 1e6 / i; j ++ ) {st[i * q[j]] = 1; p[i * q[j]] = q[j]; if(i % q[j] == 0) break; }}int ts = 1; scanf("%d",&ts); while(ts -- ) solve(); return 0;
}
