牛牛的反函数_牛客博客

传送门

加入一直乘以二加上去的话只能构造到 $60$ 的时候就超过了 $1e18$

所以需要考虑为奇数的情况的操作

发现每一次递归下去都会让函数值 $+1$

也就是说,奇数和偶数的函数变换只是让函数值 $+1$ 而已,那么显然是选择奇数的变换更优 $!!!$

也就是说我们倒推回去,一直执行 $*2$ 和 $-1$ 就能得到最小的 $x$

这么构造最优,预处理即可

发现最大能构造到 $120$

然而我这个***,一开始把奇数的 $f(x)=f(x+1)+1=f(\frac{x+1}{2})+2$

这么转换之后,就再也没看出什么规律。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[209];
signed main()
{
    memset( a,-1,sizeof a );
    int temp = 2; a[1] = 1; a[2] = 2;
    for(int i=3;i<=120;i++)
        if( !(i&1) )    a[i] = temp-1,temp-=1;
        else    a[i] = temp*2,temp*=2; 
    int t,x; cin >> t;
    while( t-- )
    {
        int x; cin >> x;
        if( x>120 )    printf("-1\n");
        else    printf("%lld\n",a[x] );
    }
}