How to count the solutions of the equation xy + xz + y*z = n (0 <= n <= 10^4) with the constraint that x >= y >= z >= 0 ?
To solve this i've isolated the z value and brute-forced the values of x and y. If the values x,y,z satisfy the constraint and equation than its a valid solution.
#include <stdio.h>
int main () {
int x,y,z,n,counter;
while ( scanf("%d", &n), n != -1 ) {
counter = 0;
for ( x = n ; x >= 0; --x ) {
for ( y = x ; y > 0 ; --y ) {
z = (n - x*y);
//negative z isn't valid
if(z < 0)
continue;
z /= (x + y);
if( z <= y && y <= x && x*y + x*z + y*z == n ) {
++counter;
}
}
}
printf("%d\n",counter);
}
return 0;
}
The input contains several lines with one value for n. The program must stop when this value is -1.
The output is the number of solutions of the equation in separated lines.
Sample Input:
20
1 9747 -1
Sample Output:
5
1 57
How to make this code faster ?