【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;
    cin >> n >> k;
    for (int i = n; i >= 1; i--) {
        if (i % k == 0) {
            cout << i;
            break;
        }
    }
    return 0;
}

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

代码参考-从小往大遍历

#include <iostream>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    int max;
    for (int i = 1; i <= n; i++) {
        if (i % k == 0) {
            max = i;
        }
    }
    cout << max;
    return 0;
}

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

代码参考-直接计算

#include <iostream>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    cout << n / k * k;
    return 0;
}

---

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