解题思路
先考虑如何将一堆数变为相同的。
显然，这里有一个条件 \(n=2^k,k\in \mathbb Z\)，证明如下：
- 每次操作只能将两个数变为相同的，那么一个数在使得其他数变为相同数的操作中（我们不妨将所有数进行这种操作称为一轮操作），一个数最多被使用一次；
- 按照错位操作，即第一轮 \(1\) 和 \(2\)、\(3\) 和 \(4\)，第二轮 \(1\) 和 \(3\)、\(2\) 和 \(4\) 这种最优决策（这样可以保证每一轮结束后不同数的数量最少）每一轮也最多减少 \(\displaystyle \left\lfloor \frac{n}{2} \right\rfloor\) 种数量；
- 按照如上方法，在第 \(i\) 轮会有 \(a_i\bmod 2^i=1\) 的数无法被操作到，那么当且仅当 \(n=2^k,k\in \mathbb Z\) 的时候，所有数可以变为相同的；
由上可以推出，当且仅当 \(n=2^k+z,k\in \mathbb Z,z\le 1\) 的时候，序列可以根据以上操作变为最多有两个不同的，而这种情况也即为样例中的情况。
那么考虑 \(n\) 为其他数的情况。我们发现对于任意大于 \(1\) 的正整数，都可以找到一个 \(x\) 使得 \(x=2^k,k\in \mathbb Z\) 且 \(\displaystyle x\ge \frac{n}{2}\)。我们还发现，因为对于任意的序列 \(a\) 和函数 \(f\)，构造方案都应成立，那么可以认为 \(a\) 对于构造方案没有影响。那么我们考虑将序列拆为 \([1,x]\) 和 \([n-x+1,n]\) 两个长度均为 \(x\) 的部分，不妨先通过上文操作使得区间 \([1,x]\) 中的数全部相等，然后再通过上文操作使得区间 \([n-x+1,n]\) 中的数全部相等，由于 \([1,n-x]\) 的数在两次操作后一定是相等的，而 \([n-x+1,n]\) 中的数在两次操作后是相等的，那么在这种操作方案下，最终序列一定有小于等于两种不同的数。
由于我们在使一个序列相同时错位操作，那么每个数在一轮中会被恰好操作一次，又由于每轮操作会使不同的数的数量减半，那么最多进行 \(O(\log_2x)\) 轮操作，那么我们最终总共会进行 \(O(2\cdot x\log_2x)\) 次操作，而在 \(n\le 1.5\times 10^4\) 的数据范围下，操作次数是小于等于 \(229376\) 次的，可以通过本题。
时间复杂度 \(O(n\log n)\) ，空间 \(O(n\log n)\)，可以通过本题。
注意事项
错位操作时细节有亿点多，如果是循环写法，一定要注意倍增的时候不要超出 \(n\) 的范围了；如果是递归或 vector 合并写法，注意数组的清空。
AC 代码
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define N 15005
#define pii std::pair<int,int>
int n,cnt,c[N];
std::vector<pii> ans;
std::vector<int> a[N],b[N];
inline void print(){
printf("%d\n",ans.size());
for(auto now:ans){
int x=now.first;
int y=now.second;
printf("%d %d\n",x,y);
}
}
inline void GetAns(int l,int r){
int m=r-l+1,now=2;while(m>1){
for(register int i=l;i<=r;i+=now)
for(register int j=i;j<i+(now>>1);++j)
ans.push_back({j,j+(now>>1)});
m>>=1;now<<=1;
}
}
signed main(){
scanf("%d",&n);
for(register int i=1;i<=n;++i)
c[i]=i;int mid=1;
while((mid<<1)<n) mid<<=1;
GetAns(1,mid);
GetAns(n-mid+1,n);
print();
}