题解 | #小q的数列#

看到题解区写的不够好理解来补充一下

f[0]=0 f[1]=1;

f[i]=f[i/2]+f[i%2];(i>=2)

乍看是个递归，但后面还要求f[n]出现第一次，用递归不好解决

再仔细观察f[i]的递推公式，可以发现其算法与十进制转二进制的“除2倒取余”类似——这里的f[i]表示i转为二进制数中'1'出现的次数，故可联想到用二进制运算求解本题

#include <stdio.h>
#include <math.h>
int main() {
    int t=0;
    long n=0;
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%ld",&n);
        while(n)//以下对n的操作都为对其二进制形式的操作（位操作）
        {   int count=0;   //count为n的二进制数中1出现的次数
            count+=(n&1)==1?1:0;//& 按位与，二进制两数同一位数上的数都为1则结果为真
            n>>=1;//n=n>>1 二进制n右移一位(低位舍弃，高位补符号位(正数为0)),达到逐位判断的效果
        }
        printf("%d %ld\n",count,(long)pow(2,count)-1);
                                  //等比数列求和公式
        count=0;//重置计数器
    }
    return 0;
}

把思路写下来了，第一次接触这类题感觉还是挺难的，最后求n'那里看了半天才发现是等比数列求和公式推来的