CF1469D
DDF_
·
·
题解
题面
一个长为 n 数组 a，初始满足 a_{i}=i。
可以做不超过 n+5 次操作：每次选定满足 x \neq y 的两个下标 x,y，令 a_{x}=\lceil \frac{a_{x}}{a_{y}} \rceil。
问是否可以将 a 数组变为含 n-1 个 1 和 1 个 2 的数组。
题解
不知道，只会暴力。
然后要处理这个 $n$，在 $[2,n-1]$ 里找一个数 $x$，对 $n$ 和 $x$ 做操作，每次大除以小直到一个数为 $1$，特判另一个数是否为 $2$，如果为 $2$ 那么这个方案是合法的。
上面这个可以直接模拟。
然后从 $2$ 到 $n-1$ 暴力枚举找到做操作次数最小的 $x$。在 $[1,n]$ 中所有数，除了 $1$，$x$ 和 $n$ 全都直接除以 $n$，然后 $x$ 和 $n$ 照上面那个模拟互相除。
时间复杂度 $O(n \log n)$。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int _;
int n;
int main() {
scanf("%d",&_);
while(_--) {
scanf("%d",&n);
if(n<3) {puts("0");continue;}
int ans=30000,s=0;
for(int i=2;i<n;i++) {
int x1=i,x2=n,cnt=0;
while(x1>1&&x2>1) {
if(x2>x1) x2=(x2+x1-1)/x1,cnt++;
else x1=(x1+x2-1)/x2,cnt++;
}
if(cnt<ans&&(x1==2||x2==2)) ans=cnt,s=i;
}
printf("%d\n",n-3+ans);
for(int i=2;i<n;i++) if(i!=s) printf("%d %d\n",i,n);
// for(int i=n;i>=3;i--) printf("%d %d\n",i,i/2+1);
int x1=s,x2=n;
while(x1>1&&x2>1) {
if(x2>x1) x2=(x2+x1-1)/x1,printf("%d %d\n",n,s);
else x1=(x1+x2-1)/x2,printf("%d %d\n",s,n);
}
}
return 0;
}
```