首页 > 试题广场 >

小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

算法知识视频讲解

keepyang

go 处理输入是真不行..

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    // "strings"
)

// fmt.Scan fmt.Fscan 都超时..
func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()

    var n int
    fmt.Fscan(os.Stdin, &n)

    for i := 0; i < n; i++ {
        var t int
        // fmt.Fscan(os.Stdin, &t)
        s, _ := r.ReadString('\n')
        t,_ = strconv.Atoi(s[:len(s)-1])
        cnt := 0
        for t > 0 {
            if (t & 1) == 1 {
                cnt++
            }
            t >>= 1
        }
        //fmt.Fprintf(os.Stdout, "%d %d\n", cnt, (1<<cnt)-1)
        w.WriteString(strconv.Itoa(cnt))
        w.WriteByte(' ')
        w.WriteString(strconv.Itoa((1 << cnt) - 1))
        w.WriteByte('\n')
    }
}

编辑于 2023-12-26 06:36:35 回复(0)