【GESP】C++一级练习BCQM3040，初识条件语句if，求幸运数

到目前为止，应该是第一道可能需要用到if语句的题目（后来发现也可以不用），也算刚刚接近GESP 1级真题水平的题目，值得一做。

BCQM3040

题目要求

描述

A同学认为自己的幸运数是不超过N的非负整数里能被K整除的最大的数，你能帮他的算幸运数吗？

输入

输入—行，包含两个整数N,K(1 ≤ N,K ≤ 2×10^9)。

输出

输出—行，包含一个整数，表示幸运数。

输入样例

3 2

输出样例

2

---

题目分析

要找不超过N的，能被K整除的最大的数。即 该数 % K == 0，且最大。那么我们只要从最大的N开始循环遍历往1找，判断每个数 % K 是否等于0即可。第一个满足条件的数，就是最大的数。

此外，根据题目的输入条件N, K <= 2 * 10^9，属于int类型的数据范围，因此用int类型变量去存储N,K的值即可。

代码参考-从大往小遍历

#include <iostream>
using namespace std;
int main() {
    int n, k;               // 定义变量n存储上限，k存储除数
    cin >> n >> k;          // 从标准输入读取n和k的值
    // 从n开始倒序遍历到1，寻找能被k整除的最大数
    for (int i = n; i >= 1; i--) {
        if (i % k == 0) {   // 若当前数i能被k整除，则i即为所求幸运数
            cout << i;      // 输出该幸运数
            break;          // 找到后立即退出循环
        }
    }
    return 0;               // 程序正常结束
}

为了加强练习，我还让孩子编写了一个从1开始查找的解法，区别在于从1开始，第一个满足条件的数不是最大的数，最后一个才是，因此要用一个中间变量去保存遍历中符合条件的数。因为数在逐步增大，因此每查到一个，更新该变量的值即可，直到循环完成，此时就是最大的符合条件的数。显然，该方法遍历的次数一定比之前的从大往小遍历次数多，虽然从时间复杂度上看，都是O(n)。

代码参考-从小往大遍历

#include <iostream>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;          // 读取上限N和除数K
    int max;                // 用于记录当前找到的最大幸运数
    for (int i = 1; i <= n; i++) {
        if (i % k == 0) {   // 若i能被K整除，则i是一个候选幸运数
            max = i;        // 更新最大幸运数（因为i递增，故每次直接覆盖即可）
        }
    }
    cout << max;            // 输出最终找到的最大幸运数
    return 0;
}

其实还有一个更直接快速的方法，就是利用整数计算取整的特性直接 N / K * K，即可得到答案。

代码参考-直接计算

#include <iostream>
using namespace std;
int main() {
    int n, k;           // 定义两个整数变量n和k，分别表示上限N和除数K
    cin >> n >> k;      // 从标准输入读取n和k的值
    cout << n / k * k;  // 利用整数除法向下取整的特性，直接计算不超过n且能被k整除的最大数
    return 0;           // 程序正常结束
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号