幸运数 题解

题目分析

本题要求判断给定正整数是否为“幸运数”。幸运数的定义分三步理解：

1. 拆位：将数字从右向左编号，个位为第 1 位，十位为第 2 位，百位为第 3 位，依此类推。
2. 变换：
   • 偶数位（第 2、4、6…位）保持不变；
   • 奇数位（第 1、3、5…位）要进行变换：将该位上的数字乘以 7，然后反复求各位数字之和，直到结果变成一位数（即不大于 9），这个一位数就是变换结果。
3. 判定：将所有位（偶数位直接取原数字，奇数位取变换结果）的数字相加，若总和是 8 的倍数，则原数是幸运数，输出 T；否则输出 F。

输入数据规模：数字个数 N ≤ 20，每个数小于 10^12。时间限制 1000ms，完全可以逐个处理。

解题思路

直接按照题目描述模拟即可，但需要注意两点：

• 对奇数位的“乘以 7 再反复各位相加”这一操作，其实就是在求该数字乘以 7 后的数字根（除 0 外，数字根等价于模 9 的余数，余数为 0 时数字根为 9）。利用这个性质可以将多次循环求和转化为一次公式计算，提高效率。
• 从右向左数位时，个位是第 1 位，我们可以用一个变量 d 表示当前是第几位（从 1 开始），每次处理完最后一位后除以 10，位数加 1。这样可以顺序遍历所有位。

因此解题流程为：

1. 读入 N；
2. 循环 N 次，每次读入一个数 x；
3. 对 x，从低位到高位逐位处理：
   • 用 x % 10 获取当前最低位的数字；
   • 若当前位数为偶数，直接累加该数字；
   • 若为奇数，用数字根公式计算变换结果并累加；
4. 判断累加和 sum 是否能被 8 整除，输出 T 或 F。

算法说明

1. 数字根公式

对于一个正整数 n，它的数字根 dr(n) 定义为不断将各位相加直到一位数的结果。数学上：

dr(n) = (n - 1) % 9 + 1   (n > 0)
dr(0) = 0

因此奇数位数字 t 变换结果的求法为：

dr(t * 7) = ((t * 7) - 1) % 9 + 1   (当 t*7 > 0)

只要 t ≠ 0，上述公式就成立；当 t = 0 时，乘以 7 仍为 0，变换结果就是 0。

参考代码中的 trans 函数就使用了这个技巧，避免了反复循环求和。

2. 逐位处理

cpp
复制
1int sum = 0;
2for (int d = 1; x > 0; d++, x /= 10) {
3    int t = (int)(x % 10);   // 取出当前最低位数字
4    if (d % 2 == 0)
5        sum += t;            // 偶数位直接累加
6    else
7        sum += trans(t);     // 奇数位变换后累加
8}

• d 从 1 开始，表示个位是第 1 位（奇数位）。
• 每次循环末尾将 x 除以 10，去掉已经处理过的最低位。
• 当 x 变成 0 时所有位处理完毕。

3. 整体流程

cpp
复制
1int N;
2cin >> N;
3while (N--) {
4    long long x;
5    cin >> x;
6    if (judge(x))
7        cout << "T" << endl;
8    else
9        cout << "F" << endl;
10}

题目提示可以边读边判断边输出，无需存储所有输入。

时间复杂度分析

• 对于每一个数 x（< 10^12），最多有 12 位数字。逐位处理每次常数时间，所以每个数的判断是 O(log x) ≈ O(12) 常数。
• N ≤ 20，因此总操作次数极小，能在 1ms 内完成。

空间复杂度为 O(1)，仅需几个变量。

参考代码及解释

cpp
复制
1#include <iostream>
2using namespace std;
3
4// 奇数位数字变换，t 为 0~9，返回变换后的一位数
5int trans(int t) {
6    if (t == 0)
7        return 0;
8    // 数字根公式：(n-1)%9+1
9    return (t * 7 - 1) % 9 + 1;
10}
11
12// 判断 x 是否为幸运数
13bool judge(long long x) {
14    int sum = 0;
15    // d 代表当前从右往左的位数（个位为 1）
16    for (int d = 1; x > 0; d++, x /= 10) {
17        int t = (int)(x % 10);  // 取末位
18        if (d % 2 == 0)         // 偶数位保留原数
19            sum += t;
20        else                    // 奇数位变换
21            sum += trans(t);
22    }
23    return (sum % 8 == 0);      // 总和是 8 的倍数
24}
25
26int main() {
27    int N = 0;
28    cin >> N;
29    for (int n = 0; n < N; n++) {
30        long long x = 0;
31        cin >> x;
32        if (judge(x))
33            cout << "T" << endl;
34        else
35            cout << "F" << endl;
36    }
37    return 0;
38}

代码细节解释

1. 数字根公式 (t * 7 - 1) % 9 + 1

   • 对于 t ∈ [1, 9]，t7 ∈ [7, 63]。该公式返回的值等价于反复求和至一位数的结果。例如 t=7 → 77=49 → 4+9=13 → 1+3=4，公式计算：(49-1)%9+1 = 48%9+1 = 3+1=4，一致。
   • 当 t=0 时单独处理返回 0。

2. 循环变量 d 的奇偶性

   • 个位为第 1 位（奇数），所以初始 d=1 时对个位做变换。
   • 偶数位 d=2,4,6… 保留原数字。
   • 注意位置从右往左编号，不能从左往右。

3. 数据类型

   • 输入的数小于 10^12，用 long long（或 long）存储，避免 int 溢出。

本题属于模拟题，只要理解位数的编号规则和数字根的性质，即可轻松解决。