CF1469D Ceil Divisions题解

CF1469D Ceil Divisions

感觉是很巧妙的一题？

一开始想到，对于任何小于$n$的数$x$，直接对它除以$n$可以得到$1$。那么对$3\sim n-1$做完此操作后，还剩下$1$、$2$、$n$。将$n$变成$1$要花费$logn$次，显然总操作次数超过了$n+5$次。

进一步地，发现瓶颈在于把$n$变成$1$，于是利用根号，用$\sqrt{n}$对$n$进行两次除操作就可以把$n$变成$1$了。

极限数据$2e5$最多开$5$次根号，每次开根号就有一次多余的操作，恰好满足$n+5$的限制。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,tot,ans[N][2];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        tot=0;
        scanf("%d",&n);
        while(n>2)
        {
            int p=sqrt(n);
            if(p*p<n)p++;
            for(int i=p+1;i<n;i++)ans[++tot][0]=i,ans[tot][1]=n;
            ans[++tot][0]=n,ans[tot][1]=p;
            ans[++tot][0]=n,ans[tot][1]=p;
            n=p;
        }
        printf("%d\n",tot);
        for(int i=1;i<=tot;i++)printf("%d %d\n",ans[i][0],ans[i][1]);
    }
    return 0;
}