v-O_O-v's blog

Can we do this problem in a better way

By v-O_O-v, history, 6 years ago, In English

214A - System of Equations Of course, we can do this using brute-force method. Does a better way exists please share it. Thanks.

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

$$$a + b ^ 2 = n$$$, so $$$a = n - b ^ 2$$$, so $$$a ^ 2 + b = (n - b ^ 2) ^ 2 + b = b ^ 4 - 2 * n * b ^ 2 + n ^ 2 + b = m$$$.

The last equation can be solved in $$$O(1)$$$. If you don't like math, don't open this link

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

    you won't have much fun, if you try to solve that for $$$b$$$...

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

      I'm sure every heathy person won't solve this problem using Ferrari's formula

      → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Iterate over $$$a$$$ up to $$$\sqrt n$$$. For each $$$a$$$, compute $$$b$$$ from the first equation and check if the second equation holds. The complexity is $$$O(\sqrt n)$$$. If you want something better, have fun with ugly equations.

→ Reply