GESP 五级 · GESP 202312 C++ 五级 第 24 题

小杨想写一个程序来算出正整数 $N$ 有多少个因数，经过思考他写出了一个重复没有超过 $N/2$ 次的循环就能够算出来了。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】因数个数计算｜循环次数优化｜数论边界条件

🎯 考纲定位 这道题在 GESP 五级循环模块，命题人卡住的就是绝大多数考生对"因数"概念的暴力理解。五级考生普遍习惯把循环次数写满 N，这道题专门检验你是否真的理解因数成对出现的数学本质——任何大于 N/2 的因数只能是 N 本身，所以 N/2 次循环确实覆盖所有"非 N 的因数"，只需最后补上 N 即可。

🧠 解题思维 看到题先想"因数怎么数？"——遍历所有可能的除数，判断能否整除。关键观察是：若 i 能整除 N，则 N/i 也能整除 N，因此因数成对出现。推理链：1 到 N 遍历有 N 次，但 1 到 N/2 遍历只漏掉 N 自己。所以 N/2 次循环能数出除 N 以外的所有因数，程序里加个 if(N%1==0) 就能算出总数。这就是"通法"：任何"数因数"的题，优先想"对称性"和"边界条件"，而不是盲目写 N 次循环。

🪤 陷阱拆解 陷阱藏在"没有超过 N/2 次"这个绝对化表述里。命题人利用的是考生对因数概念的表面理解——以为因数就是 1,2,...,N，自然要循环 N 次。实际上，因数定义是"能整除 N 的正整数"，而任何大于 N/2 的因数只能是 N 本身（因为 1.5N 不可能整除 N）。如果你只背了"因数个数公式"，没理解数论本质，就会误以为 N/2 次不够，选错。

🔄 反命题思维 如果把"N/2"换成"N 次"，那循环次数确实够了，但题目问的是"没有超过 N/2 次"是否可行，答案依然是正确。如果把"因数"换成"质因数"，那 N/2 次循环就完全不行了，因为质因数个数远小于 N/2。所以刷到类似题，先问自己"命题人想考我什么？"——考的是对"因数"的数学定义和循环次数的优化，不是死记硬背。