题解：P3922 中学数学题

__camelia · 2025-08-03 20:16:40 · 题解

P3922 中学数学题 题解

题目传送门

这中学数学题？

题意还是很明了的，一看就明白，不再赘述。

其实笔者看到这题就想暴力。

但是在看到难度和数据范围时不舍地捏碎了我的暴力梦。

解密输入后发现 k 最大是 10^{233}，根据通项公式，得到数列中可能的最大值为 2^{10^{233}} 果断放弃暴力。

极大的数据启示我们寻找规律。

Part 1：规律：

先贴上找规律用的代码：

code1：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 乘2
string multwo(const std::string& num) {
    string result;
    int carry = 0;

    for (int i = num.size() - 1; i >= 0; --i) {
        int digit = (num[i] - '0') * 2 + carry;
        result.push_back(digit % 10 + '0');
        carry = digit / 10;
    }

    // 处理进位
    while (carry > 0) {
        result.push_back(carry % 10 + '0');
        carry /= 10;
    }

    // 反转结果字符串以获得正确顺序
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    string current = "1";

    // 计算并输出2的1到10000次幂
    for (int i = 1; i <= 10000; ++i) {
        // 输出当前幂次和结果
        cout << "2^" << i << " = " << current << std::endl;

        // 计算下一个幂次
        current = multwo(current);

    }

    return 0;
}    

使用这段代码输出 2 的 1 到 10000 次幂，开始找规律。

为了方便讲解，我把前 50 行输出粘贴到下面：

2^1 = 1
2^2 = 2
2^3 = 4
2^4 = 8
2^5 = 16
2^6 = 32
2^7 = 64
2^8 = 128
2^9 = 256
2^10 = 512
2^11 = 1024
2^12 = 2048
2^13 = 4096
2^14 = 8192
2^15 = 16384
2^16 = 32768
2^17 = 65536
2^18 = 131072
2^19 = 262144
2^20 = 524288
2^21 = 1048576
2^22 = 2097152
2^23 = 4194304
2^24 = 8388608
2^25 = 16777216
2^26 = 33554432
2^27 = 67108864
2^28 = 134217728
2^29 = 268435456
2^30 = 536870912
2^31 = 1073741824
2^32 = 2147483648
2^33 = 4294967296
2^34 = 8589934592
2^35 = 17179869184
2^36 = 34359738368
2^37 = 68719476736
2^38 = 137438953472
2^39 = 274877906944
2^40 = 549755813888
2^41 = 1099511627776
2^42 = 2199023255552
2^43 = 4398046511104
2^44 = 8796093022208
2^45 = 17592186044416
2^46 = 35184372088832
2^47 = 70368744177664
2^48 = 140737488355328
2^49 = 281474976710656
2^50 = 562949953421312

统计了开头各数字出现次数后，发现以 4 为开头的项较少，考虑通过其他开头数字出现的规律来求解。

观察到以 1 为开头的数字有很多，不妨考虑以 1 为开头的数字。

将开头数字单独摘出：

发现 1 好像在循环。

继续往下找，又发现两种以 1 开头，结尾的序列：

按字典序排列后：

奇怪的事情发生了。

我们暂且称上面几种序列为“循环段”，用 c_i 表示，值为原数列中 list_i 的最高位的值。

顺便定义由 list_i 得到 c_i 的函数：

代入 list_i，c_i 得：

（注：此处 \log {x} 均为以十为底的对数，即 \log_{10} x，考虑可读性不在定义式中加入。）

发现：

段长为 5 时，段中出现一个 4。

段长为 4 时，段中不出现 4。

在笔者往下看了几百行数字后，更确信此结论的正确性。

Part 2：证明：

命题：循环段长度为 4 \mid 5， 且仅有如上 5 种：

因为原数列中每项都等于前一项 \times 2。

所以每个数位都应 = 前一位 \times 2 (竖式乘法计算步骤)。

若段长为 5：

则 c_5 对应的项的前两位应为此循环段中第一个 \ge 10 的数。

