自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 21:39:37，当前版本为作者最后更新于2020-08-12 13:24:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

给定一个序列 $a_i$ 的通项公式

$$a_0=0,a_1=1,a_{2i}=a_i,a_{2i+1}=a_i+a_{i+1}$$

给定 $n$，求 $a_n$

Solution

又是高精

这题可以进行转化，比如 $a_{2i}$ 和 $a_{2i+1}$，可以转化为两个 $a_i$ 和一个 $a_{i+1}$。

$a_i$ 和 $a_{i+1}$ 可以继续转化，我们就可以把 $a_n$ 转化为：

我们可以让所有满足 $n \in \mathbb Z,n>1$ 的 $a_n$ 转化为上面的式子，比如：

• $a_2=a_\frac{2}{2}=a_1=0 \times a_0+1 \times a_1=1$
• $a_3=a_\frac{2}{2}+a_{\frac{2}{2}+1}=a_1+a_2=a_1+a_1=0 \times a_0+2 \times a_1=2$
• $a_4=a_\frac{4}{2}=a_2=a_1=0 \times a_0+1 \times a_1=1$

所以我们只需要求出 $l$ 和 $r$ 即可，因为 $a_0=0,a_1=1$，所以输出 $r$ 即可。

Code 1

#include <bits/stdc++.h>

using namespace std;

int main () {
	long long t;
	scanf("%lld", &t);
	while (t--) {
		long long n;
		scanf("%lld", &n);
		long long l = 1, r = 0;
		while (n > 0) {
			if (n % 2 == 0)
				l = l + r;
			else
				r = l + r;
			n /= 2;
		}
		printf("%lld\n", r);
	}
	return 0;
}

预计得分：$50$ 分
Record Link

让我们重新审视 $n$ 的数据范围，$n \le 10^{100}$。

所以这题需要高精。

Code 2

t = int(input())

for i in range(1, t + 1) :
    n = int(input())
    
    l = 1
    r = 0

    while n > 0 :
        if n % 2 == 0 :
            l = l + r
        else :
            r = l + r
        n //= 2

    print(r)

预计得分：$100$ 分
Record Link

用 python 会被骂的，所以还是要好好写 C++ 比较好

By Shuchong
2020.8.12