A. FizzBuzz 变种版 详细题解

题目理解

我们需要统计在 $[0, n]$ 范围内，有多少个整数 $i$ 满足：

$$i \bmod 3 = i \bmod 5$$

关键观察：

• $0$ 总是满足条件，因为 $0 \bmod 3 = 0$，$0 \bmod 5 = 0$。
• 对于一般的 $i$，我们要求两个余数相等。

---

数学推导

设 $i \bmod 3 = i \bmod 5 = r$，其中 $0 \le r \le 2$（因为模 $3$ 的余数只能是 $0,1,2$）。

那么：

$$i \equiv r \pmod{3}$$ $$i \equiv r \pmod{5}$$

这意味着：

$$i - r \text{ 能被 } 3 \text{ 和 } 5 \text{ 整除}$$ $$i - r \text{ 能被 } \mathrm{lcm}(3,5) = 15 \text{ 整除} $$

所以：

$$i = r + 15k \quad (k \ge 0)$$

对于 $r = 0,1,2$，我们得到三个等差数列：

• $r = 0$：$0, 15, 30, 45, \dots$
• $r = 1$：$1, 16, 31, 46, \dots$
• $r = 2$：$2, 17, 32, 47, \dots$

---

结论

每 $15$ 个连续整数中，恰好有 $3$ 个满足条件（即 $15k, 15k+1, 15k+2$，其中 $k \ge 0$）。

---

计数公式

设 $q = \lfloor \frac{n}{15} \rfloor$，$r = n \bmod 15$（这里 $r$ 是余数，注意与上面的 $r$ 不同）。

完整周期部分：

从 $0$ 到 $15q - 1$，有 $q$ 个完整的长度为 $15$ 的区间，每个区间贡献 $3$ 个满足条件的数。
因此完整周期部分有 $3q$ 个数。

剩余部分：

剩余部分是从 $15q$ 到 $n$，共 $r+1$ 个数。
我们需要检查这些数中哪些满足条件。

这些数是：

$$15q,\ 15q+1,\ 15q+2,\ \dots,\ 15q+r$$

因为 $15q \bmod 15 = 0$，所以：

• $15q$ 对应 $r=0$ 的情况，满足条件
• $15q+1$ 对应 $r=1$ 的情况，满足条件
• $15q+2$ 对应 $r=2$ 的情况，满足条件
• $15q+3$ 对应 $r=3$，但 $3 \bmod 3 = 0$，$3 \bmod 5 = 3$，不相等
• 以此类推...

实际上，我们只需要检查 $j = 0,1,\dots,r$ 是否满足 $j \bmod 3 = j \bmod 5$。
因为 $15q + j \equiv j \pmod{3}$ 且 $\equiv j \pmod{5}$。

最终公式：

$$\text{ans} = 3 \times \left\lfloor \frac{n}{15} \right\rfloor + \text{count\_remainder}(n \bmod 15) $$

其中 $\text{count\_remainder}(m)$ 表示在 $0,1,\dots,m$ 中满足 $j \bmod 3 = j \bmod 5$ 的个数。

---

剩余部分查找表

$m = n \bmod 15$，$m$ 从 $0$ 到 $14$：

$m$	满足条件的 $j$	个数
0		1
1	0,1	2
2	0,1,2	3
3
4
5
6
7
8
9
10
11
12
13
14

观察发现，除了 $m=0,1,2$ 时有特殊情况，当 $m \ge 2$ 时都是 $3$ 个。
实际上更精确地说：

• 如果 $m=0$：剩余部分有 $\{0\}$，共 $1$ 个
• 如果 $m=1$：剩余部分有 $\{0,1\}$，共 $2$ 个
• 如果 $m \ge 2$：剩余部分包含 $\{0,1,2\}$，共 $3$ 个

但注意：当 $m=2$ 时，剩余部分就是 $\{0,1,2\}$，正好 $3$ 个。

所以：

$$\text{count\_remainder}(m) = \min(m+1, 3)$$

更准确地说是 $\min(m,2) + 1$？我们验证：

• $m=0$：$\min(0,2)+1 = 1$ ✓
• $m=1$：$\min(1,2)+1 = 2$ ✓
• $m=2$：$\min(2,2)+1 = 3$ ✓
• $m=3$：$\min(3,2)+1 = 3$ ✓

但注意 $m=3$ 时，剩余数是 $\{0,1,2,3\}$，其中 $0,1,2$ 满足，$3$ 不满足，共 $3$ 个，公式成立。

---

简化公式

$$\text{ans} = 3 \times \left\lfloor \frac{n}{15} \right\rfloor + \min\left(n \bmod 15 + 1,\ 3\right) $$

更简单的写法：

$$\text{ans} = 3 \times \left\lfloor \frac{n}{15} \right\rfloor + \min( (n \bmod 15) + 1,\ 3) $$

等价地：

$$\text{ans} = 3 \times \left\lfloor \frac{n}{15} \right\rfloor + \min( n \bmod 15,\ 2) + 1 $$

因为 $\min(m+1,3) = \min(m,2) + 1$。

---

标程验证

给定的 Python 代码：

t = int(input())
for i in range(t):
    n = int(input())
    ans = 3 * (n // 15)
    n %= 15
    for j in range(n + 1):
        if j % 3 == j % 5:
            ans += 1
    print(ans)

这个代码：

1. 先计算完整周期数 $3 \times \lfloor n/15 \rfloor$
2. 然后对剩余部分 $0$ 到 $n \% 15$ 逐个判断，累加满足条件的个数
3. 复杂度 $O(t \times 15)$，完全可行

---

复杂度分析

• 每个测试用例 $O(1)$ 计算（若用公式）
• 总时间复杂度 $O(t)$，可以轻松处理 $t \le 10^4$

---

最终公式代码实现（C++）

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long n;
        cin >> n;
        
        long long ans = 3 * (n / 15) + min(n % 15 + 1, 3LL);
        // 等价写法： ans = 3 * (n / 15) + min(n % 15, 2) + 1;
        
        cout << ans << endl;
    }
    
    return 0;
}

---

验证示例

以 $n=15$ 为例：

• $15/15 = 1$，完整周期贡献 $3 \times 1 = 3$
• $15 \% 15 = 0$，$\min(0+1,3)=1$
• 总答案 $3+1=4$，匹配输出

以 $n=5$ 为例：

• $5/15 = 0$，贡献 $0$
• $5 \% 15 = 5$，$\min(5+1,3)=3$
• 总答案 $3$，匹配输出 $\{0,1,2\}$

以 $n=0$ 为例：

• $0/15 = 0$，贡献 $0$
• $0 \% 15 = 0$，$\min(0+1,3)=1$
• 总答案 $1$，匹配输出 $\{0\}$

---

总结

核心思想是发现 $i \bmod 3 = i \bmod 5$ 当且仅当 $i \equiv 0,1,2 \pmod{15}$，然后利用周期性快速计数，避免 $O(n)$ 的逐个判断。