NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 24 题

#include <stdio.h> 
int main() 
{ 
 int a, b, u, v, i, num;  
 scanf("%d%d%d%d", &a, &b, &u, &v); 
 num = 0; 
 for (i = a; i <= b; i++) 
if (((i % u) == 0) || ((i % v) == 0)) 
   num++; 
 printf("%d\n", num); 
 return 0; 
} 

输入：1 1000 10 15 输出：_________

这题本质就是数[1,1000]里能被10或15整除的个数。别急着敲代码，先用容斥原理：分别算10的倍数、15的倍数，再减去重复的30的倍数，马上就能得出答案133。

最容易掉进两个坑：一是把lcm(10,15)算成150，导致减去的交集少了，结果变成183；二是忘记容斥必须减交集，直接相加得166。记住，求“或”一定要减“且”，且必须用最小公倍数，不是最大公约数也不是随便乘一下。

这道题考查的是循环结构配合容斥原理求并集元素个数，属于初赛里非常经典的‘数论+编程’组合题。命题人故意给出一段看似普通的循环代码，其实是在考察你是否能透过代码看到背后的数学本质——统计区间内满足某种整除条件的数的个数。这类题目在NOIP提高组初赛中出现频率不低，2013年就是典型代表，而近年考频明显上升，2024年高达128题，2025年更是飙到158题，说明命题组越来越喜欢在代码阅读题里埋数论坑。

先说核心概念。题目要求统计从a到b之间，能被u或v整除的数的个数。这里的‘或’是数学上的并集概念，对应集合论里的|A∪B|。根据容斥原理，|A∪B| = |A| + |B| - |A∩B|。也就是说，要算能被10或15整除的数，得分别算能被10整除的数、能被15整除的数，再减去同时能被10和15整除的数（即交集A∩B）。

交集里的数必须同时是10和15的倍数，那不就是它们的最小公倍数吗？lcm(10,15)怎么算？用公式lcm(a,b) = a×b / gcd(a,b)。10和15的最大公约数是5，所以lcm(10,15) = 10×15 / 5 = 30。很多同学会在这里栽跟头，把lcm当成150，或者干脆手误写成gcd的结果，这都是命题人爱挖的坑。记住，求‘或’一定用最小公倍数，不是最大公约数，也不是随便乘一下。

接下来是具体计算。区间是[1,1000]，求10的倍数个数，就是向下取整1000/10 = 100个；15的倍数个数是1000/15 = 66个；30的倍数个数是1000/30 = 33个。代入容斥公式：100 + 66 - 33 = 133。这就是正确答案。

再看代码怎么体现这个逻辑。程序里用循环从a遍历到b，每次判断(i%u==0)||(i%v==0)，满足就num++。这个写法其实是在暴力枚举，对于小范围没问题，但命题人更想让你意识到，这种枚举本质上就是在计算并集的大小，而用容斥原理可以O(1)得到结果，这才是竞赛思维——看到循环就想优化，看到整除就想数论。这就是命题视角：他们不会只考你跑代码，而是考你透过代码看到数学结构的能力。

思考心法方面，拿到这类题先别急着写循环，先问自己：题目到底在算什么？是求并集吗？如果是，能不能用容斥？如果能，交集是什么？怎么算？最后再回头写代码验证。这样一步步推，就不会在lcm上掉坑，也不会漏减交集。

避坑方面，除了刚才说的lcm算错，还有两个常见错误：一是忘记容斥必须减交集，直接相加得166；二是把lcm(10,15)算成150，导致减去的交集少了，结果变成183。这两个错误在历年真题里出现频率很高，属于必考点。

从考频趋势看，循环结构题库共考过609题，覆盖12个考试级别，逐年分布显示2023年77题、2024年128题、2025年158题、2026年161题，呈明显上升趋势。最大公约数与最小公倍数题库共考过32题，其中2025年高达13题，说明数论基础题在近年被高频复用。结合这两组数据，可以预测未来这类‘循环+数论’的组合题还会继续升温，命题人可能会换数字、换区间、甚至改成求‘不能被u或v整除’的个数，但核心还是考容斥和lcm/gcd的运用。

总之，这道题的答案是133，但更重要的是掌握背后的容斥思想和lcm计算方法，这才是应对未来类似题目的关键。