约数、倍数与试除

老师先和你一起读题

我们现在走到“数论与位运算工具箱”。先不要急着背模板，我把今天的问题缩成一句话：枚举到sqrt(n)即可成对找到约数，注意完全平方数只计一次。把这句话抄成自己的语言，再问三个问题：输入是什么、程序要维持什么、最后输出凭什么正确。考级真正拉开差距的不是敲字速度，而是能否把题面故事翻译成一个可执行、可检查的小模型。

上一课是“差分处理成段增减”。它留下的工具会在今天继续使用；今天学会后，会自然连接到“质数判断和筛法入口”。这不是把九十一个知识点平铺在桌上，而是一条不断复用旧能力的训练线。遇到陌生题时，先找它与旧题相同的对象、状态或边界，再处理新变化。

跟着我做第一遍

今天的课堂任务是：列出36全部约数并排序。第一步，用铅笔圈出数据范围和输出格式；第二步，写一组最小输入并手算；第三步，列变量表或状态表；第四步才写代码；第五步用一个故意刁难程序的反例验收。每一步都留下纸面证据，这样答案错了也能定位首个偏差，而不是从头乱改。

假设输入规模是 14。先估朴素方案要做多少次核心操作，再决定能否使用。若循环处理了前 i 个元素，就用一句完整的话写循环不变量：已经处理的前缀满足什么，未处理部分还剩什么。初始化时它成立；每轮更新保持它；循环结束时它推出答案。考场不要求写长证明，但你必须在脑中完成这三段。

把代码一行一行说成人话

下面是本章会反复用到的最小片段。它不是今天答案的替身，而是训练“代码—状态—输出”的转换：

long long gcd(long long a,long long b){while(b){long long r=a%b;a=b;b=r;}return a;}

逐行解释每个变量的类型、初值、合法范围和更新时机。若片段省略了声明或外围 main，请补成能用 C++17 编译运行的完整程序。运行前先预测输出；运行后若与预测不同，比较第一处不同状态。能解释代码为何正确，比能默写更重要。

最容易丢分的地方

本课高频错误是：循环到n导致不必要超时。不要只记“别这样”，要构造一个最小反例让它真的失败。例如数组问题优先试空概念边界、n=1、全相同、全负和极值；字符串试单字符、空格、重复；搜索试无解、起点即终点、环；数值题试0、1和接近类型上限。反例越小，越容易看见错误原因。

再做四项提交前检查：下标是否始终合法；中间量是否溢出；多组数据是否清空；输出的空格、换行和大小写是否完全符合题面。样例通过只说明一条路径正确，不能替代这些边界证据。

第二遍由你来讲

现在合上示例，按“题意—状态—步骤—正确性—复杂度—测试”六句话向老师复述。接着独立完成任务，不看答案。若卡住，不要整段抄模板，只退回上一层：不会写代码就先写伪代码；不会写伪代码就画一次状态变化；连状态也说不清，就重新圈输入输出。

做完后回答：为什么这个方法不会漏？为什么不会重复？最坏做多少次操作？额外使用多少空间？哪一个输入最可能让错误暴露？开放推导题必须写出这些证据；只写算法名不得分。

课堂板书：把答案拆成得分点

考试答案可以拆成五行板书。第一行写“已知”和“要求”，不把故事名词直接当变量；第二行写核心状态及初值；第三行写一次更新，并说明更新前后哪个事实保持不变；第四行写终止时怎样从状态读出答案；第五行写复杂度和最危险边界。今天的核心状态必须能够表达“枚举到sqrt(n)即可成对找到约数，注意完全平方数只计一次”，课堂实现则以“列出36全部约数并排序”为验收目标。

老师追问时，不接受“模板就是这样”。如果删掉某个判断，请给出会失败的输入；如果改变循环方向，请说明一个元素会不会被重复使用；如果把 long long 改成 int，请估算最大中间量；如果把 BFS 换成 DFS，请说明最短性是否仍成立。你能回答这些“为什么不能改”，才说明代码不是碰巧通过。

最后做一次迁移：把课堂数字全部换掉，或把目标从求和改成计数、从首次位置改成最后位置。先指出哪些结构不变，哪些边界必须重写。真正掌握的知识可以迁移；只能认出原题外形，还不算会做。

课后闭环

今天的连接结论是：试除连接判质数。立即完成单选、多选、代码跟踪或计算、开放推导四题；有代码实验的课再从空文件实现并跑满四组内联测试。错题记录首因，不写“粗心”：应写成“循环上界把 < n 写成 <= n，反例 n=1 越界；明天遮住答案重写”。隔天能在新数字下独立完成，才算学会“约数、倍数与试除”。