思路

• 定义数的“平方因子核”函数：记 $\mathrm{sf}(x)$ 为 $x$ 的质因子中幂次为奇数的质因子相乘得到的数（即把所有平方因子剥去后得到的平方自由部分）。

• 关键性质：对任意正整数 $a,b$，有

  $a\cdot b \text{ 是完全平方数} \iff \mathrm{sf}(a)$ = $\mathrm{sf}(b).$

• 因此，将 $1\ldots n$ 按 $\mathrm{sf}(x)$ 相等分组。组内相邻两数乘积一定为平方数；不同组之间不可能为平方数。

• 若把每个组作为一个连续块并依次拼接，则代价为所有组内成功对数之和，即

  $\sum_{G} (|G|-1)$ = $n$ - $\#\{\text{不同的 } \mathrm{sf}(x)\}.$

  这是上界且可达，所以该构造最优。

• 实现：预处理最小质因子 SPF（到所有用例的最大 $n$），用它分解每个 $x$ 的质因子并计算 $\mathrm{sf}(x)$。按 $\mathrm{sf}(x)$ 排序并输出数值即可。

C++

#include <bits/stdc++.h>
using namespace std;

// 计算到 maxN 的最小质因子表
static vector<int> build_spf(int maxN) {
	vector<int> spf(maxN + 1);
	for (int i = 2; i <= maxN; ++i) {
		if (spf[i] == 0) {
			for (long long j = i; j <= maxN; j += i) {
				if (spf[j] == 0) spf[j] = i;
			}
		}
	}
	spf[0] = 0; spf[1] = 1;
	return spf;
}

// 计算平方因子核 sf(x)：质因子中幂为奇数者的乘积
static int squarefree_kernel(int x, const vector<int>& spf) {
	int res = 1;
	while (x > 1) {
		int p = spf[x];
		int parity = 0;
		while (x % p == 0) {
			x /= p;
			parity ^= 1; // 只关心奇偶
		}
		if (parity) res *= p;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	if (!(cin >> T)) return 0;
	vector<int> ns(T);
	int maxN = 0;
	for (int i = 0; i < T; ++i) {
		cin >> ns[i];
		maxN = max(maxN, ns[i]);
	}

	// 预处理 SPF
	vector<int> spf = build_spf(maxN);

	for (int tc = 0; tc < T; ++tc) {
		int n = ns[tc];
		vector<pair<int,int>> v;
		v.reserve(n);
		for (int i = 1; i <= n; ++i) {
			int k = squarefree_kernel(i, spf);
			v.emplace_back(k, i);
		}
		// 按平方因子核分组，组内顺序任意
		sort(v.begin(), v.end(), [](const auto& a, const auto& b){
			if (a.first != b.first) return a.first < b.first;
			return a.second < b.second; // 次序可选
		});
		for (int i = 0; i < n; ++i) {
			if (i) cout << ' ';
			cout << v[i].second;
		}
		cout << '\n';
	}
	return 0;
}

Python

import sys

# 构建到 maxN 的最小质因子表
def build_spf(maxN: int):
    spf = [0] * (maxN + 1)
    if maxN >= 1:
        spf[1] = 1
    for i in range(2, maxN + 1):
        if spf[i] == 0:
            for j in range(i, maxN + 1, i):
                if spf[j] == 0:
                    spf[j] = i
    return spf

# 计算平方因子核 sf(x)
def squarefree_kernel(x: int, spf):
    res = 1
    while x > 1:
        p = spf[x]
        parity = 0
        while x % p == 0:
            x //= p
            parity ^= 1
        if parity:
            res *= p
    return res

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    it = iter(data)
    T = next(it)
    ns = [next(it) for _ in range(T)]
    maxN = max(ns) if ns else 0
    spf = build_spf(maxN)

    out_lines = []
    for n in ns:
        pairs = []
        for i in range(1, n + 1):
            k = squarefree_kernel(i, spf)
            pairs.append((k, i))
        pairs.sort()  # 先按核再按数
        out_lines.append(' '.join(str(b) for _, b in pairs))
    sys.stdout.write('\n'.join(out_lines))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
	// 快速读入
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		int nextInt() throws IOException {
			int c, sgn = 1, x = 0;
			do { c = read(); } while (c <= 32);
			if (c == '-') { sgn = -1; c = read(); }
			for (; c > 32; c = read()) x = x * 10 + (c - '0');
			return x * sgn;
		}
	}

	// 构建到 maxN 的最小质因子表
	static int[] buildSpf(int maxN) {
		int[] spf = new int[maxN + 1];
		if (maxN >= 1) spf[1] = 1;
		for (int i = 2; i <= maxN; i++) {
			if (spf[i] == 0) {
				for (int j = i; j <= maxN; j += i) {
					if (spf[j] == 0) spf[j] = i;
				}
			}
		}
		return spf;
	}

	// 计算平方因子核 sf(x)
	static int squarefreeKernel(int x, int[] spf) {
		int res = 1;
		while (x > 1) {
			int p = spf[x];
			int parity = 0;
			while (x % p == 0) {
				x /= p;
				parity ^= 1;
			}
			if (parity == 1) res *= p;
		}
		return res;
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		int T = fs.nextInt();
		int[] ns = new int[T];
		int maxN = 0;
		for (int i = 0; i < T; i++) {
			ns[i] = fs.nextInt();
			if (ns[i] > maxN) maxN = ns[i];
		}
		int[] spf = buildSpf(maxN);
		StringBuilder out = new StringBuilder();
		for (int tc = 0; tc < T; tc++) {
			int n = ns[tc];
			int[][] arr = new int[n][2]; // [核, 值]
			for (int i = 1; i <= n; i++) {
				int k = squarefreeKernel(i, spf);
				arr[i - 1][0] = k;
				arr[i - 1][1] = i;
			}
			Arrays.sort(arr, (a, b) -> {
				if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
				return Integer.compare(a[1], b[1]);
			});
			for (int i = 0; i < n; i++) {
				if (i > 0) out.append(' ');
				out.append(arr[i][1]);
			}
			out.append('\n');
		}
		System.out.print(out.toString());
	}
}

题目内容

给定一个正整数 $n$ ，一个长度为 $n$ 的排列 $p$ 是由 {$1,2,...,n$} 这 $n$ 个整数按任意顺序组成的数组，其中每个整数恰好出现一次;

我们定义该排列的代价为满足 $p_i×p_{i+1}$ 是完全平方数的索引 $i$ 的个数 $(1 ≤i< n)$ ;

请你构造一个排列 $p$ ，使其代价最大。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦T≦ 10^4)$ ，表示测试用例数;

此后 $T$ 行，每行输入一个整数 $n(2≦n≦2×10^5)$，表示排列的长度;

此外，保证所有测试用例的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新起一行，输出一个长度为 $n$ 的排列 $p$ 为最大代价的排列。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

2
5
10

输出

2 3 1 4 5
10 7 6 1 4 9 2 8 3 5