### Statement
[This problem](https://codeforces.com/blog/entry/93981)
Given [imath]S, T (0 \leq S, T \leq 10^{18})[/imath]
I need to count the number of tuple [imath](a, b, c)[/imath] satisfied [imath](min(a, b, c) \geq 0)[/imath] and [imath](a + b + c \leq S)[/imath] and [imath](a \times b \times c \leq T)[/imath]
I tried to fix [imath]a[/imath] to be the minimum and [imath](0 \leq a \leq \sqrt[3]{T})[/imath] then count the number of pair [imath](b, c)[/imath] satisfied [imath](min(b, c) \geq a)[/imath] and [imath](b + c \leq S - a)[/imath] and [imath](b \times c \leq \lfloor \frac{T}{a} \rfloor)[/imath].
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
### Combinatorics Approach
Because some tuple [imath](a, b, c)[/imath] may equal to [imath](a, c, b), (b, a, c), (b, c, a), (c, a, b)[/imath] or [imath](c, b, a)[/imath] (example [imath]a = b[/imath]), while some may not (example [imath]a < b < c[/imath]). Therefore I split into 4 cases
>>>>>>>>>>>>>>>>>>>>> Case**[1]** [imath]\Rightarrow[/imath] [imath]0 \leq a < b < c[/imath] and [imath](a \leq \sqrt[3]{T})[/imath]
[imath]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)[/imath]
[imath]= \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)[/imath]
[imath] = \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([/imath] [imath]\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 [/imath][imath]\Huge)[/imath]
for [imath]I(x) = x[/imath]
for [imath]f(a) = \Big\lfloor min\Big(\frac{S - a}{2} \, \frac{T}{2a} + 1, \sqrt{\lfloor \frac{T}{a} \rfloor} \Big) \Big\rfloor[/imath]
and [imath]g(a) = max\Large(\normalsize k\ |\ S - a - k \leq \lfloor \frac{T}{a} \rfloor\Big)[/imath]
>>>>>>>>>>>>>>>>>>>>> Case**[2]** [imath]\Rightarrow[/imath] [imath]0 \leq a < b = c[/imath] and [imath](a \leq \sqrt[3]{T})[/imath]
[imath]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)[/imath]
[imath]= \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)[/imath]
>>>>>>>>>>>>>>>>>>>>> Case**[3]** [imath]\Rightarrow[/imath] [imath]0 \leq a = b < c[/imath] and [imath](a \leq \sqrt[3]{T})[/imath]
[imath]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)[/imath]
[imath] = 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)[/imath]
>>>>>>>>>>>>>>>>>>>>> Case**[4]** [imath]\Rightarrow[/imath] [imath]0 \leq a = b = c[/imath] and [imath](a \leq \sqrt[3]{T})[/imath]
[imath]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)[/imath]
[imath] = \lfloor min(\frac{S}{3}, \sqrt[3]{T}) \rfloor + 1[/imath]
>>>>>>>>>>>>>>>>>>>>> Now [imath]result[/imath] = number of different tuple [imath](a, b, c)[/imath] satisfied the condition
In case **[1]** [imath](a, b, c) \neq (a, c, b) \neq (b, a, c) \neq (b, c, a) \neq (c, a, b) \neq (c, b, a)[/imath]
In case **[2]** [imath](a, b, c) \neq (b, c, a) \neq (c, a, b)[/imath]
In case **[3]** [imath](a, b, c) \neq (b, c, a) \neq (c, a, b)[/imath]
In case **[4]** [imath](a, b, c)[/imath] is unique
Therefore, [imath]result = 6 \times cnt_1 + 3 \times cnt_2 + 3 \times cnt_3 + 1 \times cnt_4[/imath]
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
### Algorithm Complexity
It is known that [imath]\overset{r}{\underset{x = l}{\Large\Sigma}} \normalsize (x) = \frac{r(r+1)}{2} - \frac{l(l-1)}{2}[/imath] when [imath]l \leq r[/imath] and [imath]\overset{r}{\underset{x = l}{\Large\Sigma}} \normalsize (x) = 0[/imath] otherwise
Let [imath]f(p, q, x) = \overset{min(q, \lfloor \frac{T}{x} \rfloor)}{\underset{k = 1}{\Sigma}} \lfloor \frac{T}{xk} \rfloor[/imath]
> There is [imath]O(\sqrt{T})[/imath] solution based on the fact that the number of different floor value in that series is [imath]O(\sqrt{T})[/imath]
> There is also a [imath]O(\sqrt[3]{T} log(T))[/imath] solution based on the fact that the number of different slopes in from the graph of that series is [imath]O(\sqrt[3]{T})[/imath]
The overall complexity should be [imath]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}})[/imath]
or even be [imath]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}})[/imath]
But for some reasons or maybe hidden constant it seems to be about [imath]O(T^{\frac{2}{3}})[/imath]
It is also known that by not fixing [imath]a[/imath] as minimum, you can also achieve [imath]O(S \times \sqrt[3]{T})[/imath]
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
### My Question:
> Any of this question if it is solvable then the whole problem is solvable for [imath]O(\sqrt[3]{T})[/imath] !
- Is there an alternative formula which can run in [imath]O(\sqrt[2](T))[/imath] or even [imath]O(\sqrt[3](T))[/imath] ?
- Is there a faster algorithm to calculate [imath]f(p, q, x)[/imath] ?
- Is there a formula to calculate [imath]f(p, q, x)[/imath] from [imath]f(p, q, x - 1)[/imath] or even from [imath]f(l, r, x - 1)[/imath] for some [imath](l, r)[/imath]
- Can I calculate [imath]f(p, q, x)[/imath] from [imath]f(l, r, x - 1)[/imath] for some [imath](l, r)[/imath] faster than [imath]O(log(T))[/imath] ?
- Given a array [imath]p[][/imath] of [imath]T[/imath] numbers where [imath]p[i] = \lfloor \frac{T}{i} \rfloor[/imath]. Given [imath]O(\sqrt[3]{T})[/imath] queries [imath]Q(l, r, x) = \overset{r}{\underset{x = l}{\Sigma}} p[x][/imath]. Can this be solved in [imath]O(\sqrt[3]{T})[/imath] after somehow compressing p[] and optimizing the calculation ?
[This problem](https://codeforces.com/blog/entry/93981)
Given [imath]S, T (0 \leq S, T \leq 10^{18})[/imath]
I need to count the number of tuple [imath](a, b, c)[/imath] satisfied [imath](min(a, b, c) \geq 0)[/imath] and [imath](a + b + c \leq S)[/imath] and [imath](a \times b \times c \leq T)[/imath]
I tried to fix [imath]a[/imath] to be the minimum and [imath](0 \leq a \leq \sqrt[3]{T})[/imath] then count the number of pair [imath](b, c)[/imath] satisfied [imath](min(b, c) \geq a)[/imath] and [imath](b + c \leq S - a)[/imath] and [imath](b \times c \leq \lfloor \frac{T}{a} \rfloor)[/imath].
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
### Combinatorics Approach
Because some tuple [imath](a, b, c)[/imath] may equal to [imath](a, c, b), (b, a, c), (b, c, a), (c, a, b)[/imath] or [imath](c, b, a)[/imath] (example [imath]a = b[/imath]), while some may not (example [imath]a < b < c[/imath]). Therefore I split into 4 cases
>>>>>>>>>>>>>>>>>>>>> Case**[1]** [imath]\Rightarrow[/imath] [imath]0 \leq a < b < c[/imath] and [imath](a \leq \sqrt[3]{T})[/imath]
[imath]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)[/imath]
[imath]= \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)[/imath]
[imath] = \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([/imath] [imath]\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 [/imath][imath]\Huge)[/imath]
for [imath]I(x) = x[/imath]
for [imath]f(a) = \Big\lfloor min\Big(\frac{S - a}{2} \, \frac{T}{2a} + 1, \sqrt{\lfloor \frac{T}{a} \rfloor} \Big) \Big\rfloor[/imath]
and [imath]g(a) = max\Large(\normalsize k\ |\ S - a - k \leq \lfloor \frac{T}{a} \rfloor\Big)[/imath]
>>>>>>>>>>>>>>>>>>>>> Case**[2]** [imath]\Rightarrow[/imath] [imath]0 \leq a < b = c[/imath] and [imath](a \leq \sqrt[3]{T})[/imath]
[imath]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)[/imath]
[imath]= \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)[/imath]
>>>>>>>>>>>>>>>>>>>>> Case**[3]** [imath]\Rightarrow[/imath] [imath]0 \leq a = b < c[/imath] and [imath](a \leq \sqrt[3]{T})[/imath]
[imath]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)[/imath]
[imath] = 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)[/imath]
>>>>>>>>>>>>>>>>>>>>> Case**[4]** [imath]\Rightarrow[/imath] [imath]0 \leq a = b = c[/imath] and [imath](a \leq \sqrt[3]{T})[/imath]
[imath]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)[/imath]
[imath] = \lfloor min(\frac{S}{3}, \sqrt[3]{T}) \rfloor + 1[/imath]
>>>>>>>>>>>>>>>>>>>>> Now [imath]result[/imath] = number of different tuple [imath](a, b, c)[/imath] satisfied the condition
In case **[1]** [imath](a, b, c) \neq (a, c, b) \neq (b, a, c) \neq (b, c, a) \neq (c, a, b) \neq (c, b, a)[/imath]
In case **[2]** [imath](a, b, c) \neq (b, c, a) \neq (c, a, b)[/imath]
In case **[3]** [imath](a, b, c) \neq (b, c, a) \neq (c, a, b)[/imath]
In case **[4]** [imath](a, b, c)[/imath] is unique
Therefore, [imath]result = 6 \times cnt_1 + 3 \times cnt_2 + 3 \times cnt_3 + 1 \times cnt_4[/imath]
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
### Algorithm Complexity
It is known that [imath]\overset{r}{\underset{x = l}{\Large\Sigma}} \normalsize (x) = \frac{r(r+1)}{2} - \frac{l(l-1)}{2}[/imath] when [imath]l \leq r[/imath] and [imath]\overset{r}{\underset{x = l}{\Large\Sigma}} \normalsize (x) = 0[/imath] otherwise
Let [imath]f(p, q, x) = \overset{min(q, \lfloor \frac{T}{x} \rfloor)}{\underset{k = 1}{\Sigma}} \lfloor \frac{T}{xk} \rfloor[/imath]
> There is [imath]O(\sqrt{T})[/imath] solution based on the fact that the number of different floor value in that series is [imath]O(\sqrt{T})[/imath]
> There is also a [imath]O(\sqrt[3]{T} log(T))[/imath] solution based on the fact that the number of different slopes in from the graph of that series is [imath]O(\sqrt[3]{T})[/imath]
The overall complexity should be [imath]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}})[/imath]
or even be [imath]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}})[/imath]
But for some reasons or maybe hidden constant it seems to be about [imath]O(T^{\frac{2}{3}})[/imath]
It is also known that by not fixing [imath]a[/imath] as minimum, you can also achieve [imath]O(S \times \sqrt[3]{T})[/imath]
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
### My Question:
> Any of this question if it is solvable then the whole problem is solvable for [imath]O(\sqrt[3]{T})[/imath] !
- Is there an alternative formula which can run in [imath]O(\sqrt[2](T))[/imath] or even [imath]O(\sqrt[3](T))[/imath] ?
- Is there a faster algorithm to calculate [imath]f(p, q, x)[/imath] ?
- Is there a formula to calculate [imath]f(p, q, x)[/imath] from [imath]f(p, q, x - 1)[/imath] or even from [imath]f(l, r, x - 1)[/imath] for some [imath](l, r)[/imath]
- Can I calculate [imath]f(p, q, x)[/imath] from [imath]f(l, r, x - 1)[/imath] for some [imath](l, r)[/imath] faster than [imath]O(log(T))[/imath] ?
- Given a array [imath]p[][/imath] of [imath]T[/imath] numbers where [imath]p[i] = \lfloor \frac{T}{i} \rfloor[/imath]. Given [imath]O(\sqrt[3]{T})[/imath] queries [imath]Q(l, r, x) = \overset{r}{\underset{x = l}{\Sigma}} p[x][/imath]. Can this be solved in [imath]O(\sqrt[3]{T})[/imath] after somehow compressing p[] and optimizing the calculation ?