链接：httpsacnowcodercomacmcontest57300F来源：牛客网给你一个正整数 nn你需要构造一个 n times nn×n 的矩阵 AA第 ii 行第 jj 列用 A_ijA ij 表示对于所有的 A_ij1 le i j le nA ij 1≤ij≤n 满足：1 le A_ij le n1≤A ij ≤n且 1-n1−n 中的每个数恰好出现 nn 次。若 i =

题意简述

给定一个正整数 $n$，构造一个 $n \times n$ 的矩阵 $A$，使得 $A_{i,j}$ 取值在 $[1,n]$ 中，每个数恰好出现 $n$ 次，并且满足以下条件：

• 当 $i=1$ 或 $i=n$ 时，对于所有 $1 \leq j \leq n-1$，有 $\gcd(A_{i,j},A_{i,j+1})=1$；
• 当 $j=1$ 或 $j=n$ 时，对于所有 $1 \leq i \leq n-1$，有 $\gcd(A_{i,j},A_{i+1,j})=1$；
• 其他情况下，对于所有 $1 \leq i,j \leq n$，有 $\gcd(A_{i,j},A_{i,j+1})=1$，$\gcd(A_{i,j},A_{i,j-1})=1$，$\gcd(A_{i,j},A_{i+1,j})=1$，$\gcd(A_{i,j},A_{i-1,j})=1$。

思路分析

首先考虑 $n=1$ 的情况，此时只有一个格子，填入 $1$ 即可。

对于 $n \geq 2$，我们可以考虑将 $[1,n]$ 中的数分成两部分，一部分是所有质数，一部分是所有非质数。对于质数，我们将它们随机分配到矩阵的两条对角线上；对于非质数，我们将它们随机填入除了两条对角线以外的位置。

这样构造出来的矩阵显然符合每个数恰好出现 $n$ 次的条件，而且对于 $i=1$ 或 $i=n$ 的情况，两条对角线上的数都是质数，所以满足 $\gcd(A_{i,j},A_{i,j+1})=1$ 的条件；对于 $j=1$ 或 $j=n$ 的情况，对角线上的数都不会与其他数产生公因数，所以满足 $\gcd(A_{i,j},A_{i+1,j})=1$ 的条件；对于其他情况，对角线上的数都是质数，所以满足 $\gcd(A_{i,j},A_{i,j+1})=1$，$\gcd(A_{i,j},A_{i,j-1})=1$，$\gcd(A_{i,j},A_{i+1,j})=1$，$\gcd(A_{i,j},A_{i-1,j})=1$ 的条件。

时间复杂度分析

构造矩阵的时间复杂度为 $O(n)$，检验条件的时间复杂度为 $O(n^2)$，因此总时间复杂度为 $O(n^2)$。

参考代码

C++ 代