How fast can I count tuple (a, b, c) satisfy (a + b + c <= S) and (a * b * c <= T) and (min (a, b, c) >= 0)?

[SPyofgame]

### Statement

[This problem](https://codeforces.com/blog/entry/93981)

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)$

I tried to fix $a$ to be the minimum and $(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)$.

------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------------------------------------------------

### Combinatorics Approach

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

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 T^{\frac{1}{3}} \times \overset{min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\Sigma}} \LARGE \sqrt[2]{\Large \lfloor \normalsize \sqrt[2]{\Large \lfloor \normalsize \frac{T}{a}} \Large \rfloor} \Large \rfloor \Big) \normalsize \approx O(T^{\frac{1}{2}})$

or even be $O\Big(\normalsize T^{\frac{1}{3}} \times \overset{min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\Sigma}} \LARGE \sqrt[3]{\Large \lfloor \normalsize \sqrt[2]{\Large \lfloor \normalsize \frac{T}{a}} \Large \rfloor} \Large \rfloor \Big) \normalsize \approx O(T^{\frac{1}{2}})$

But for some reasons or maybe hidden constant it seems to be about $O(T^{\frac{2}{3}})$

It is also known that by not fixing $a$ as minimum, you can also achieve $O(S \times \sqrt[3]{T})$


------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------------------------------------------------

### My Question:

> Any of this question 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)$ ?

- Is there a 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)$

- 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 ?