Codeforces 1419B. Stairs

题意:
x个方格可以构成多少种不同阶梯图形,要求每个组成单位都是正方形。

思路:
容易推出 s u m [ i ] = s u m [ i − 1 ] ∗ 2 + n o w ∗ n o w sum[i] = sum[i - 1] * 2 + now * now sum[i]=sum[i1]2+nownow,然后算能用多少个就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <unordered_map>
#include <bitset>using namespace std;typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 998244353;ll sum[105];void init() {sum[1] = 1;ll now = 2;for(int i = 2;i <= 30;i++) {sum[i] = sum[i - 1] * 2 + now * now;now *= 2;}
}int main() {init();int T;scanf("%d",&T);while(T--) {ll x;scanf("%lld",&x);int ans = 0;for(int i = 1;i <= 30;i++) {if(x >= sum[i]) {ans = i;x -= sum[i];} else {break;}}printf("%d\n",ans);}return 0;
}