题解 | 小q的数列

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
long search(long m,int step)
{
    if(m==0||m==1)
    return m;
    if(m==2)
    return 1;
    long mmm=step;//得到了几次奇数
    long mm=m;//判断留存
    while(m!=0&&m!=1)
    {
        
        if(m/2%2==0)//除后得到奇数？不是直接除
        {
            m=m/2;
        }
        else//是的话step++
        {
            mmm++;
            m=m/2;
        }
    }
    if(mm%2==0)//偶数的话默认次数-1
    return mmm;
    else//奇数默认加一，因为没有判断m==1再拆解
    return mmm+1;
}
long fff(long m)//递归，很好理解
{
    if(m==0||m==1)
    return m;
    else if(m%2==0)
    {
        return fff(m/2);
    }
    else
    {
        return fff(m/2)+1;
    }
}
int main() {
    long a;
    int m;
    int step=0;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%ld",&a);
        step=0;
        printf("%ld %ld\n",fff(a),(long)pow(2,(search(a,step)))-1);
    }
    return 0;
}
//下面是解释
//我们先全部求解，发现偶数就是f[x/2]，奇数就是f[(x-1)/2]+1;
//然后很自然的想到递归函数fff
//然后接下来就是找位置了
//全部列出来，然后找规律，我们发现只要下一项拆解到了奇数就会有加一的操作，所以我们联想和奇数的关系
//然后就发现只要拆解到奇数
//1:2*1-1 2*次数-1
//3:2*2-1
//5:2*2-1
//7:2*2*2-1
//然后结合f15，f31就发现了规律
//由于偶数默认传递过来的时候，我们最后都会拆到1，但是1又没有实际作用，所以return mmm
//奇数拆到1还要加1，所以我们return mmm+1
//是不是很奇妙呢，我也这样觉得，求佛啊求佛，开始暴力计算，结果段错误，不允许我用这么长的数据
//闪开！