题目链接
翻译
定义一个数组 (a_i = i)
你每次可以选择两个下标 (i) 和 (j)，让你用 (a_i) 去除 (a_j) (向上取整)。
希望最后 (n) 个数字中剩下 (n-1) 个 (1) 以及 (1) 个 (2)。
且操作的次数不能超过 (n+5) 次。
题解
思路是这样的，对于 (1) 的产生，只需用 (i) 去除 (i+1) 即可。
看样子我们只需要进行 ((i,i+1)) 就能完成这个任务，但是有一个问题，最大的 (n) 没有 (n+1) 让他进行除了。
想法是留一个比较小的数字 (x)，让 (n) 一直去除 (x)。
(x) 为 (2) 的话，太小了，要除的次数太多了。
所以就一直试这个数字 (x)，发现 (x=64) 时是合适的。
那么就用 ((i,i+1)) 这样的操作把除了 (2,64,n) 这三个数字之外的数字都变成 (1)。
然后用 (n) 不断除 (64),因为 (64^3) 就大于 (2*10^5) 了，所以只需三次操作。
而 (64) 变成 (1) 则需要除 (2) 六次。
再加上 ((i,i+1)) 的 (3..63) 以及 (65..n-1) 的 (n-4) 次。
那么最多的操作次数就为 (n-4+6+3=n+5) 次操作。
对于 (n) 小于等于 (64) 的情况，就直接保留 (n) 和 (2) ，然后用 (n) 除 (2) 就行了。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5;
int T, n,tot;
int x[2*N + 10], y[2*N + 10];
void addOpe(int i, int j) {
x[++tot] = i;y[tot] = j;
}
void outAnswer() {
cout << tot << endl;
for (int i = 1; i <= tot; i++) {
cout << x[i] << " " << y[i] << endl;
}
}
int main() {
#ifdef LOCAL_DEFINE
freopen("in.txt", "r", stdin);
#endif // LOCAL_DEFINE
ios::sync_with_stdio(0), cin.tie(0);
cin >> T;
while(T--){
tot = 0;
cin >> n;
if (n <= 64) {
for (int i = 3; i <= n - 1; i++) {
addOpe(i, i + 1);
}
//a[3..n-1]=1
int an = n;
while (an != 1) {
addOpe(n, 2);
an = ceil(1.0 * an / 2.0);
}
}
else {
const int mid = 64;
//n>100
for (int i = 3; i <= mid-1; i++) {
addOpe(i, i + 1);
}
//a[3..mid-1] = 1
for (int i = mid+1; i <= n - 1; i++) {
addOpe(i, i + 1);
}
//a[mid+1..n-1]=1
int an = n;
while (an != 1) {
addOpe(n, mid);
an = ceil(1.0 * an / mid);
}
int amid = mid;
while (amid != 1) {
addOpe(mid, 2);
amid = ceil(1.0 * amid / 2);
}
}
outAnswer();
}
return 0;
}