Statement
This question is based on bonus of this problem.
We need to count such triple $$$(a, b, c)$$$ that satisfy $$$(0 \leq a + b + c \leq S)$$$ and $$$(0 \leq a \times b \times c \leq T)$$$ and $$$min(a, b, c) \geq 0$$$
Since the result may be very big, you can either use bignum or modulo $$$10^9 + 7$$$ for convention
Notice that:
- $$$(0, 0, 1) \neq (0, 1, 0) \neq (1, 0, 0)$$$
Constraint:
$$$0 \leq S, T \leq 10^{18}$$$
$$$0 \leq a, b, c$$$
No Time Limit. But expect to be 10 seconds
Memory Limit: 1Gb
Input:
- A single line contain only two positive 60-bit integers $$$S$$$ and $$$T$$$ ($$$0 \leq S, T \leq 10^{18}$$$)
Output:
- Print a single integer, the number of positive tuple satisfy mathematical condition
Example:
After many hours, the answer for $$$f(10^{18}, 10^{18})$$$ is reached but not confirmed therefore I wont add in the example
Current Research
When $$$S \leq \lfloor \frac{S}{3} \rfloor \times \lfloor \frac{S + 1}{3} \rfloor \times \lfloor \frac{S + 2}{3} \rfloor \leq T$$$. The condition $$$a \times b \times c \leq T$$$ is satisfied, therefore the result is $$$\frac{(S+1)(S+2)(S+3)}{6}$$$
When $$$T = 0$$$, at least one of them must be zero, therefore the result will be $$$\frac{3S(S-1)}{2} + 1$$$
When $$$S = 0$$$, there is only one triple satisfied $$$(0, 0, 0)$$$
When $$$S = T$$$, the function $$$f(S, T) \approx 1.5 S^2$$$ (Tested with $$$10^7$$$ integers $$$n \leq 10^{12}$$$
Without depend on $$$O(f(S))$$$, the best current known algorithm is $$$O(T^{\frac{2}{3}})$$$ (actually smaller)
Without depend on $$$O(f(T))$$$, the best current known algorithm is $$$O(S^2)$$$ (can be further optimized but not on researched)
Sadly, there were no papers, documentaries, integer sequences or math formulas found to apply this function.
Math discussion for Proof
Used this Paper
Reference Code