problem E tutorial :
My AC code: https://codeforces.net/contest/50/submission/210541474

• Observations:
• We can classify roots into two types, rational and irrational.
• We observe that irrational roots are always unique.

• So, we can count rational and irrational roots separately.
• For counting irrational root, iterate on $$$b$$$ from 1 to $$$N$$$, and try to find several valid c such that $$$b^2 - c$$$ is not a perfect square. This can be done by a contradictory way of first finding all $$$(b,c)$$$ pairs where $$$b^2 - c$$$ is a perfect square and subtracting from the possible ways in $$$O(1)$$$.

• This first part of the solution can be done in $$$O(N)$$$ overall. Even binary search can be done to find $$$C$$$'s lower and upper limits for a fixed $$$B$$$. This takes $$$O(NlogN)$$$, which is also accepted.

  The second part of the solution is to count all integer roots, which can be done in $$$O(N)$$$.

• It is easy to show that our roots lie in the range $$$[-N, -1]$$$.
• We can iterate over root, say R from $$$[-N, -1]$$$ to count the answer.
• For each R, check whether a valid $$$B$$$ and $$$C$$$ exist; this can be checked by following the relation $$$r^2 +2br + c = 0$$$.

• The overall solution becomes $$$O(N)$$$ which is accepted due to the time limits (~5sec).