小q的数列

NC15979. 小q的数列

描述

小q最近迷上了各种好玩的数列，这天，他发现了一个有趣的数列，其递推公式如下：

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

现在，他想考考你，问：给你一个n，代表数列的第n项，你能不能马上说出f[n]的值是多少，以及f[n]所代表的值第一次出现在数列的哪一项中？（这里的意思是：可以发现这个数列里某几项的值是可能相等的，则存在这样一个关系f[n'] = f[n] = f[x/2]+f[x%2] = f[x]...（n'<n<x）他们的值都相等，这里需要你输出最小的那个n'的值)(n<10^18)

输入描述

输入第一行一个t
随后t行，每行一个数n，代表你需要求数列的第n项，和相应的n'
(t<4*10^5)

输出描述

输出每行两个正整数
f[n]和n'，以空格分隔

示例1

输入:

2
0
1

输出:

0 0
1 1

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 82ms, 内存消耗: 8196K, 提交时间: 2022-02-11 20:24:18

#include<cstdio>
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		long long x;
        scanf("%lld",&x);
		int cnt=__builtin_popcountll(x);
		printf("%d %lld\n",cnt,(1ll<<cnt)-1);
	}
    return 0;
}

pypy3 解法, 执行用时: 1667ms, 内存消耗: 38428K, 提交时间: 2023-02-21 19:21:45

for i in range(int(input())):
    n=int(input())
    b=bin(n).count("1")
    print(b,2**b-1)

Python3 解法, 执行用时: 1875ms, 内存消耗: 10888K, 提交时间: 2022-02-05 19:25:35

for _ in range(int(input())):
    n=bin(int(input())).count('1')
    print(n,(1<<n)-1)