PAT 乙级 1087——有多少不同的值。题面很短：给一个正整数 N，把 1 到 N 每个整数 i 都算一遍 ⌊i/2⌋ + ⌊i/3⌋ + ⌊i/5⌋，最后输出这些结果里不同值的个数。第一次看到这道题，多数人第一反应是“这不就是模拟吗”，可真正动手之后会发现它考的不是手速，而是两件事：怎么优雅地给一大堆结果去重，以及能不能看穿这个函数只会单调上涨。这篇把我做这道题时的三种解法、踩过的坑、顺手推出来的 O(1) 容斥公式，一次性说清楚，适合刚刷完乙级前半段、准备往“观察规律”方向进阶的选手。1. 题目到底在问什么1.1 把题目翻译成人话题目原文一般长这样：对任意自然数 i，计算 ⌊i/2⌋ + ⌊i/3⌋ + ⌊i/5⌋，i 从 1 取到 N，问一共能得到多少个不同的值。翻译过来就是三件事。第一，把 1 到 N 的每个数都代进那个式子，得到 N 个整数结果。第二，如果两个 i 算出来的结果一样，它们只能算同一个值。第三，最后输出的是“不同值”的个数，不是结果的个数，也不是某个结果具体多大。这里要特别提醒一点：⌊x⌋ 是向下取整，但对正整数做除法的时候，C/C++ 的整数除法本身就是向下取整，所以整个题完全不需要碰浮点数。很多人一看到向下取整就去调 floor 函数，结果引入精度问题，属于给自己加戏。这道题数据范围不大，N 一般也就是 10^4 量级，所以它从来不是性能竞赛。真正的考点藏在“不同值”三个字里：怎么去重，以及能不能不看代码就猜出答案的大致范围。1.2 输入输出的规矩输入就一行，一个正整数 N。输出也是一个整数，末尾要换行。PAT 的老规矩在这里同样适用：输出格式多一个空格、少一个换行，都可能直接 WA。我习惯用 scanf 和 printf，输入量不大，cin/cout 把同步关掉也没问题，但既然一行就能读完，用 C 风格 IO 最稳。自测的时候可以拿 N=2017 当基准，跑出来的答案应该是 1480，这个数能帮你快速确认代码逻辑没写歪。1.3 这道题真正想考的东西表面上看是一道枚举题，实际上它一次塞了三个知识点。第一是集合去重。N 个结果里有很多重复值，用 set 或者标记数组把重复项滤掉，是最直接的解法。第二是单调性观察。f(i) 这个函数随着 i 增大只会不变或变大，这个性质一旦看穿，很多代码都能简化。第三是容斥原理。如果把问题抽象成“统计增量大于 0 的次数”，答案可以直接用包含排除推成一个常数时间公式。乙级题常见的一个特征是：数据范围小到暴力分明能过，但出题人想让你在“明明能过”的过程里顺带建立几个好习惯。1087 就是典型代表。2. 解题思路：从无脑枚举到抓住单调性2.1 第一版：暴力枚举加集合去重最朴素的写法，开一个 set，循环 i 从 1 到 N，把每个计算结果插进去，最后输出 set 的大小。#include <cstdio> #include <set> using namespace std; int main() { int N; scanf("%d", &N); set<int> s; for (int i = 1; i <= N; i++) { s.insert(i / 2 + i / 3 + i / 5); } printf("%d\n", (int)s.size()); return 0; }set 底层是红黑树，插入一次 O(logN)，去重是天然完成的。N 只有 10^4 量级的时候，N 次 logN 的插入连 1 毫秒都用不到。这版代码唯一的“技术含量”就是想到用 set 而不是自己写一个手动去重。很多人第一反应是开一个数组当桶，把每个结果对应的下标置 1，这也没问题，但 set 的优点是根本不用管值域上界在哪，插就完了。麻烦的地方只有一个：size() 返回的是 size_t，直接 printf 用 %d 会类型不匹配，记得强转成 int。2.2 关键观察：f(i) 只会涨不会跌暴力版能过，但真正让这道题有意思的是下面这个观察。把 f(i) 和 f(i-1) 相减看增量：f(i) - f(i-1)= (⌊i/2⌋ - ⌊(i-1)/2⌋)(⌊i/3⌋ - ⌊(i-1)/3⌋)(⌊i/5⌋ - ⌊(i-1)/5⌋)每一项当且仅当 i 能被对应的除数整除时才会增加 1，否则就是 0。所以这个差值只可能是 0、1、2、3 四种情况。这句话信息量很大。第一，f 单调不减，永远不会倒退，新值只会在增量大于 0 的时候产生。第二，两个不同值之间的最大空隙是 3，因为增量最多一次跳 3。第三，整个序列的值都集中在 0 到 f(N) 之间，不会稀疏到天上去。最有意思的是 i=6 这一跳。f(5) = ⌊5/2⌋ + ⌊5/3⌋ + ⌊5/5⌋ = 2 + 1 + 1 = 4，而 f(6) = 3 + 2 + 1 = 6，直接跳过了 5。所以从 1 到 6 得到的值是 0、1、2、3、4、6，一共 6 个。如果你天真地以为“i 每加 1，结果就加 1”，到这里就翻车了。这个例子也解释了为什么必须用集合去重：重复不是唯一的问题，还有跳跃。2.3 数学版本：用容斥把答案算出来单调性观察再往前走一步，就能得到一个完全不需要枚举的公式。因为每个新值只在增量大于 0 的步数产生，所以答案等于 1 加上“从 2 到 N 中能被 2、3、5 至少一个整除的数的个数”。为什么是 1？因为 i=1 时 f(1)=0，这是第一个值，必须先算上。设 A 表示 1 到 N 中不能被 2、3、5 整除的数的个数，那么从 2 到 N 中能被 2、3、5 至少一个整除的个数就是 (N-1) - (A-1)，注意数字 1 本身也不能被 2、3、5 整除，所以它在 A 里，得先减掉。整理一下：答案 = 1 + (N-1) - (A-1) = N - A + 1而 A 可以用容斥原理直接算：A = N - (N/2 + N/3 + N/5) + (N/6 + N/10 + N/15) - N/30这里所有除法都是整数除法，也就是向下取整。把 A 代回去化简，得到：答案 = N/2 + N/3 + N/5 - N/6 - N/10 - N/15 + N/30 + 1拿小 N 验证一下，这个公式非常稳：N枚举得到的集合结果公式结果1{0}112{0,1}223{0,1,2}334{0,1,2,3}445{0,1,2,3,4}556{0,1,2,3,4,6}667{0,1,2,3,4,6}66N=2017 时，代入算一遍，答案正好是 1480，可以作为对拍基准。2.4 三种思路怎么选方案时间复杂度空间复杂度代码量适用场景set 去重O(N log N)O(N)最短通用，最不容易写错标记数组O(N)O(N)短值域可估算且不大容斥公式O(1)O(1)最短大 N、面试追问、性能极致考试的时候我推荐直接写 set 版，30 秒搞定，逻辑不可能出错。标记数组版适合想省一点常数的人。公式版更多是用来秀理解或者应付“N 变成 10^18 怎么办”这种扩展问题。务实一点说：先保证能过，再想着怎么优雅。3. 代码实现与细节处理3.1 C++ 的 set 写法set 写法上面已经给了，几个容易出问题的地方单独强调一遍。第一，头文件要包含和 ，别漏。第二，printf 里输出 (int)s.size()，不转类型在部分编译器下会报警告，虽然一般也能跑对，但 PAT 环境下最好干干净净。第三，循环变量 i 从 1 开始，题目说的是“1 到 N”，别手滑从 0 开始。从 0 开始其实也能过，因为 f(0)=0 和 f(1)=0 重复，set 去重后结果一样，但从 0 开始会让后面推公式时思路混乱。3.2 用标记数组的写法如果不想用 set，可以开一个标记数组，把每个计算结果当成下标置 1，最后统计有多少个下标被置过 1。#include <cstdio> #include <vector> using namespace std; int main() { int N; scanf("%d", &N); int maxValue = N / 2 + N / 3 + N / 5; vector<char> vis(maxValue + 1, 0); for (int i = 1; i <= N; i++) { vis[i / 2 + i / 3 + i / 5] = 1; } int ans = 0; for (int v = 0; v <= maxValue; v++) { if (vis[v]) ans++; } printf("%d\n", ans); return 0; }关键在于数组大小。i/2 + i/3 + i/5 的最大值出现在 i=N 时，也就是 maxValue = N/2 + N/3 + N/5，所以数组开 maxValue+1 就一定不会越界。算个上界：N/2 + N/3 + N/5 ≤ 31N/30，约等于 1.033N，也就是说标记数组大概是 N 的 1.04 倍大小，非常小。这里我用的是 vector ，不是 vector 。这俩在语义上有区别：vector 是压位的，每个元素只占 1 bit，读写行为跟普通 bool 数组不完全一样，新手容易踩坑。这种只需要标记 0/1 的场景，用 vector 最踏实。如果开全局数组，默认就是全 0，省掉初始化这一步，但要注意全局数组不能开太离谱，10^6 级别以内都没问题。3.3 O(1) 公式版本公式推导在前面已经给了，代码短到不好意思：#include <cstdio> int main() { int N; scanf("%d", &N); int ans = N / 2 + N / 3 + N / 5 - N / 6 - N / 10 - N / 15 + N / 30 + 1; printf("%d\n", ans); return 0; }这个版本成立的前提是“整数除法等于向下取整”。C/C++ 对正整数就是这样的行为，但如果你把代码改成浮点除法再 floor，结果不仅慢，还可能因为浮点精度问题出错。比如某个边界值在浮点下变成 0.9999999，floor 下来就少 1，这种 bug 特别隐蔽。还有一点，N/6 表示的是同时能被 2 和 3 整除的数，也就是 6 的倍数，N/10 是 2 和 5 的公倍数，N/15 是 3 和 5 的公倍数，最后 N/30 是三个数的最小公倍数的倍数。容斥的符号规律是：单数个条件减，双数个条件加，三条件全满足的再减回来。3.4 Python 一行集合推导式虽然 PAT 判题环境主流是 C/C++，但 Python 版本非常适合本地对拍和验证公式。n = int(input()) vals = {i // 2 + i // 3 + i // 5 for i in range(1, n + 1)} print(len(vals))这里有两个细节。第一，必须用 // 整数除法，用 / 会得到浮点数，集合里存的就全是带小数点的数，答案直接错。第二，集合推导式会自动去重，所以 len 就是答案。这个版本和 C++ 的 set 版逻辑完全一致，我在本地经常拿它跟公式版对拍，两边输出一致才敢把公式版交上去。4. 做题时容易踩的坑4.1 0 到底算不算一个值f(1) = ⌊1/2⌋ + ⌊1/3⌋ + ⌊1/5⌋ = 0 + 0 + 0 = 0，所以 0 是结果集合里的合法元素，必须算进去。有些人看到题目里写“自然数”，下意识觉得 0 不是自然数，就把 0 从结果里排除了，这是理解错了。题目说 i 取自然数，说的是输入范围，不是输出范围。输出是计算结果，f(1) 算出来就是 0，这个 0 就是集合的一员。用 set 写不会踩这个坑，因为 set 不会因为你“觉得 0 不该出现”就帮你删掉；但如果你手写计数，很容易在初始化答案时忘了把 0 算上，答案就会少 1。4.2 循环从 0 开始还是从 1 开始题目明确是 i 从 1 到 N，所以循环就从 1 开始。从 0 开始虽然因为 set 去重最终答案一样，但会带来两个隐患：一是 f(0)=0 和 f(1)=0 重复，如果你不是用 set 而是用“每个 i 产生一个新值”的计数逻辑，就会多算；二是会对你的思维产生污染，后面推公式的时候，你会发现公式的“+1”到底加在哪，跟循环起点纠缠不清。所以我的建议很朴素：题目怎么写，代码就怎么写，别自作聪明改起点。4.3 标记数组开多大才不会越界标记数组的越界问题是这道题最常见的运行时错误来源。正确的大小是 maxValue = N/2 + N/3 + N/5，然后把数组开到 maxValue+1。因为下标从 0 开始，最大可能的下标就是 maxValue。有的同学图省事直接开 N 大小，在 N 比较小的时候可能侥幸没炸，但 N 一旦上万，i/2+i/3+i/5 会比 N 大，数组越界，本地可能不报错，OJ 上直接 RE。如果你实在懒得算上界，就学 set 版，完全避开这个问题。4.4 输出比 N 大？多半是根本没去重答案最多是 N，这是必然的，因为 N 个输入最多产生 N 个不同的输出。如果你跑出来的答案比 N 还大，不用怀疑，一定是把每个 i 的结果都当成新值累加了，也就是说根本没去重。检查方法很简单：本地跑 N=6，正确集合应该是 {0,1,2,3,4,6}，是 6 个；如果代码输出 7 或者更大，说明你把 i=6 那个跳过的 5 也算进去了，或者把重复的 6 算了两次。这种小规模手算验证，比肉眼盯着代码找 bug 快得多。4.5 超时焦虑怎么破这道题 set 版在 10^4 量级下运行时间是微秒到毫秒级别，完全不需要担心超时。真正值得思考的是：什么情况下需要考虑优化？如果 N 变成 10^7，set 的 O(N logN) 会开始吃力；如果 N 变成 10^18，连数组都开不下。这时候单调性和容斥公式就派上用场了。我自己的判断标准是：当 N 超过 10^6 或者内存紧张时，才值得把暴力版换成数学版。PAT 乙级这道题远没到那个程度，但知道这个判断标准，以后遇到同类问题就不会慌。5. 从这道题带走的经验5.1 遇到“数不同值”先问三个问题这道题给我的启发是：凡是遇到“计算 N 个结果，数一数有多少个不同值”这类问题，下手写代码前先快速问自己三个问题。第一，这个序列有没有单调性？如果结果只会递增，那么“新值”一定出现在增量大于 0 的位置，计数方式可以完全改变。第二，相邻两个值的增量有哪几种可能？如果只有有限的几种，说明值域是稠密的，可以用区间或者公式直接算。第三，能不能用集合论或者容斥把“不同值的个数”表达成另一个更简单的计数问题？这三个问题都答不上来的时候，set 永远是最后一道保险。但答得上来的时候，你往往能写出比“暴力+集合”漂亮得多的解法。5.2 “暴力先行、优化后置”的应试节奏刷题这么多年，我越来越认同一个观点：先写能过的版本，再想更优的版本。以这道题为例，set 版 30 秒写完，交了就是 AC。然后你再在草稿纸上推公式，推到一半发现推错了，也不影响分数。最怕的是上来就憋大招，想直接写 O(1) 公式，结果容斥某项符号写错，答案差一点，debug 半天才发现问题。我自己的习惯是：暴力版和公式版都写出来，本地用随机数据对拍。暴力版提供正确答案，公式版提供性能上限，两边输出一致才说明公式真的理解对了。这个习惯从乙级一直带到后面的题目，帮我省了无数次无意义的提交。5.3 换个除数，思路还成立吗最后留一个扩展思考。如果题目把除数从 2、3、5 改成 2、3、5、7，上面所有思路都还成立，只是容斥公式会从三项变成四项：先减单个整除的，再加两两公倍数的，再减三三公倍数的，最后加 2、3、5、7 四者公倍数的。每一项的符号是 (-1)^k，k 是同时整除的除数个数。再进一步，如果 f(i) 本身不是单调的，比如式子变成 ⌊i/2⌋ - ⌊i/3⌋ + ⌊i/5⌋，那么 set 就成了唯一简单可靠的方案，因为这时候“不同值的个数”和“增量大于 0 的次数”不再等价。这种举一反三的思考，才是刷一道题真正的收获。回到 1087 这道题本身，我个人实际做题时的体会是：set 版解决的是“怎么算对”，单调性解决的是“为什么是这个答案”，容斥公式解决的是“能不能更快”。三个层次递进下来，一道乙级小题也能嚼出不少东西。最后再分享一个小技巧：任何一道“算 N 个值再数不同值”的题，我都建议先用 set 写个标尺代码，再去推数学结论。标尺代码五分钟能写完，后续所有优化版本都可以拿它当基准对拍。希望这篇能让你在刷到 1087 的时候，少绕两个弯。
PAT 乙级 1087——有多少不同的值。题面很短：给一个正整数 N，把 1 到 N 每个整数 i 都算一遍 ⌊i/2⌋ + ⌊i/3⌋ + ⌊i/5⌋，最后输出这些结果里不同值的个数。第一次看到这道题，多数人第一反应是“这不就是模拟吗”，可真正动手之后会发现它考的不是手速，而是两件事：怎么优雅地给一大堆结果去重，以及能不能看穿这个函数只会单调上涨。这篇把我做这道题时的三种解法、踩过的坑、顺手推出来的 O(1) 容斥公式，一次性说清楚，适合刚刷完乙级前半段、准备往“观察规律”方向进阶的选手。1. 题目到底在问什么1.1 把题目翻译成人话题目原文一般长这样：对任意自然数 i，计算 ⌊i/2⌋ + ⌊i/3⌋ + ⌊i/5⌋，i 从 1 取到 N，问一共能得到多少个不同的值。翻译过来就是三件事。第一，把 1 到 N 的每个数都代进那个式子，得到 N 个整数结果。第二，如果两个 i 算出来的结果一样，它们只能算同一个值。第三，最后输出的是“不同值”的个数，不是结果的个数，也不是某个结果具体多大。这里要特别提醒一点：⌊x⌋ 是向下取整，但对正整数做除法的时候，C/C++ 的整数除法本身就是向下取整，所以整个题完全不需要碰浮点数。很多人一看到向下取整就去调 floor 函数，结果引入精度问题，属于给自己加戏。这道题数据范围不大，N 一般也就是 10^4 量级，所以它从来不是性能竞赛。真正的考点藏在“不同值”三个字里：怎么去重，以及能不能不看代码就猜出答案的大致范围。1.2 输入输出的规矩输入就一行，一个正整数 N。输出也是一个整数，末尾要换行。PAT 的老规矩在这里同样适用：输出格式多一个空格、少一个换行，都可能直接 WA。我习惯用 scanf 和 printf，输入量不大，cin/cout 把同步关掉也没问题，但既然一行就能读完，用 C 风格 IO 最稳。自测的时候可以拿 N=2017 当基准，跑出来的答案应该是 1480，这个数能帮你快速确认代码逻辑没写歪。1.3 这道题真正想考的东西表面上看是一道枚举题，实际上它一次塞了三个知识点。第一是集合去重。N 个结果里有很多重复值，用 set 或者标记数组把重复项滤掉，是最直接的解法。第二是单调性观察。f(i) 这个函数随着 i 增大只会不变或变大，这个性质一旦看穿，很多代码都能简化。第三是容斥原理。如果把问题抽象成“统计增量大于 0 的次数”，答案可以直接用包含排除推成一个常数时间公式。乙级题常见的一个特征是：数据范围小到暴力分明能过，但出题人想让你在“明明能过”的过程里顺带建立几个好习惯。1087 就是典型代表。2. 解题思路：从无脑枚举到抓住单调性2.1 第一版：暴力枚举加集合去重最朴素的写法，开一个 set，循环 i 从 1 到 N，把每个计算结果插进去，最后输出 set 的大小。#include <cstdio> #include <set> using namespace std; int main() { int N; scanf("%d", &N); set<int> s; for (int i = 1; i <= N; i++) { s.insert(i / 2 + i / 3 + i / 5); } printf("%d\n", (int)s.size()); return 0; }set 底层是红黑树，插入一次 O(logN)，去重是天然完成的。N 只有 10^4 量级的时候，N 次 logN 的插入连 1 毫秒都用不到。这版代码唯一的“技术含量”就是想到用 set 而不是自己写一个手动去重。很多人第一反应是开一个数组当桶，把每个结果对应的下标置 1，这也没问题，但 set 的优点是根本不用管值域上界在哪，插就完了。麻烦的地方只有一个：size() 返回的是 size_t，直接 printf 用 %d 会类型不匹配，记得强转成 int。2.2 关键观察：f(i) 只会涨不会跌暴力版能过，但真正让这道题有意思的是下面这个观察。把 f(i) 和 f(i-1) 相减看增量：f(i) - f(i-1)= (⌊i/2⌋ - ⌊(i-1)/2⌋)(⌊i/3⌋ - ⌊(i-1)/3⌋)(⌊i/5⌋ - ⌊(i-1)/5⌋)每一项当且仅当 i 能被对应的除数整除时才会增加 1，否则就是 0。所以这个差值只可能是 0、1、2、3 四种情况。这句话信息量很大。第一，f 单调不减，永远不会倒退，新值只会在增量大于 0 的时候产生。第二，两个不同值之间的最大空隙是 3，因为增量最多一次跳 3。第三，整个序列的值都集中在 0 到 f(N) 之间，不会稀疏到天上去。最有意思的是 i=6 这一跳。f(5) = ⌊5/2⌋ + ⌊5/3⌋ + ⌊5/5⌋ = 2 + 1 + 1 = 4，而 f(6) = 3 + 2 + 1 = 6，直接跳过了 5。所以从 1 到 6 得到的值是 0、1、2、3、4、6，一共 6 个。如果你天真地以为“i 每加 1，结果就加 1”，到这里就翻车了。这个例子也解释了为什么必须用集合去重：重复不是唯一的问题，还有跳跃。2.3 数学版本：用容斥把答案算出来单调性观察再往前走一步，就能得到一个完全不需要枚举的公式。因为每个新值只在增量大于 0 的步数产生，所以答案等于 1 加上“从 2 到 N 中能被 2、3、5 至少一个整除的数的个数”。为什么是 1？因为 i=1 时 f(1)=0，这是第一个值，必须先算上。设 A 表示 1 到 N 中不能被 2、3、5 整除的数的个数，那么从 2 到 N 中能被 2、3、5 至少一个整除的个数就是 (N-1) - (A-1)，注意数字 1 本身也不能被 2、3、5 整除，所以它在 A 里，得先减掉。整理一下：答案 = 1 + (N-1) - (A-1) = N - A + 1而 A 可以用容斥原理直接算：A = N - (N/2 + N/3 + N/5) + (N/6 + N/10 + N/15) - N/30这里所有除法都是整数除法，也就是向下取整。把 A 代回去化简，得到：答案 = N/2 + N/3 + N/5 - N/6 - N/10 - N/15 + N/30 + 1拿小 N 验证一下，这个公式非常稳：N枚举得到的集合结果公式结果1{0}112{0,1}223{0,1,2}334{0,1,2,3}445{0,1,2,3,4}556{0,1,2,3,4,6}667{0,1,2,3,4,6}66N=2017 时，代入算一遍，答案正好是 1480，可以作为对拍基准。2.4 三种思路怎么选方案时间复杂度空间复杂度代码量适用场景set 去重O(N log N)O(N)最短通用，最不容易写错标记数组O(N)O(N)短值域可估算且不大容斥公式O(1)O(1)最短大 N、面试追问、性能极致考试的时候我推荐直接写 set 版，30 秒搞定，逻辑不可能出错。标记数组版适合想省一点常数的人。公式版更多是用来秀理解或者应付“N 变成 10^18 怎么办”这种扩展问题。务实一点说：先保证能过，再想着怎么优雅。3. 代码实现与细节处理3.1 C++ 的 set 写法set 写法上面已经给了，几个容易出问题的地方单独强调一遍。第一，头文件要包含和 ，别漏。第二，printf 里输出 (int)s.size()，不转类型在部分编译器下会报警告，虽然一般也能跑对，但 PAT 环境下最好干干净净。第三，循环变量 i 从 1 开始，题目说的是“1 到 N”，别手滑从 0 开始。从 0 开始其实也能过，因为 f(0)=0 和 f(1)=0 重复，set 去重后结果一样，但从 0 开始会让后面推公式时思路混乱。3.2 用标记数组的写法如果不想用 set，可以开一个标记数组，把每个计算结果当成下标置 1，最后统计有多少个下标被置过 1。#include <cstdio> #include <vector> using namespace std; int main() { int N; scanf("%d", &N); int maxValue = N / 2 + N / 3 + N / 5; vector<char> vis(maxValue + 1, 0); for (int i = 1; i <= N; i++) { vis[i / 2 + i / 3 + i / 5] = 1; } int ans = 0; for (int v = 0; v <= maxValue; v++) { if (vis[v]) ans++; } printf("%d\n", ans); return 0; }关键在于数组大小。i/2 + i/3 + i/5 的最大值出现在 i=N 时，也就是 maxValue = N/2 + N/3 + N/5，所以数组开 maxValue+1 就一定不会越界。算个上界：N/2 + N/3 + N/5 ≤ 31N/30，约等于 1.033N，也就是说标记数组大概是 N 的 1.04 倍大小，非常小。这里我用的是 vector ，不是 vector 。这俩在语义上有区别：vector 是压位的，每个元素只占 1 bit，读写行为跟普通 bool 数组不完全一样，新手容易踩坑。这种只需要标记 0/1 的场景，用 vector 最踏实。如果开全局数组，默认就是全 0，省掉初始化这一步，但要注意全局数组不能开太离谱，10^6 级别以内都没问题。3.3 O(1) 公式版本公式推导在前面已经给了，代码短到不好意思：#include <cstdio> int main() { int N; scanf("%d", &N); int ans = N / 2 + N / 3 + N / 5 - N / 6 - N / 10 - N / 15 + N / 30 + 1; printf("%d\n", ans); return 0; }这个版本成立的前提是“整数除法等于向下取整”。C/C++ 对正整数就是这样的行为，但如果你把代码改成浮点除法再 floor，结果不仅慢，还可能因为浮点精度问题出错。比如某个边界值在浮点下变成 0.9999999，floor 下来就少 1，这种 bug 特别隐蔽。还有一点，N/6 表示的是同时能被 2 和 3 整除的数，也就是 6 的倍数，N/10 是 2 和 5 的公倍数，N/15 是 3 和 5 的公倍数，最后 N/30 是三个数的最小公倍数的倍数。容斥的符号规律是：单数个条件减，双数个条件加，三条件全满足的再减回来。3.4 Python 一行集合推导式虽然 PAT 判题环境主流是 C/C++，但 Python 版本非常适合本地对拍和验证公式。n = int(input()) vals = {i // 2 + i // 3 + i // 5 for i in range(1, n + 1)} print(len(vals))这里有两个细节。第一，必须用 // 整数除法，用 / 会得到浮点数，集合里存的就全是带小数点的数，答案直接错。第二，集合推导式会自动去重，所以 len 就是答案。这个版本和 C++ 的 set 版逻辑完全一致，我在本地经常拿它跟公式版对拍，两边输出一致才敢把公式版交上去。4. 做题时容易踩的坑4.1 0 到底算不算一个值f(1) = ⌊1/2⌋ + ⌊1/3⌋ + ⌊1/5⌋ = 0 + 0 + 0 = 0，所以 0 是结果集合里的合法元素，必须算进去。有些人看到题目里写“自然数”，下意识觉得 0 不是自然数，就把 0 从结果里排除了，这是理解错了。题目说 i 取自然数，说的是输入范围，不是输出范围。输出是计算结果，f(1) 算出来就是 0，这个 0 就是集合的一员。用 set 写不会踩这个坑，因为 set 不会因为你“觉得 0 不该出现”就帮你删掉；但如果你手写计数，很容易在初始化答案时忘了把 0 算上，答案就会少 1。4.2 循环从 0 开始还是从 1 开始题目明确是 i 从 1 到 N，所以循环就从 1 开始。从 0 开始虽然因为 set 去重最终答案一样，但会带来两个隐患：一是 f(0)=0 和 f(1)=0 重复，如果你不是用 set 而是用“每个 i 产生一个新值”的计数逻辑，就会多算；二是会对你的思维产生污染，后面推公式的时候，你会发现公式的“+1”到底加在哪，跟循环起点纠缠不清。所以我的建议很朴素：题目怎么写，代码就怎么写，别自作聪明改起点。4.3 标记数组开多大才不会越界标记数组的越界问题是这道题最常见的运行时错误来源。正确的大小是 maxValue = N/2 + N/3 + N/5，然后把数组开到 maxValue+1。因为下标从 0 开始，最大可能的下标就是 maxValue。有的同学图省事直接开 N 大小，在 N 比较小的时候可能侥幸没炸，但 N 一旦上万，i/2+i/3+i/5 会比 N 大，数组越界，本地可能不报错，OJ 上直接 RE。如果你实在懒得算上界，就学 set 版，完全避开这个问题。4.4 输出比 N 大？多半是根本没去重答案最多是 N，这是必然的，因为 N 个输入最多产生 N 个不同的输出。如果你跑出来的答案比 N 还大，不用怀疑，一定是把每个 i 的结果都当成新值累加了，也就是说根本没去重。检查方法很简单：本地跑 N=6，正确集合应该是 {0,1,2,3,4,6}，是 6 个；如果代码输出 7 或者更大，说明你把 i=6 那个跳过的 5 也算进去了，或者把重复的 6 算了两次。这种小规模手算验证，比肉眼盯着代码找 bug 快得多。4.5 超时焦虑怎么破这道题 set 版在 10^4 量级下运行时间是微秒到毫秒级别，完全不需要担心超时。真正值得思考的是：什么情况下需要考虑优化？如果 N 变成 10^7，set 的 O(N logN) 会开始吃力；如果 N 变成 10^18，连数组都开不下。这时候单调性和容斥公式就派上用场了。我自己的判断标准是：当 N 超过 10^6 或者内存紧张时，才值得把暴力版换成数学版。PAT 乙级这道题远没到那个程度，但知道这个判断标准，以后遇到同类问题就不会慌。5. 从这道题带走的经验5.1 遇到“数不同值”先问三个问题这道题给我的启发是：凡是遇到“计算 N 个结果，数一数有多少个不同值”这类问题，下手写代码前先快速问自己三个问题。第一，这个序列有没有单调性？如果结果只会递增，那么“新值”一定出现在增量大于 0 的位置，计数方式可以完全改变。第二，相邻两个值的增量有哪几种可能？如果只有有限的几种，说明值域是稠密的，可以用区间或者公式直接算。第三，能不能用集合论或者容斥把“不同值的个数”表达成另一个更简单的计数问题？这三个问题都答不上来的时候，set 永远是最后一道保险。但答得上来的时候，你往往能写出比“暴力+集合”漂亮得多的解法。5.2 “暴力先行、优化后置”的应试节奏刷题这么多年，我越来越认同一个观点：先写能过的版本，再想更优的版本。以这道题为例，set 版 30 秒写完，交了就是 AC。然后你再在草稿纸上推公式，推到一半发现推错了，也不影响分数。最怕的是上来就憋大招，想直接写 O(1) 公式，结果容斥某项符号写错，答案差一点，debug 半天才发现问题。我自己的习惯是：暴力版和公式版都写出来，本地用随机数据对拍。暴力版提供正确答案，公式版提供性能上限，两边输出一致才说明公式真的理解对了。这个习惯从乙级一直带到后面的题目，帮我省了无数次无意义的提交。5.3 换个除数，思路还成立吗最后留一个扩展思考。如果题目把除数从 2、3、5 改成 2、3、5、7，上面所有思路都还成立，只是容斥公式会从三项变成四项：先减单个整除的，再加两两公倍数的，再减三三公倍数的，最后加 2、3、5、7 四者公倍数的。每一项的符号是 (-1)^k，k 是同时整除的除数个数。再进一步，如果 f(i) 本身不是单调的，比如式子变成 ⌊i/2⌋ - ⌊i/3⌋ + ⌊i/5⌋，那么 set 就成了唯一简单可靠的方案，因为这时候“不同值的个数”和“增量大于 0 的次数”不再等价。这种举一反三的思考，才是刷一道题真正的收获。回到 1087 这道题本身，我个人实际做题时的体会是：set 版解决的是“怎么算对”，单调性解决的是“为什么是这个答案”，容斥公式解决的是“能不能更快”。三个层次递进下来，一道乙级小题也能嚼出不少东西。最后再分享一个小技巧：任何一道“算 N 个值再数不同值”的题，我都建议先用 set 写个标尺代码，再去推数学结论。标尺代码五分钟能写完，后续所有优化版本都可以拿它当基准对拍。希望这篇能让你在刷到 1087 的时候，少绕两个弯。