OneCoder Avatar
OneCodercoderli.com · 937 篇博文
【GESP】C++一级练习BCQM3040,初识条件语句if,求幸运数📷 题解插图

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

📅 2024-10-08·✍️ OneCoder·计算中...·⏱️ 4 分钟
#GESP#C++#基础语句

到目前为止,应该是第一道可能需要用到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的值即可。

代码参考-从大往小遍历

CPP
#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)。

代码参考-从小往大遍历

CPP
#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,即可得到答案。

代码参考-直接计算

CPP
#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;           // 程序正常结束
}

💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745)Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder (lihongzheshuai)

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

💬 读者留言与交流

0 条讨论
✨ 支持 Markdown 语法格式
还没有留言,快来成为第一个讨论者吧!