首页 > 试题广场 >

小q的数列

[编程题]小q的数列

热度指数：9621 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小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

算法知识视频讲解

Java

Sen🍓🍀

注释里有【】超时报错，不加就通过

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        in.nextInt();
 
        while (in.hasNextLong()) {  //  注意：超时是这里出问题
            long n = in.nextLong();
            String s = Long.toBinaryString(n);
            long fn = s.length() - s.replaceAll("1", "").length();
            // 1l(long) 或 1L(Long)    注意：结果不对是这里有问题
            long n1 = (1l << fn) - 1;
            System.out.println(fn + " " + n1);
        }
    }
}

发表于 2025-01-26 16:12:33 回复(0)