Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

v-O_O-v's blog

Can we do this problem in a better way

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

214A - Система уравнений 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

»
7 years ago, hide # |
← 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
»
7 years ago, hide # |
 
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