求 Σ floor(n/i)·i(整除分块)
哪些公司问过
中国民生银行信用卡中心1
答案要点
- floor(n/i) 只有约 2√n 种取值,取值相同的 i 构成连续区间
- 区间右端点 r = n / (n / l),区间贡献为 q × (l + r)(r − l + 1) / 2
- 单个 n 的复杂度由 O(n) 降到 O(√n)
- 循环读入直到 −1,每个 n 独立输出
- 结果量级约 0.82n²,需要 64 位整数并防止中间乘积溢出
易错点
- 逐项累加 O(n),n 很大或数据组数多时超时
- 用 32 位整数存结果,或等差数列中间乘积溢出
- 分块右端点算错,导致区间重叠或死循环
面试官常见追问
- 为什么 floor(n/i) 只有 O(√n) 种取值?
- 这个和有什么数论含义?
- 查询很多时怎么优化?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。