GESP 题解库 / 1 级题解 / [GESP202409 一级] 美丽数字 · 第 5 / 29 题
✏️ GESP 2024.09 一级 · B4035

美丽数字

一个数是"美丽的"当且仅当它是 9 的倍数但不是 8 的倍数——核心武器是两个取余 + 逻辑与!

📊
n ≤ 10⁵
数据规模
🔢
aᵢ ≤ 10⁵
数值范围
⚡
O(n)
时间复杂度
🎯
%9 & !%8
核心判断
01
题目是啥?
先读题,再动笔 ~

📝 题目大意

小杨有 n 个正整数。他认为一个数是美丽数字当且仅当:

两个条件必须同时满足!统计 n 个数中有多少个美丽数字。

💡
人话翻译:能被 9 整除但不能被 8 整除的数,就是"美丽的"。比如 9 是(9%9=0 且 9%8=1≠0),72 不是(72%9=0 但 72%8=0,同时是 8 和 9 的倍数)。

📋 样例来看一看

输入:3 个数 → 1, 9, 72

1:  1%9=1≠0  → 不是 9 的倍数 → ✗ 不美丽
9:  9%9=0    9%8=1≠0   → 是 9 倍数,不是 8 倍数 → ✓ 美丽!
72: 72%9=0   72%8=0    → 是 9 倍数,也是 8 倍数 → ✗ 不美丽
→ 美丽数字数量 = 1
✅
为啥 72 不美?因为 72 既是 9 的倍数(72=8×9),又是 8 的倍数(72=9×8)。题目说"不是 8 的倍数"才美丽,所以 72 排除。
02
美丽数字是啥?
9 倍数但非 8 倍数

🔢 9 的倍数 vs 8 的倍数

先搞清楚哪些数是 9 的倍数,哪些是 8 的倍数:

美丽数字 = 9 的倍数 - 8 和 9 的公倍数

从 9 的倍数里去掉那些同时也是 8 的倍数的数。剩下就是"美丽的"。

9 的倍数: 9  18  27  36  45  54  63  72  81  90  99
8 的倍数: 8  16  24  32  40  48  56  64  72  80  88  96

美丽:      9  18  27  36  45  54  63      81  90  99  ✓
不美丽:                                               72 ✗(同时是 8 和 9 的倍数)
📌
72 的特殊性:72 = 8 × 9 = 9 × 8,它是最小的同时是 8 和 9 的倍数的数(即 最小公倍数 LCM(8,9) = 72)。每 72 个数就有一个同时是 8 和 9 的倍数。

🎨 可视化:1~30 中哪些是美丽数字?

绿色=美丽数字(9 的倍数),灰色=不是 9 的倍数,红色=同时是 8 和 9 的倍数(不美丽)

⚖️ 判断逻辑

一个数 x 是美丽数字,需要两个条件同时成立:

x % 9 == 0
且 (AND)
x % 8 != 0
↓
美丽数字 ✓
if (x % 9 == 0 && x % 8 != 0) {
    cnt++;  // 美丽!计数+1
}
03
核心思路:遍历+判断
逐个检查,满足条件就计数

🎯 走一遍样例:n=3, 数组=[1, 9, 72]

检查 1
1 % 9 = 1 ≠ 0 → 不是 9 的倍数 → ✗ 跳过
检查 9
9 % 9 = 0    → 是 9 的倍数 ✓
9 % 8 = 1 ≠ 0 → 不是 8 的倍数 ✓
→ 两个条件都满足 → 美丽!cnt = 1
检查 72
72 % 9 = 0  → 是 9 的倍数 ✓
72 % 8 = 0  → 也是 8 的倍数 ✗
→ 第二个条件不满足 → 不美丽!cnt 不变
最终结果
cnt = 1 → 输出 1
04
动手算一算
自己输入数据试试看

🧪 自由实验台

分析结果会显示在这里

点"算一下"按钮开始 →

05
算法三步走
思路理清楚

🧠 核心思路

1

读入 n 和 n 个数

第一行读 n,第二行读 n 个正整数。

2

逐个判断

对每个数 x,判断 x % 9 == 0 && x % 8 != 0。两个条件同时成立才算美丽。

3

计数输出

用计数器 cnt 记录美丽数字的个数,最后输出 cnt。

🔑 为啥用 && 而不是 ||?

题目说"是 9 的倍数但不是 8 的倍数"——"但"表示同时满足,用逻辑与 &&:

如果用 ||(或)就变成"满足任一条件",那所有 9 的倍数都算美丽了,不对!

06
完整代码
抄作业时间 ✍️

💻 C++ 完整解法

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int cnt = 0;  // 计数器
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        // 是 9 的倍数 且 不是 8 的倍数
        if (x % 9 == 0 && x % 8 != 0) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}
⚡
不需要数组!可以边读边判断——读一个数就检查一个,满足条件就 cnt++。不用把所有数存起来,省空间又省时间。

⚠️ 容易踩的坑

⚠️
别搞混 && 和 ||:"是 9 倍数但不是 8 倍数" = x%9==0 && x%8!=0。不是 ||!
⚠️
!= 0 不要写成 == 1:x % 8 != 0 是"不是 8 的倍数"。不要写成 x % 8 == 1,因为余数可能是 1~7 中任意一个。
⚠️
计数器初始化:cnt 要初始化为 0!不初始化的话可能是任意值。
07
算一算效率
复杂度分析
时间复杂度
O(n)
空间复杂度
O(1)
n 的范围
≤ 10⁵
aᵢ 范围
≤ 10⁵

时间:遍历 n 个数,每个做两次取余和一次比较,都是 O(1)。总共 O(n)。

空间:不需要数组,边读边判断,只有 cnt 和 x 两个变量,O(1)。

✅ n=10⁵ 时只有 10 万次循环,远远低于 1 亿次限制!

08
拓展一下
相关知识点

🔗 逻辑运算小抄

// 逻辑与(AND):两个都为 true 才为 true
if (a && b) { ... }  // a 和 b 都为 true

// 逻辑或(OR):至少一个为 true
if (a || b) { ... }  // a 或 b 为 true

// 逻辑非(NOT):取反
if (!a) { ... }     // a 为 false 时执行

// 组合使用
if (a && b || c) { ... }  // 先算 a&&b,结果再 || c
if (a && (b || c)) { ... } // 先算 b||c,结果再 && a

📚 9 的倍数特征

一个数是 9 的倍数,当且仅当它的各位数字之和是 9 的倍数。

🌟
思考题:如果题目改成"是 9 的倍数或不是 8 的倍数"(用 ||),美丽数字会变多还是变少?答案:变多!因为条件放宽了——只要满足一个就行。几乎所有不是 8 倍数的数都算美丽。