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:
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$$$
Math discussion for Proof
Used this Paper
Reference Code