I've come across this problem in my studies. I was wondering if there is a better algorithm for it: Given a fixed positive integer $T$, count the solutions of $$n^2 + n m + m^2 = T$$ where $m$ and $n$ are integers.
I've come up with an $\mathcal{O}(\sqrt{T})$ algorithm.
Basically you can iterate $n$ from $\lfloor\sqrt{T/3}\rfloor$ to $\lfloor 2\sqrt{T/3}\rfloor$ and solve the quadratic equation for $m$ to get all the possible solutions. I won't go into the gory details here. Is there a faster way to count these solutions?
Update Added a TL/DR version of the best answer. Thanks to Will Jagy for the solution and references.
Answer: Let $T = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_r^{a_r}$ If any $p_i$ is equal to 2 mod 3, and its exponent ($a_i$) is odd, then the number of solutions is zero. If $a_i$ is even, then it does not affect the number of solutions and can be ignored. So assume that all primes dividing $T$ are equal to 1 mod 3. Then the answer is $$p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_r^{a_r} \mapsto 6*(1 + a_1)(1 + a_2)(1 + a_3)\cdots (1 + a_r)$$
it is in Dickson's little 1929 book, page 77, exercises 3 and 4. That is, when $m$ has $r$ distinct prime factors, each congruent to $1 \pmod 3,$ then there are exactly $6 \cdot 2^r$ proper representations $m=x^2 + xy + y^2.$ If you want to include all representations and some exponents are larger than one, you may divide $m$ by each square that divides it and add.
You should be aware that, if a prime $q \equiv 2 \pmod 3,$ and the exponent of $q$ in factoring $m$ is odd, then there are no representations at all. If the exponent is even, dividing by $q^2$ does not change the number of representations, so just ignore those: the number of representations of $25$ is the same as the number of representations of $1.$
http://www.abebooks.com/servlet/SearchResults?an=dickson&sts=t&tn=introduction+to+the+theory+of+numbers