B3756 [信息与未来 2021] 幸运数字

· · 题解

欢迎报名洛谷网校，期待和大家一起进步！

本题考察枚举和进制转换。

本题要求将数字转化为 5,7,9 进制。我们先回忆一下如何进行进制转换。例如要将一个正整数 x 转换为 5 进制，我们要做的操作是：

  1. 求出 x 除以 5 的余数 q；
  2. 将 x 除以 5，得到的结果向下取整；
  3. 如果 x>0，则回到第一步；
  4. 将得到的余数倒序排列，所得的结果就是 x 转换成 5 进制的结果；

因此，一个正整数在 5 进制下的表示没有 0，可以理解成每次除以 5 得到的余数 q 从来不出现 0。对于 7,9 进制的表示也是同理。

因此，我们可以编写一个函数 bool check(int x, int base)，表示正整数 x 在 \mathit{base} 进制下的表示是否不含有 0。返回值为 true，则说明不含有；返回值为 false，则说明含有。

bool check(int x, int base) {
    while (x) {
        if (x % base == 0)
            return false;
        x /= base;
    }
    return true;
}

接着在主程序中，只用将枚举的 i 代入 check 函数三次，即可得到答案：

for (int i = a; i <= b; i++) {
    if (check(i, 5) && check(i, 7) && check(i, 9))
        ans++;
}