面试题库 › 算法 / 大模型 › 求 Σ floor(n/i)·i(整除分块)

求 Σ floor(n/i)·i(整除分块)

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:数学与智力题

哪些公司问过

中国民生银行信用卡中心1

常见岗位:人工智能

答案要点

  1. floor(n/i) 只有约 2√n 种取值,取值相同的 i 构成连续区间
  2. 区间右端点 r = n / (n / l),区间贡献为 q × (l + r)(r − l + 1) / 2
  3. 单个 n 的复杂度由 O(n) 降到 O(√n)
  4. 循环读入直到 −1,每个 n 独立输出
  5. 结果量级约 0.82n²,需要 64 位整数并防止中间乘积溢出

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题