Count solutions of a equation with a constraint
Repeating work

Suppose one test case were 9747 and another test case were 9748.  Right now, you do the full work for each test case, throwing away the work done for other test cases.  This causes your program to take a long time if there are many large test cases.

There is a way to compute all the answers for each of the 10000 test cases in one computation, so you can immediately find the answer to any test case instantly after that.

Sieve-like algorithm

This algorithm works similar to the Sieve of Eratosthenes.  It loops through each (x,y,z) combination and increments count[n] by one.  Once that is done, count[n] is the answer for any test case n.

#include &lt;stdio.h&gt;

#define MAX        10000
int counts[MAX+1];

int main(void)
{
    int x, y, z, n;

    // For each (x,y,z) combination, increment counts[n] by one, where
    // n = x*y + x*z + y*z, or in other words: n = x*y + z*(x+y)
    for (x = 0; x &lt;= MAX; x++) {
        for (y = 0; y &lt;= x; y++) {
            int sum = x+y;
            for (z = 0, n = x*y; z &lt;= y &amp;&amp; n &lt;= MAX; z++, n += sum) {
                counts[n]++;
            }
        }
    }

    // Read test cases and print out answers.
    do {
        scanf("%d", &amp;n);
        if (n == -1 || n &gt; MAX)
            break;
        printf("%d\n", counts[n]);
    } while(1);

    return 0;
}


Timing comparison

The sieve program takes 0.04 seconds on my computer no matter how many test cases are thrown at it.  The original program took 0.03 seconds for the sample input shown (3 test cases), but it took 0.56 seconds to handle a test input of 20 large test cases (9900..9919).  So as you can see, the original program is \$O(n)\$ on the number of test inputs when it could be made to be \$O(1)\$ using the sieve method.