问题: https://www.spoj.com/problems/DIVCNT1/ 解答: https://yhx-12243.github.io/OI-transit/records/spojDIVCNT1.html 演算法: 给定一条凸曲线，用Stern-Brocot Tree找到一条折线，紧贴曲线上方。 我的疑问: 如何证明二分法找到的向量，恰好紧贴曲线上方? ------------------------------------------------------------------------------ 以下是文献调查 [1] 此演算法源自Euler Project #540的讨论区，使用者Animus的留言。 https://projecteuler.net/thread=540#229299 (需要登入、并且解完该题) [2] 网友min_25将之实作。 https://min-25.hatenablog.com/entry/2018/05/03/145505 [3] 朱震霆《一些特殊的数论函数求和问题》求得时间复杂度O(n^(1/3) log^3(n))。 https://reurl.cc/73Kkpy (IOI2018中国国家候选队论文集) https://ideone.com/PagVPQ (朱震霆的实作程式码) [4] Richard Sladkey《A Successive Approximation Algorithm for Computing the Divisor Summatory Function》是另一种演算法，其原理十分相似。 http://arxiv.org/abs/1206.3369 [5] stackexchange的相关讨论。 https://math.stackexchange.com/questions/384520/ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.137.167.111 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1634992539.A.64E.html ※ 编辑: DJWS (220.137.167.111 台湾), 10/23/2021 20:43:13 ※ 编辑: DJWS (220.137.167.111 台湾), 10/23/2021 20:47:09