自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 22:20:51，当前版本为作者最后更新于2020-08-07 19:54:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

P6445

Description

定义由 $4$ 和 $7$ 组成的数为幸运数，求第 $k$ 个幸运数。

Solution 1

只有 $4$ 和 $7$？其实我们可以模拟成二进制数的，即求第 $k$ 个二进制数，只不过 $0$ 是 $4$，$1$ 是 $7$。

1. 将 $(k)_{10}$ 转化为二进制
2. 如果是 $0$ 输出 $4$，是 $1$ 输出 $7$，比如 $0100111$ 就输出 $4744777$

Code 1

#include <bits/stdc++.h>

using namespace std;

long long j, a[100000];

void erzhi (long long i) {
	while (i) {
        	j++;
    		a[j] = i % 2;
    		i /= 2;
	}
}

void ans (long long k) {
	erzhi(++k);
	for (long long i = j - 1; i >= 1; i--)
		if (a[i] == 0)
			printf("4");
		else
			printf("7");
}

int main () {
	long long k;
	scanf("%lld", &k);
	ans(k);
	return 0;
}

Solution 2

我们也可以直接不用二进制，用一种类似递归的方式来。

比如我们看第 $8$ 个幸运数，$447$，是第 $3$ 个幸运数加上一个 $7$，第 $3$ 个幸运数又是第 $1$ 个幸运数加上一个 $4$，这时候我们就可以发现一个规律，对于第 $k$ 个幸运数，可以通过下面的公式得出（假设第 $k$ 个幸运数是 $a_k$）

$$a_k=a_{\left\lfloor\frac{k-1}{2}\right\rfloor}\times 10+d\begin{cases}d=4(k\bmod 2=1)\\d=7(k\bmod 2=0)\end{cases} $$

初始化 $a_1=4,a_2=7$。

然后就可以打一份递归的代码了，这里建议用字符串存储。

By Shuchong
2020.8.7