Skip to main content
1 of 3
Felipe
  • 597
  • 1
  • 5
  • 13

Count solutions of a equation with a constraint

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 ?

Felipe
  • 597
  • 1
  • 5
  • 13