自动搬运

查看原文

来自洛谷，原作者为

	zengyongxu QQ:2116368445 || 「不积跬步无以至千里，不积小流无以成江海。」

搬运于2025-08-24 22:43:39，当前版本为作者最后更新于2025-08-14 10:22:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

写在前面

::::warning[warning] 不要抄题解！ ::::

认为是一道好题，特地来写写题解以回报自己一小时的战果。

思路

做完这道题，看了看楼下两篇题解，感觉我的代码像是两篇题解综合起来。

首先，看到这道题，首先想到的是部分分（是因为我太弱了）。

但是部分分没有啊！那就只好骗分，注意到 $k=0$ 或 $k = n$ 的时候答案一定是 0，于是特判一下。

但是我也不知道多少分。因为接下来我想到了正解。

接下来来思考正解。

手搓自己造的样例，发现这个 $a_{n+1}$ 非常重要，可以用来当临时使用。

那么，我们让任意一个数赋值到 $n+1$，不妨设为 1，令一个指针 $p$，初始指向 1，代表当前可以赋值为目标的地方。

那我们就可以不断地让当前数赋值为应该目标数，然后让 $p$ 指向目标数所在的下标。

但是，在手搓了自己又造了的几组略大的数据之后，发现好像会有一些问题诶。

可能会出现多个环，而不是理想状态下的 $p$ 指针一直移动最终全部赋值成目标值。

那么每次在发现环的时候就可以让 $p$ 指针随便指向一个地方就可以了，我这里让 $p$ 指针直接指向下一个地方。

代码实现 & 细节

首先，判断是否形成环。只需要存一个 $begin$ 指针，表示一个环的开头，一开始 $begin$ 指向 1，以后每次发现 $p = begin$ 的时候就形成了环，这是 $p$ 指针会指向下一个地方，而我们让 $begin$ 指向 $p$ 即可。

其次，形成环时需要实现的步骤：

1. 让当前 $a_p$ 赋值为 $a_{n + 1}$ 因为 $a_{n+1}$ 存储了 $a_{begin}$ 原本的值。
2. 移动 $p$ 指针，更新 $begin$ 指针。
3. 让 $a_{n+1}$ 赋值为 $a_p$ 这样才可以在下次发现形成环的时候正确的赋值。

这一部分的注意点是在第 3 步中，需要判断是不是还有需要修改的地方。可能不用，因为 $a_{n+1}$ 最终赋值什么值都可以。但是我懒没有尝试可不可以。

其他注意事项和小技巧：

1. 前面所说的骗分同时也是特判记得加上。
2. 可以直接用 vector 来存储答案，不需要楼下的 $n + \gcd(n,k)$。（当然我只是偷懒而已） 顺便吐槽：楼下怎么还把加法打成了乘法啊……

代码 & 代码解释

::::success[code]

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int t, n, k, to[N];

int gcd(int a, int b){
    return (!b ? a : gcd(b, a % b));
}

int main(){
    cin >> t;
    while (t -- ){
        cin >> n >> k;
        if (k == 0 || k == n){
            cout << "0\n";
            continue;
        }
        
        for (int i = 1; i <= n; i ++ ) to[i] = (i <= k ? n - k + i : i - k);

        vector <pair<int, int> > res;

        res.push_back({n + 1, 1});
        int now = 1, beg = 1, cnt = 0;
        while (cnt < n){
            if (to[now] != beg){
                res.push_back({now, to[now]});
                now = to[now];
            }
            else{
                res.push_back({now, n + 1});
                beg = now = now % n + 1;
                if (cnt != n - 1) res.push_back({n + 1, now});
            }
            cnt ++;
        }
        
        cout << res.size() << "\n";
        for (auto [i, j] : res) cout << i << " " << j << "\n";
    }
}

::::

代码解释：

1. 代码中的 $now$ 为文中的 $p$。
2. 代码中的 $beg$ 为文中的 $begin$。
3. 代码中的 $res$ 为文中小技巧部分所提到的记录答案的 vector。
4. 代码中的 $to$ 为存储目标值的数组。