题解：CF1419B Stairs

Marionette_Guillotin · 2024-03-31 16:02:51 · 题解

不难发现，只有 n 为 2^{k}-1 时，才能组成一个“好阶梯”。推理过程如下：

任意“好阶梯”中最大的正方形把整个阶梯分成了上下两部分，而这两部分又分成了两个小的“好阶梯”。而次大的正方形把这两个小的“好阶梯”再次分出两个更小的“好阶梯”。以此类推，每一个“好阶梯”都可以被一个正方形再次分出两小的“好阶梯”，而这些部分可以继续分割成更小的“好阶梯”。

接下来就是代码实现了，需要使用位运算和高斯求和公式。

温馨提示：十年 OI 一场空，不开 long long 见祖宗！

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        int n,p=1;cin>>n;
        while(n>0)
        {
            p++;
            int k=(1<<p)-1;//位运算
            n-=k*(k+1)/2;//高斯求和
        }
        cout<<p-1<<endl;//p 需要减 1
    }
    return 0;
}