CF1469D Ceil Divisions

siyue · 2021-01-24 10:13:04 · 题解

题目

这道题如果直接用小数除以大数的话，最后一个大数就要除很多次，此时我们可以在中间找一个数，这样次数就不会超过（n+5）了。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,t,a[500005][2],total;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>t;
    while(t--)
    {
        cin>>n;
        total=0;
        if(n<=6)
        {
            for(i=3; i<=n; i++)
            {
                int l=i;
                while(l!=1)
                    a[++total][0]=i,a[total][1]=2,l=(l+1)/2;
            }
            cout<<total<<endl;
            for(i=1; i<=total; i++)
                cout<<a[i][0]<<' '<<a[i][1]<<endl;
        }
        else if(n>=18)
        {
            for(i=18; i<=n; i++)
                a[++total][0]=i-1,a[total][1]=i;
            for(i=5; i<=16; i++)
                a[++total][0]=i-1,a[total][1]=i;
            int l=n;
            while(l!=1)
                a[++total][0]=n,a[total][1]=16,l=(l+15)/16;
            a[++total][0]=16,a[total][1]=3,a[++total][0]=16, a[total][1]=3,a[++total][0]=16,a[total][1]=3,a[++total][0]=3,a[total][1]=2,a[++total][0]=3,a[total][1]=2;
            cout<<total<<endl;
            for(i=1; i<=total; i++)
            {
                cout<<a[i][0]<<' '<<a[i][1]<<endl;
            }
        }
        else if(n>6&&n<18)
        {
            for(i=4; i<=n; i++)
                a[++total][0]=i-1,a[total][1]=i;
            int l=n;
            while(l!=1)
                a[++total][0]=n,a[total][1]=2,l=(l+1)/2;
            cout<<total<<endl;
            for(i=1; i<=total; i++)
                cout<<a[i][0]<<' '<<a[i][1]<<endl;
        }
    }
    return 0;
}