SPyofgame's blog

By SPyofgame, history, 3 years ago, In English

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

  • Vote: I like it
  • +52
  • Vote: I do not like it

»
3 years ago, # |
Rev. 2   Vote: I like it +109 Vote: I do not like it

there is no time limit so brute-force is enough

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The bonus problem itself doesnt have the constraint, so I fixed my blog that 1 second time limit and 1Gb memory limit and non-negative tuple

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

You should specify constraints for $$$a, b, c$$$ as well. For example, for any $$$x$$$ there is a solution $$$a = 0, b = x, c = -x$$$, since for those $$$0 \leq a + b + c = 0 + x - x = 0 \leq S$$$ and $$$0 \leq a \cdot b \cdot c = 0 \leq T$$$ and for every $$$S$$$ and $$$T$$$ the answer is infinity.

When you include constraints for $$$a, b, c$$$ as $$$ 0 \leq a, b, c$$$, then constraints $$$0 \leq a + b + c$$$ and $$$0 \leq a \cdot b \cdot c$$$ become redundant ;)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Ah yes, I just also fix that too, at exact the time you submit your comment, sorry about that

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I have a question too, how many pairs (x, y) such that x, y >= 0 satisfy following condition: x + y <= S, x * y <= T

(When I was trying these post's problem, I encountered this and I just wonder, thanks.)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    AFAIK this problem can be solved in $$$O(\sqrt[3]{T})$$$

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think i might have something. WLOG assume x<=y<=z. Note x<=10^6. Iterate for x. After that note that if product is fixed, sum of two numbers is minimal when they are as close to each other as possible. So you can use binary search for rest i think.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    That is a good approach, which I think it will be the real solution

    But I still find it very difficult to get the quick answer for fixed $$$k$$$ in $$$O(1)$$$ or $$$O(polylog(S) + polylog(T))$$$

    Subproblem: Count such pair $$$(x, y)$$$ satisfy $$$(x + y \leq S - k)$$$ and $$$(x \times y \leq \frac{S}{k})$$$ and $$$(x \geq y \geq k)$$$

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Honestly, I don't think any "good" solution exists
      Let's say you want want to solve this problem for just two numbers(brute force the smallest one up to 10^6)

      Now for fixed values of $$$S, T$$$ you want to find the number of pairs $$$(a, b)$$$, such that $$$a+b \leq S$$$ and $$$ab \leq T$$$
      It's not hard to see that for a fixed value of $$$a$$$, the number of "good" $$$b$$$ is $$$min(\lfloor \frac{T}{a} \rfloor, S - a)$$$

      And now you want to know the sum of this expression for all $$$a \leq S$$$, but if you take a look at the graphs of $$$S - a$$$ and $$$\frac{T}{a}$$$, you'll notice that in general case almost for all $$$a$$$ the graph of a fraction will lie below the graph of a line, thus solving this problem becomes close to finding smth similar to $$$\sum_{a=1}^{S}{\lfloor \frac{T}{a} \rfloor}$$$, and the best time complexity(AFAIK) for it is $$$O(\sqrt{T})$$$, which is too large.

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

i think the sample cases are wrong. for example input:

10 10 should give 193

edit: i was wrong it should be 213.

edit2: is there any solution faster than O(s^2)?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes there is, currently I am achieving $$$O(S log S + sqrt(T))$$$ but a little bug to optimize to $$$O(S log S + sqrt(sqrt(T)))$$$

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please share the O(s^2) approach.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Spoiler
»
3 years ago, # |
Rev. 4   Vote: I like it +6 Vote: I do not like it

Spending for 3 days and I cant optimize more, so I decide to quit.

The best I achieve for this problem (which I used to generate the test cases above) is $$$O(S \times T^{\frac{1}{3}})$$$ (use for large T small S) and $$$O(T^{\frac{5}{6}})$$$ (use for large S small T) (both can calculate $$$S = T = 10^{10}$$$ under 1 second)

Good luck to anyone who try to solve this with a better algorithm <3

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Update: Now it is $$$O(T^{\frac{2}{3}})$$$ and calculate $$$S \leq 10^{18}$$$ and $$$T \leq 10^{12}$$$ in $$$830ms$$$

»
3 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Update: Using integral, my real complexity is actually only $$$O\Huge(\normalsize \overset{min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\Huge \Sigma}} \LARGE( \normalsize log_2(\Large \lfloor \normalsize \sqrt{\frac{T}{a}} \Large \rfloor) \LARGE + \Large \lfloor \normalsize \normalsize \frac{T}{a} \Large \rfloor \LARGE ^{^{\normalsize 1/3}}) \Huge) \normalsize = O\Large( \int_{_{\normalsize 1}}^{^{\normalsize T^{1/3}}}\frac{\normalsize T^{1/3}}{\normalsize a^{1/3}} \normalsize da \Large) \normalsize = O(T^{5/9})$$$

No papers were found to has a better bound

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing Problem! BTW, I reckon that you're supposed to mention a,b,c are non-negative intergers.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$min(a, b, c) \geq 0$$$ condition is mentioned :(

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      e, I mean, integer

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, ok, gonna fix that later. (Though I actually tried to count real numbers too)