Блог пользователя v-O_O-v

Can we do this problem in a better way

Автор v-O_O-v, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

$$$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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить