信息奥赛题解｜Outro

---

🚀 题目浏览

【题目描述】

Outro, means the end. This is the last problem of this contest. So, good luck!

Let’s call a permutation $p$ of length $n$ “Outro” if the condition $\gcd(i,p_i)=1$ holds for all $i\ (1\le i\le n)$.

Your task is for a given number $n$, construct any one of “Outro” permutation of length $n$ and print it.

• $\gcd(a,b)$ means the greatest common divisor of the two integers $a$ and $b$.
• A permutation of length $n$ means that each integer from $1$ to $n$ occurs exactly once in the sequence.

我们将长度为 $n$，且 $1$ 到 $n$ 之间的每个正整数均只出现一次的排列称为“全排列”。

例如，${5,2,1,4,3},{2,3,1}$ 就是全排列，而 ${1,2,2}, {3,1}$ 不是全排列。

现需要构造一个长度为 $n$ 的全排列 $p_1,p_2,\cdots,p_n$，并且需要保证对于 $i\in[1,n]$， $p_i$ 与 $i$ 互质。

两数互质即表示两数的最大公因数为 $1$，即 $\gcd(a,b)=1$。

【输入】

The only line contains a single integer $n$ — the length of permutation.

$1\le n\le 10^5$

输入仅一行一个正整数 $n$。

【输出】

The only line contains a single integer $n$ — the length of permutation.

$1\le n\le 10^5$

输入仅一行一个正整数 $n$。

【输入样例】

4

【输出样例】

4 3 2 1

---

☘️ 题解分析

需要知道的数学知识：$gcd(n, n+1) = 1$

来自GPT的证明：

1. Assume Contradiction: Assume that $\gcd(n, n+1) = d$ where $d > 1$. This means $d$ divides both $n$ and $n+1$.
2. Divisibility: If $d$ divides $n$ and $n+1$, then $n = dk$ and $n+1 = dl$ for some integers $k$ and $l$.
3. Difference: Consider the difference $(n+1) - n$. This equals $dl - dk$, which simplifies to $d(l - k)$.
4. Contradiction: Since $d(l - k) = 1$, this means $d$ must divide 1. However, the only divisors of 1 are ±1. Therefore, our assumption that $d > 1$ must be wrong.
5. Conclusion: Hence, $\gcd(n, n+1)$ cannot be greater than 1. Since $\gcd(n, n+1)$ is at least 1 (as every integer has 1 as a divisor), we conclude that $\gcd(n, n+1) = 1$.

---

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int n;

int main() {
    cin >> n;

    // gcd(1, n) = 1
    cout << n << " ";

//    gcd(i, i+1) = 1
    for (int i = 1; i <= n - 1; i++) cout << i << " ";
    cout << endl;

    return 0;
}