H - 小q的数列 - 南昌大学航天杯第二届程序设计竞赛校赛网络同步赛

时间:2021-06-18 19:33:40

链接:https://www.nowcoder.com/acm/contest/122/H
来源:牛客网

题目描述
小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

[分析]
其实本质就是给一个数,他除以2如果是偶数就是本身,是奇数就+1.
然后第一个数字有规律可循
now=0;
now = now * 2 + 1;
不断循环第二句,每一个都是第一个数。

[代码]

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

int main()
{
    ll t;
    scanf("%lld", &t);
    ll a;
    while (t--)
    {
        scanf("%lld", &a);
        ll flag = 0;
        ll pos;
        ll ans=0;
        while (a)
        {
            if (a & 1)
            {
                ans++;
            }
            a /= 2;
        }
        ll now = 0;
        ll cnt = 0;
        while (cnt != ans)
        {
            now = now * 2 + 1;
            cnt++;
        }
        printf("%lld %lld\n", ans, now);
    }

}