求满足条件的整数个数 - 入门算法题

求满足条件的整数个数 - 入门算法题

比赛题目

时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 16MB，其他语言 32MB

描述

在1－n中，找出能同时满足用3除余2，用5除余3，用7除余2的所有整数的个数, 如果没有请输出0。

输入描述

输入一行，只有一个整数n(1<=n<=2000)

输出描述

输出只有一行（这意味着末尾有一个回车符号），包括1个整数。

用例输入 1

100 用例输出 1

1

解题思路：

题目要求找出在1到n中同时满足以下三个条件的整数个数：

1. 用3除余2
2. 用5除余3
3. 用7除余2

我们可以使用循环从1到n遍历每个整数，然后判断它是否满足上述三个条件。如果满足，计数器加1。最后返回计数器的值即可。

具体实现如下：

1. 读取输入的整数n。
2. 初始化计数器count为0。
3. 使用循环从1到n遍历每个整数i。
4. 判断i是否满足上述三个条件：
   • 如果i除以3的余数不等于2，跳过当前循环。
   • 如果i除以5的余数不等于3，跳过当前循环。
   • 如果i除以7的余数不等于2，跳过当前循环。
5. 如果i满足上述三个条件，计数器count加1。
6. 循环结束后，输出计数器count的值。

时间复杂度分析： 由于需要遍历从1到n的每个整数，时间复杂度为O(n)。

空间复杂度分析： 除了输入和输出的空间，只需要使用常量空间，所以空间复杂度为O(1)。

完整代码如下：

#include <iostream>
using namespace std;

int main() {
    // 读取输入的整数n
    int n;
    cin >> n;

    // 初始化计数器count为0
    int count = 0;

    // 遍历1到n的每个整数
    for (int i = 1; i <= n; i++) {
        // 判断i是否满足条件
        if (i % 3 == 2 && i % 5 == 3 && i % 7 == 2) {
            // 如果满足条件，计数器count加1
            count++;
        }
    }

    // 输出计数器count的值
    cout << count << endl;

    return 0;
}