P3922 中学数学题 题解

题目传送门

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 = 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

段长为 $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}$：

CPP

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$$

$c_4$ 的值为 $1 \mid 8 \mid 9$，而 无论 $c_4$ 取何值，经过扩展后的 $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 , 2 , {\color{red}4} , 8$

$1 , 2 , {\color{red}4} , 9$

$1 , 2 , 5$

$1 , 3 , 6$

$1 , 3 , 7$

$1 , 2 , {\color{red}4} , 8 \quad$ 不进位

$1 , 2 , {\color{red}4} , 9 \quad$ 进位 $1$

$1 , 2 , 5 \quad$ 进位 $1$

$1 , 3 , 6 \quad$ 进位 $1$

$1 , 3 , 7 \quad$ 进位 $2$