牛客网 ACM 竞赛 57300 F 题：构造矩阵满足最大公因数条件

题意简述

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

• 当 'i=1' 或 'i=n' 时，对于所有 '1 ≤ j ≤ n-1'，有 'gcd(A_{i,j},A_{i,j+1})=1'；
• 当 'j=1' 或 'j=n' 时，对于所有 '1 ≤ i ≤ n-1'，有 'gcd(A_{i,j},A_{i+1,j})=1'；
• 其他情况下，对于所有 '1 ≤ i,j ≤ 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 ≥ 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++ 代码示例