Count a, b, c satisfy a + b + c <= S and a * b * c <= T for large S, T

Revision en24, by SPyofgame, 2022-03-27 20:25:23

### Statement

This question is based on bonus of this problem.

We need to count such non-negative integer triple $(a, b, c)$ that satisfy $(0 \leq a + b + c \leq S)$ and $(0 \leq a \times b \times c \leq T)$.

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:

Example 0
Example 1
Example 2
Example 3
Example 4
Example 5
Example 6
Example 7
Example 8
Example 9
Example 10
Example 11
Example 12
Example 13
Example 14
Example 15

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^{5/9})$

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

Current best known algorithm: O(T^(5/9)) - Used modulo for large result

Note: It is now A347221

#### History

Revisions

Rev. Lang. By When Δ Comment
en24 SPyofgame 2022-03-27 20:25:23 103
en23 SPyofgame 2021-08-26 21:40:29 10 Tiny change: ' is $O(T^{\frac{5}{9}})$\n\nWit' -> ' is $O(T^{5/9})$\n\nWit'
en22 SPyofgame 2021-08-26 21:39:38 31
en21 SPyofgame 2021-08-25 22:07:22 518 Tiny change: 'ler>\n\n> The answer ' -> 'ler>\n\n> After many hours, the answer '
en20 SPyofgame 2021-08-25 21:59:48 1368
en19 SPyofgame 2021-08-23 05:04:36 10 Tiny change: 'deone.com/myrecent)\n[Proof]' -> 'deone.com/yMi8tu)\n[Proof]'
en18 SPyofgame 2021-08-22 22:32:16 1 Tiny change: 'rac{2}{3}}$time &md' -> 'rac{2}{3}})$ time &md'
en17 SPyofgame 2021-08-22 22:31:09 5440 Tiny change: 'der $830ms, 3640KB$\n\n[Code' -> 'der $830ms$\n\n[Code'
en16 SPyofgame 2021-08-19 14:46:12 6 Tiny change: '00000000\n123456\nFull Out' -> '00000000\n\nFull Out'
en15 SPyofgame 2021-08-19 14:39:26 9
en14 SPyofgame 2021-08-19 13:38:05 907
en13 SPyofgame 2021-08-18 15:14:27 10 Tiny change: '------\n\n### Example\n\n<spoil' -> '------\n\n**Example:**\n\n<spoil'
en12 SPyofgame 2021-08-18 11:49:30 126
en11 SPyofgame 2021-08-18 10:59:20 118
en10 SPyofgame 2021-08-17 22:35:17 228
en9 SPyofgame 2021-08-17 22:30:14 11 Tiny change: 'nOutput:\n2122766957\n\n</s' -> 'nOutput:\n15007668845\n\n</s'
en8 SPyofgame 2021-08-17 22:28:01 86 Tiny change: '\nSince this number may be ve' -> '\nSince the result may be ve'
en7 SPyofgame 2021-08-17 22:11:00 34 Tiny change: 'T \leq 10^18$)\n\n----' -> 'T \leq 10^{18}$)\n\n----'
en6 SPyofgame 2021-08-17 22:00:04 305 Tiny change: 'eq T) and min(a, b, ' -> 'eq T) and \$min(a, b, '
en5 SPyofgame 2021-08-17 21:27:35 295
en4 SPyofgame 2021-08-17 20:42:32 884
en3 SPyofgame 2021-08-17 20:40:45 91
en2 SPyofgame 2021-08-17 20:39:59 926
en1 SPyofgame 2021-08-17 20:34:58 1220 Initial revision (published)