#P2963. 第1题-小红的矩阵
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 24
            Accepted: 11
            Difficulty: 3
            
          
          
          
                       所属公司 : 
                              阿里
                                
            
                        
              时间 :2025年5月17日-阿里淘天(算法岗)
                              
                      
          
 
- 
                        算法标签>构造          
 
第1题-小红的矩阵
题解
题面描述
给定一个整数 n(1≤n≤105),要求构造一个 2×n 的矩阵,使得:
- 每一行都是 [1,n] 的一个排列;
 - 对于任意两个相邻元素 ai1,j1 与 ai2,j2(满足 ∣i1−i2∣+∣j1−j2∣=1),都有 gcd(ai1,j1,ai2,j2)=1。
 
这样的矩阵称为“好矩阵”,保证答案总是存在。
思路
我们需要保证矩阵中任意水平或垂直相邻的两个数互质。可以利用以下性质:
- 连续两数互质:对于任意整数 k,都有 gcd(k,k+1)=1。
 - 首尾相接也互质:由于 gcd(1,n)=1 当且仅当 n=1 或 n 与 1 没有其他公约数,但 1 与任意 n 都互质。
 
因此,我们可以构造:

验证:
- 水平相邻:
- 第一行中,相邻的 k 与 k+1 互质;
 - 第二行同理;
 - 在第二行末尾,n 与 1 也互质。
 
 - 垂直相邻:
- 对于列 j(1≤j≤n−1),第一行的 j 为 j,第二行的 j 为 j+1,二者互质;
 - 对于第 n 列,第一行是 n,第二行是 1,互质。
 
 
该构造满足所有条件,且时间复杂度 O(n),空间复杂度 O(n)。
代码实现
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    
    // 特殊情况:n=1 时,矩阵唯一,1 与 1 互质
    if (n == 1) {
        cout << 1 << '\n';
        cout << 1 << '\n';
        return 0;
    }
    // 第一行:1, 2, ..., n
    for (int i = 1; i <= n; ++i) {
        cout << i;
        if (i < n) cout << ' ';
    }
    cout << '\n';
    // 第二行:2, 3, ..., n, 1
    for (int i = 2; i <= n; ++i) {
        cout << i << ' ';
    }
    cout << 1 << '\n';
    return 0;
}
Python
import sys
def main():
    data = sys.stdin.read().strip()
    n = int(data)
    # 当 n=1 时,唯一解
    if n == 1:
        print(1)
        print(1)
        return
    # 第一行:1 到 n
    first_row = list(range(1, n+1))
    # 第二行:2 到 n,再加上 1
    second_row = list(range(2, n+1)) + [1]
    # 输出结果
    print(' '.join(map(str, first_row)))
    print(' '.join(map(str, second_row)))
if __name__ == '__main__':
    main()
Java
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        
        // n=1 的情况
        if (n == 1) {
            System.out.println(1);
            System.out.println(1);
            return;
        }
        // 构造并输出第一行
        StringBuilder sb1 = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb1.append(i);
            if (i < n) sb1.append(' ');
        }
        System.out.println(sb1);
        // 构造并输出第二行
        StringBuilder sb2 = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            sb2.append(i).append(' ');
        }
        sb2.append(1);
        System.out.println(sb2);
    }
}
        题目内容
小红认为一个2×n的矩阵如果同时满足:
- 第一行由[1,n]的排列构成
 - 第二行也由[1,n]的排列构成
 - 对于任意两个元素 ai1,j1,ai2,j2(其中∣i1−i2∣+∣j1−j2∣=1),满足gcd(ai1,j1,ai2,j2)=1。
 
则该矩阵是一个好矩阵。 现在给定整数n,请你帮助小红构造一个2×n的好矩阵,可以证明始终存在一个满足条件的解。
长度为 n 的排列是由1~n这n个整数、按任意顺序组成的数组,其中每个整数恰好出现一次。例如,{2,3,1,5,4} 是一个长度为5的排列,而{1,2,2} 和 {1,3,4}都不是排列,因为前者存在重复元素,后者包含了超出范围的数。
输入描述
一个整数n(1≤n≤10^5),表示矩阵的列长。
输出描述
共2行n列,同一行的元素以空格隔开,若存在多解,输出任意一个满足条件的即可。
样例1
输入
2
输出
2 1
1 2