13108.情报站

题目分析

我们需要统计区间 ([A, B]) 中满足两个条件的整数个数：

1. 是 7 的倍数；
2. 是 奇数。

换句话说，我们要找所有满足 (x \bmod 7 = 0) 且 (x \bmod 2 \neq 0) 的整数 (x)。

7 的倍数可以写成 (7 \times k)，当 (k) 为奇数时，(7k) 才是奇数。因此满足条件的数实际上是 7 的奇数倍，即：
[
x = 7, 21, 35, 49, \ldots
]
这些数恰好构成一个等差数列：首项为 7，公差为 (14)（因为相邻两个 7 的奇数倍相差 (7\times 2 = 14)）。
也可以写成通项公式：(x = 14t + 7)（(t) 为非负整数）。

于是问题转化为：求区间 ([A, B]) 中形如 (14t + 7) 的整数个数。

解题思路

方法一：循环统计（参考代码做法）

由于数据范围上限只有 (10^7)，最坏情况下循环次数约为 (\frac{10^7}{14} \approx 7 \times 10^5)，完全可以在 1 秒内完成。

具体步骤：

1. 找到区间内第一个满足条件的数 start：
   • 先将 A 调整到第一个大于等于 A 的 7 的倍数；
   • 如果该数是偶数，则再加 7 使其变为奇数（同时也是下一个 7 的倍数）。
2. 从 start 开始，每次增加 14（保证依然是 7 的倍数且为奇数），遍历到不超过 B 为止，每遇到一个数就计数一次。
3. 输出计数值。

方法二：数学公式（O(1)）

可以直接利用等差数列的项数公式：

• 找到第一个 (\ge A) 且形如 (14t+7) 的数，记作 (L)；
• 找到最后一个 (\le B) 且形如 (14t+7) 的数，记作 (R)；
• 如果 (L > B)，答案为 0；否则答案为 (\displaystyle \frac{R - L}{14} + 1)。

两种方法都能正确求解，参考代码选择了容易理解的循环方法。

算法说明（循环方法）

1. 读入 (A, B)。
2. 计算起点：
   • 若 (A) 本身不是 7 的倍数，则 start = A + (7 - A % 7)；
   • 若 start 是偶数，则 start += 7（因为加 7 后奇偶性反转，且仍是 7 的倍数）。
3. 使用 for 循环，初始化 i = start，步长为 14，循环条件 i <= B，每迭代一次计数器加 1。
4. 输出计数器的值。

为什么步长是 14？
因为每增加 14，数仍然是 7 的倍数（14 = 2×7），同时奇偶性保持不变（14 是偶数）。所以从一个奇数 7 的倍数开始，每次加 14 得到的仍然是奇数 7 的倍数。

时间复杂度分析

• 参考代码的循环每次增加 14，循环次数约为 (\frac{B - A}{14}) 次，最坏情况下约为 (7 \times 10^5) 次，每次操作 O(1)，总时间复杂度为 O(区间长度/14)，对于 (10^7) 的数据规模非常宽裕。
• 如果使用方法二，则可以直接 O(1) 计算，但本题数据范围下循环方法已经足够高效且易于理解。

参考代码解释

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int A, B;
6    cin >> A >> B;
7    
8    int count = 0;
9    // 找到第一个 >= A 且是 7 的倍数的数
10    int start = A;
11    if (start % 7 != 0) {
12        start = A + (7 - A % 7);
13    }
14    // 如果该数是偶数，再加 7 得到奇数
15    if (start % 2 == 0) {
16        start += 7;  // 加7后奇偶性改变，且仍是7的倍数
17    }
18    
19    // 步长14保证了每次迭代得到的都是奇数且是7的倍数
20    for (int i = start; i <= B; i += 14) {
21        count++;
22    }
23    
24    cout << count << endl;
25    return 0;
26}

代码细节解读：

• start = A + (7 - A % 7)：当 A % 7 != 0 时，这个表达式可以求出第一个大于等于 A 的 7 的倍数。例如 A=10，10%7=3，7-3=4，10+4=14，正是第一个 7 的倍数。
• if (start % 2 == 0) start += 7;：如果 start 是偶数，加上 7 后变为奇数，同时因为 7 是 7 的倍数，start + 7 依然是 7 的倍数。例如 start=14（偶数），加 7 得 21，满足条件。
• 循环中 i += 14：确保每次增加后仍然是一个奇数 7 的倍数。计数的次数恰好就是答案。

拓展延伸

本题也可以完全不用循环，用数学公式一行求解：
找到第一个符合条件的数 L，然后计算 (B - L) / 14 + 1（需判断 L > B 的情况）。感兴趣的读者可以自行实现，比较两种方法的异同。

---

这样就完成了对“情报站”题目的详细解析，希望对大家理解区间统计与等差数列有所帮助。