Statement
Used this Paper
Given $S, T (0 \leq S, T \leq 10^{18})$
I need to count the number of tuple $(a, b, c)$ satisfied $(\min(a, b, c) \geq 0)$ and $(a + b + c \leq S)$ and $(a \times b \times c \leq T)$
Combinatorics Approach
I tried to fix $a$ to be the minimum $\Rightarrow (0 \leq a \leq \sqrt[3]{T})$ then count the number of pair $(b, c)$ satisfied $(\min(b, c) \geq a)$ and $(b + c \leq S - a)$ and $(b \times c \leq \lfloor \frac{T}{a} \rfloor)$.
Because some tuple $(a, b, c)$ may equal to $(a, c, b), (b, a, c), (b, c, a), (c, a, b)$ or $(c, b, a)$ (example $a = b$), while some may not (example $a < b < c$). Therefore I split into 4 cases
Case [1] $\Rightarrow$ $0 \leq a < b < c$ and $(a \leq \sqrt[3]{T})$
$cnt_1 = \overset{0}{\underset{a = 0}{\LARGE\sum}} \overset{S}{\underset{b = 1}{\LARGE\sum}}\overset{S - b}{\underset{c = b + 1}{\LARGE\sum}} I(1) + \overset{\min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\LARGE\sum}} \overset{\min(S - a, \lfloor \frac{T}{a} \rfloor)}{\underset{b = a + 1}{\LARGE\sum}}\overset{\min(S - a - b, \lfloor \frac{T}{ab} \rfloor)}{\underset{c = b + 1}{\LARGE\sum}} I(1)$
$= \overset{S}{\underset{b = 1}{\LARGE\sum}} \max(0, S - 2b) + \overset{\min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\LARGE\sum}} \overset{\min(S - a, \frac{T}{a})}{\underset{b = a + 1}{\LARGE\sum}} \max(0, \min(S - a - b, \lfloor \frac{T}{ab} \rfloor) - b)$
$ = \lfloor \frac{S}{2} \rfloor \times S - 2 \times \overset{\lfloor \frac{S}{2} \rfloor}{\underset{x = 1}{\LARGE\sum}} I(x) + \overset{\min(S, \lfloor \sqrt[3]{T} \rfloor) }{\underset{a = 1}{\LARGE\sum}} \Huge($ $\overset{ f(a) }{\underset{x = 1}{\LARGE{\sum}}} \large{I(x)} + (S - a)(g(a) - a) - \overset{g(a)}{\underset{x = a + 1}{\LARGE\sum}} I(x) + \overset{f(a)}{\underset{x = g(a) + 1}{\LARGE\sum}} \lfloor \frac{T}{xa} \rfloor $$\Huge)$
for $I(x) = x$
for $f(a) = \Big\lfloor \min\Big(\frac{S - a}{2} \, \frac{T}{2a} + 1, \sqrt{\lfloor \frac{T}{a} \rfloor} \Big) \Big\rfloor$
and $g(a) = \max\Large(\normalsize k\ |\ S - a - k \leq \lfloor \frac{T}{a} \rfloor\Big)$
Case [2] $\Rightarrow$ $0 \leq a < b = c$ and $(a \leq \sqrt[3]{T})$
$cnt_2 = \overset{0}{\underset{a = 0}{\LARGE\sum}} \overset{\lfloor \frac{S}{2} \rfloor}{\underset{b = 1}{\LARGE\sum}} \overset{b}{\underset{c = b}{\LARGE\sum}} I(1) + \overset{\min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\LARGE\sum}} \overset{\min(\frac{S - a}{2}, \sqrt{\lfloor \frac{T}{a} \rfloor})}{\underset{b = 1}{\LARGE\sum}} \overset{b}{\underset{c = b}{\LARGE\sum}} I(1)$
$= \lfloor \frac{S}{2} \rfloor + \overset{min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\LARGE\sum}} max\Large( \normalsize 0, \Large \lfloor \normalsize min\Large(\normalsize \frac{S - a}{2}, \sqrt{\lfloor \frac{T}{a} \rfloor} \Large) \rfloor \normalsize - a \Large)$
Case [3] $\Rightarrow$ $0 \leq a = b < c$ and $(a \leq \sqrt[3]{T})$
$cnt_3 = \overset{0}{\underset{a = 0}{\LARGE\sum}} \overset{a}{\underset{b = a}{\LARGE\sum}} \overset{S}{\underset{c = 1}{\LARGE\sum}} I(1) + \overset{\min(\lfloor \frac{S}{2} \rfloor, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\LARGE\sum}} \overset{a}{\underset{b = a}{\LARGE\sum}} \overset{\min(S - a - b, \lfloor \frac{T}{ab} \rfloor)}{\underset{c = b + 1}{\LARGE\sum}} I(1)$
$ = S + \overset{\min(\lfloor \frac{S}{2} \rfloor, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\LARGE\sum}} \max\Large(\normalsize 0, min\Large(\normalsize S - 2a, \Large \lfloor \normalsize \frac{T}{a^2} \Large \rfloor \Large)\normalsize - a\Large)$
Case [4] $\Rightarrow$ $0 \leq a = b = c$ and $(a \leq \sqrt[3]{T})$
$cnt_4 = \overset{min(\frac{S}{3}, \sqrt[3]{T})}{\underset{a = 0}{\LARGE\sum}} \overset{a}{\underset{b = a}{\LARGE\sum}}\overset{b}{\underset{c = b}{\LARGE\sum}} I(1)$
$ = \lfloor \min(\frac{S}{3}, \sqrt[3]{T}) \rfloor + 1$
Now result = number of different tuple $(a, b, c)$ satisfied the condition
In case [1] $(a, b, c) \neq (a, c, b) \neq (b, a, c) \neq (b, c, a) \neq (c, a, b) \neq (c, b, a)$
In case [2] $(a, b, c) \neq (b, c, a) \neq (c, a, b)$
In case [3] $(a, b, c) \neq (b, c, a) \neq (c, a, b)$
In case [4] $(a, b, c)$ is unique
Therefore, $result = 6 \times cnt_1 + 3 \times cnt_2 + 3 \times cnt_3 + 1 \times cnt_4$
Algorithm Complexity
It is known that $\overset{r}{\underset{x = l}{\Large\Sigma}} \normalsize (x) = \frac{r(r+1)}{2} - \frac{l(l-1)}{2}$ when $l \leq r$ and $\overset{r}{\underset{x = l}{\Large\Sigma}} \normalsize (x) = 0$ otherwise. Therefore this only take $O(1)$ complexity
Let $f(p, q, x) = \overset{min(q, \lfloor \frac{T}{x} \rfloor)}{\underset{k = 1}{\Sigma}} \lfloor \frac{T}{xk} \rfloor$
There is $O(\sqrt{T})$ solution based on the fact that the number of different floor value in that series is $O(\sqrt{T})$
There is also a $O(\sqrt[3]{T} log(T))$ solution based on the fact that the number of different slopes in from the graph of that series is $O(\sqrt[3]{T})$
The overall complexity should be $O\Big(\normalsize \overset{min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\Huge \Sigma}} \LARGE \sqrt[3]{\Large \lfloor \normalsize \sqrt[2]{\Large \lfloor \normalsize \frac{T}{a}} \Large \rfloor} \Large \rfloor \Large) \Big)$
I expected the to be $O(\sqrt{T})$ or even be $O(\sqrt[3]{T})$ as it would in theory
But it seems to be about $O(T^{\frac{2}{3}})$ since I used many divisions and the correct solution (removed approximation part) for slope trick is not $O(T^{\frac{1}{3}})$ but much slower in theory (but still faster then all of my old correct-codes because it is division free as paper said)
UPDATE
My real complexity is only $O\Huge(\normalsize \overset{min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\Huge \Sigma}} \LARGE( \normalsize log_2(\Large \lfloor \normalsize \sqrt{\frac{T}{a}} \Large \rfloor) \LARGE + \Large \lfloor \normalsize \normalsize \frac{T}{a} \Large \rfloor \LARGE ^{^{\normalsize 1/3}}) \Huge) \normalsize = O\Large( \int_{_{\normalsize 1}}^{^{\normalsize T^{1/3}}}\frac{\normalsize T^{1/3}}{\normalsize a^{1/3}} \normalsize da \Large) \normalsize = O(T^{5/9})$. Though I calculate upto $\Large \lfloor \normalsize min \Large( \normalsize (S - a) / 2, \sqrt{\frac{T}{a}} \Large) \rfloor$ only, but the number of unique value is still based on $\lfloor \frac{T}{a} \rfloor$. Therefore make my mistake
I also just remove the $\sqrt[3]{T}$ multiplying part as my mistake while writing latex.
I also used derivatives to give closer bound
Other known property
It is easy to known that by not fixing $a$ as minimum, you can also achieve $O(S \times \sqrt[3]{T})$.
By not depending on $O(f(t))$ factor, the complexity is $O(S^2)$ but might be possible to improve
There is special case when $S \leq \sqrt[3]{T}$ then we have $0 \leq a + b + c \leq S \leq \sqrt[3]{T} \leq T$. Therefore we get rid of the product-limitation condition part and the answer will be $\frac{(S+1)(S+2)(S+3)}{6}$
When $S = T = n$, the number of solution is approximately $1.5n^2$ Tested with 10.000.000 numbers $n \leq 10^9$ using this algorithm
My Question:
Is there a way to run with smaller $a$ but not to increase the counting (b, c) part's complexity
Is there a good formula to calculate $f(p, q, x)$ from $f(p, q, x - 1)$ or even from $f(l, r, x - 1)$ for some $(l, r)$
Any of these questions below if it is solvable then the whole problem is solvable for $O(\sqrt[3]{T})$ !
Is there an alternative formula which can run in $O(\sqrt[2](T))$ or even $O(\sqrt[3](T))$ ?
Is there a faster algorithm to calculate $f(p, q, x)$ ?
Can I calculate $f(p, q, x)$ from $f(l, r, x - 1)$ for some $(l, r)$ faster than $O(log(T))$ ?
Given a array $p[]$ of $T$ numbers where $p[i] = \lfloor \frac{T}{i} \rfloor$. Given $O(\sqrt[3]{T})$ queries $Q(l, r, x) = \overset{r}{\underset{x = l}{\Sigma}} p[x]$. Can this be solved in $O(\sqrt[3]{T})$ after somehow compressing p[] and optimizing the calculation ?
