Jump to content

Talk:Dirichlet hyperbola method

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Optimal splitting point

In many cases, the sum can be computed sublinearly. Splitting at sqrt(n) gives O(n^3/4), splitting optimally in O(n^2/3) time.

https://codeforces.com/blog/entry/117635 Wqwt (talk) 22:33, 29 July 2024 (UTC)[reply]