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

Revision en23, by SPyofgame, 2021-08-26 21:40:29

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:

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
Tags #math, #algebra, #combinatorics

History

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