解题思路

阿尔法人不喜欢数字 7，所以他们在数数的时候，凡是含 7 的数字都被跳过了。

我们来看看阿尔法人的数列（把含 7 的自然数去掉）： 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20……

也就是说，阿尔法人数的第几个数，对应的自然数就是这个数列里的数。

题目给的例子：

• 阿尔法数 8 → 对应自然数 7（因为 7 被跳过，8 是数列里第 7 个数）；
• 阿尔法数 18 → 对应自然数 16（18 是数列里第 16 个数）。

那么阿尔法数 n 对应的自然数，就是“1 到 n 之间不含数字 7 的数的个数”。因为阿尔法人数到第 n 个数时，数过的自然数是 1 到 n，其中含 7 的都被跳过了，数到的个数就是不含 7 的个数。

题目要求定义函数 seven(int x) 判断整数 x 是否含数字 7，方法：

• 用 while 循环，每次看 x 的个位（x % 10）是不是 7；
• 如果是就返回 true；
• 然后把 x 除以 10（去掉个位），继续看下一位；
• 循环结束都没找到 7，就返回 false。

解题步骤：

1. 读入阿尔法数 n；
2. 遍历 i = 1 到 n，如果 seven(i) 是 false（不含 7），答案加 1；
3. 输出答案。

验证样例 n = 10：1、2、3、4、5、6、8、9、10 都不含 7，共 9 个，输出 9，和样例一致。

参考代码

// P4599 失踪的7：统计 1~n 中不含数字 7 的数的个数，就是 n 对应的自然数
#include <iostream>
using namespace std;

// 判断整数 x 中是否含有数字 7，含 7 返回 true
bool seven(int x) {
    while (x) {                    // 只要 x 还有数字
        if (x % 10 == 7) return true;  // 当前个位是 7，直接返回 true
        x /= 10;                   // 去掉个位，继续看下一位
    }
    return false;                  // 每一位都不是 7
}

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++)   // 数 1 到 n 的每个数
        if (!seven(i)) ans++;      // 不含 7 的数才会被阿尔法人数到
    cout << ans << endl;
    return 0;
}

复杂度分析

要对 1 到 n 的每个数都调用一次 seven 判断，每个数最多有它的位数位，所以总时间大约是 O(n × log n)。n 是正整数，规模不大，运行非常快。空间只用几个变量，是 O(1)。