根据循环段定义 (首尾为 1 )：

则此循环段的 c_4 一定不是 1，

即原数列这一项开头不是 1。

考虑由 c_1 得到 c_5 的情况：

每次 \times 2，对吧？

又因为第一位为 1 , 考虑进位最多的情况：

如 2^{75} \~ 2^{79}：

2^75 = 18889465931478580854784
2^76 = 37778931862957161709568
2^77 = 75557863725914323419136
2^78 = 15115727451828646838272
2^79 = 302231454903657293676544

发现每次进位都是先 \times 2 后 + 1。

不进位仅 \times 2。

所以：

c_1 = 1\\ c_2 = 2 \mid 3 \\ c_3 = 4 \mid 5 \mid 6 \mid 7\\ c_4 = 8 \mid 9 \mid 1 \\ c_5 = 1 根据循环段的定义，段长最大为 $5$。 又因为 $c_4$ 是循环段中第一个可能出现 $1$ 的单位， 所以段长最短为 $4$。 根据 $c_1$ 到 $c_5$ 的值及进位规律，易得到下面这张表：  上图中红边代表不进位且得到的 $c_{i+1} < 10$，也可理解为 $f(c_{i+1}) = c_{i+1}$。 蓝边代表进位且得到的 $c_{i+1} < 10$， 即 $f(c_{i+1}) = c_{i+1}$。 绿边代表得到的 $c_{i+1} \ge 10$，也即 $f(c_{i+1}) = 1$。 由上文定义可知： $\quad$ 绿边后必连接 $1$，当遇到绿边时，说明循环段结束。 图中共有 $5$ 条绿边，说明前文定义的循环段形式有限，数量为 $5$ 种。 顺着红蓝边查找路径，将路径经过的点按顺序排列后发现： ${\color{blue}1} , 2 , {\color{red}4} , 8 , {\color{blue}1} {\color{blue}1} , 2 , {\color{red}4} , 9 , {\color{blue}1} {\color{blue}1} , 2 , 5 , {\color{blue} 1} {\color{blue}1} , 3 , 6 , {\color{blue}1} {\color{blue}1} , 3 , 7 , {\color{blue}1}

所以，循环段的长度为 4 \mid 5，且是上文列出的 5 种情况之一。

证毕。

大佬们觉得罗嗦轻点喷啊！求求了！

这部分是给和笔者一样的蒟蒻们理清思路而写的。

（俺一下午才明白），有错误欢迎指出！

Part 3: 题目解法：

我们已经将这个等比数列划分成了几个循环段的拼接。

因为循环段开头结尾都为 1，不好处理，舍弃最后一个 1，记作 newc：

1 , 2 , {\color{red}4} , 8 1 , 2 , {\color{red}4} , 9 1 , 2 , 5 1 , 3 , 6 1 , 3 , 7

观察到对于每一个 newc，当长度为 4 时，其中必然包含 1 个 4。

不妨设序列的前 k+1 项中有 x 个循环段满足此段项数为 4，即上两种。

可以发现，2^i 若发生了进位，那么 2^{i+1} 的位数将会多 1。

找到满足 k' \le k+1 且 2^{k'} = 1 的最大的 k'。

设 2^k 共有 m 位。

考虑 2^{k'} 时共发生了几次进位即 m-1。

观察到循环段与进位的关系：

$1 , 2 , {\color{red}4} , 9 \quad$ 进位 $1 1 , 2 , 5 \quad$ 进位 $1 1 , 3 , 6 \quad$ 进位 $1 1 , 3 , 7 \quad$ 进位 $2

相加后发现进位次数就等于循环段的个数。

就可以求出段长为 3 的段数的个数：(m - 1 - x)

根据项数列方程可得：

解得：

因为 m 是 2^{k'} 在十进制下的位数，所以：

就得到答案了。

纪念我的第一道黑题！

和我的第一道黑题题解！

（话说这题咋成黑题了。）

update at 12.27 (my birthday) ：修复了一处 \LaTeX 错误，更改了文章中有关题目难度的部分。