[問題] DIVCNT1 - Counting Divisors

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間3年前 (2021/10/23 20:35)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/1

問題: 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://www.ptt.cc/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