解题思路

先读懂题目

题目要我们在 1~n 这些数里，找出“各个位的和”既不能被 2 整除、也不能被 5 整除的数，最后数一数一共有多少个。

什么是“各个位的和”？就是把一个数拆成一位一位，再把每一位加起来。比如：

• 123 的各个位是 1、2、3，各个位的和 = 1 + 2 + 3 = 6
• 25 的各个位是 2、5，各个位的和 = 2 + 5 = 7
• 30 的各个位是 3、0，各个位的和 = 3 + 0 = 3
• 100 的各个位是 1、0、0，各个位的和 = 1 + 0 + 0 = 1

什么是“不能被 2 整除”？就是除以 2 会余 1，比如 7 ÷ 2 = 3 余 1，所以 7 不能被 2 整除。“不能被 5 整除”也是这个意思，比如 7 ÷ 5 = 1 余 2，所以 7 不能被 5 整除。

拿题目给的例子试一试

• 25：各个位的和 = 2 + 5 = 7。7 除以 2 余 1，7 除以 5 余 2，既不能被 2 整除也不能被 5 整除，所以 25 满足条件。
• 30：各个位的和 = 3 + 0 = 3。3 除以 2 余 1，3 除以 5 余 3，同样既不能被 2 整除也不能被 5 整除，所以 30 也满足。
• 12：各个位的和 = 1 + 2 = 3，3 既不能被 2 整除也不能被 5 整除，满足。
• 100：各个位的和 = 1，1 既不能被 2 整除也不能被 5 整除，满足。
• 那什么样的数不满足呢？比如 5 的各个位的和是 5，5 能被 5 整除，所以 5 不满足；11 的各个位的和是 2，2 能被 2 整除，所以 11 也不满足。

怎么在程序里做

步骤很简单，分三步：

1. 用一个循环，从 1 数到 n，每个数都检查一遍；
2. 对每个数 i，拆出它的每一位，加起来得到各个位的和 s；
3. 判断 s % 2 != 0 并且 s % 5 != 0（既不能被 2 整除，也不能被 5 整除），满足就让计数器 +1。

拆位的方法：用 while 循环，每次取出个位再丢掉个位。

• t % 10 可以取出 t 的个位（比如 123 % 10 = 3）；
• t / 10 可以丢掉 t 的个位（比如 123 / 10 = 12）；
• 一直这样做，直到 t 变成 0，就说明每一位都拆完了。

以 123 为例，完整走一遍拆位：

• 一开始 t = 123，s = 0；
• 第一步：t % 10 = 3，s 变成 3；t / 10 = 12；
• 第二步：t % 10 = 2，s 变成 3 + 2 = 5；t / 10 = 1；
• 第三步：t % 10 = 1，s 变成 5 + 1 = 6；t / 10 = 0，循环结束；
• 得到 123 的各个位的和 s = 6。

枚举 1~n 的每一个数都这样做一遍，统计出满足条件的个数，最后输出计数器的值就可以了。

参考代码

#include <iostream>  // 用于 cin/cout 输入输出

using namespace std;

int main()
{
    int n;         // 输入的上限 n，在 1~n 中找数
    cin >> n;      // 读入 n

    int cnt = 0;   // 计数器，记录满足条件的数的个数

    // 从 1 到 n 一个一个检查
    for (int i = 1; i <= n; i++)
    {
        int t = i;  // 用 t 来拆 i 的每一位（不直接改动 i）
        int s = 0;  // s 用来累计 i 的各个位的和

        // 拆位：每次取出 t 的个位累加到 s，然后去掉 t 的个位
        while (t > 0)
        {
            s = s + t % 10;  // 取出 t 的个位，加进 s
            t = t / 10;      // 去掉 t 的个位
        }

        // 判断：各个位的和既不能被 2 整除，也不能被 5 整除
        if (s % 2 != 0 && s % 5 != 0)
        {
            cnt = cnt + 1;   // 满足条件，计数器加 1
        }
    }

    cout << cnt << endl;  // 输出满足条件的数的个数
    return 0;
}

复杂度分析

• 时间：循环从 1 数到 n，一共 n 次。每次都要拆位，n <= 9999，最多是 4 位数，所以每次拆位最多循环 4 次，可以看成常数。总时间复杂度是 O(n)，n 最大只有 9999，运行得非常快。
• 空间：只用了 n、cnt、i、t、s 这几个变量，没有开数组，空间复杂度是 O(1)。