CF1080D Olya and magical square

题目：Olya and magical square

思路：

首先，n>31时可以不用考虑，因为只需要划分左上角或右下角的正方形就足够了。

令$f[i]$表示把大长方形$2^n$划分成全部是边长为$2^{n?i}$小正方形的划分次数。

$g[i]$表示形成边长$2^{n?i}$通路需要的最小划分数。

$f[i]=2^{i?2?2}+f[i?1]$

$g[i]=2^i?1+g[i?1]$

所以所求的$k$需满足$k>=g[i]$且$k<=f[i]+f[n?i]?(2^n?1)?(2^n?1)$

代码：

#include<bits/stdc++.h>
using namespace std;#define ll long long 
#define readll(x) scanf("%I64d",&x)
#define m 31
#define maxn 31ll n,k;
ll f[maxn+5],g[maxn+5];void init() {
    f[1]=g[1]=1;for(int i=2;i<=m;i++) {
    f[i]=(1LL<<i*2-2)+f[i-1];g[i]=(1LL<<i)-1+g[i-1];}
}int main() {
    init();ll T;readll(T);while(T--) {
    readll(n),readll(k);if(n>m) {
     printf("YES\n%I64d\n",n-1); continue; }int flg=-1;for(int i=0;i<=n;i++) {
    if(k>=g[i]&&k<=f[i]+f[n-i]*((1LL<<i)-1)*((1LL<<i)-1)) {
    flg=i;break;}}if(~flg) printf("YES\n%I64d\n",n-flg);else printf("NO\n");}return 0;
}