6008. Inverse triangular numbers

A triangular number is a number that can be represented as a set of points arranged in an equilateral triangle with n points on each side. Below are several examples of such triangles and their corresponding triangular numbers:

It is easy to see that a triangular number is an additive analogue of the factorial:

Given an integer n, determine whether it is a triangular number. If the number is triangular, you must also determine the number of points on each side of the corresponding triangle.

For example, if n = 10, the program should report that this is a triangular number with 4 points on each side, since

10 = 4 + 3 + 2 + 1

If n = 11, the program should report that it is not a triangular number.

Input. Each line contains one integer n (0 < n < 10⁹). The last line contains -1 and should not be processed.

Output. For each value of n, determine whether it is a triangular number. If it is, print the number of points on a side on a separate line. Otherwise, print the string “bad”.

Sample input	Sample output
55 1 91 587 499500 -1	Case 1: 10 Case 2: 1 Case 3: 13 Case 4: bad Case 5: 999

SOLUTION

combinatorics

Algorithm analysis

Let k be the number of points on a side of an equilateral triangle. Then the total number of points required to fill the triangle completely is equal to the sum of the first k positive integers:

1 + 2 + … + k =

Such numbers are called triangular numbers.

Suppose an integer n is given – the number of available points. It is necessary to determine whether there exists an integer k > 0 such that

= n

Multiplying both sides of the equation by 2 and rewriting it in the standard quadratic form:

k² + k – 2n = 0

This is a quadratic equation in k. It has an integer solution if and only if its discriminant is a perfect square. The discriminant is

d = 1 + 8n

Therefore, the number n is triangular if and only if the value d = 1 + 8n is a perfect square. In this case, the positive root of the equation is given by

k =

If the obtained value of k is a positive integer, then n is a triangular number and k is the number of points on a side of the triangle. Otherwise, the number n is not triangular.

Example

Consider n = 55. Substituting this value into the equation, we obtain:

k² + k – 110 = 0

Compute the discriminant:

d = 1 + 440 = 441

Since 441 = 21² is a perfect square, the equation has an integer solution. The positive root is

k = = = 10

Therefore, the number 55 is triangular and corresponds to a triangle with 10 points on each side.

Algorithm implementation

Process the test cases sequentially. Read the input value n.

cs = 1;

while (scanf("%lld", &n), n != -1)

{

printf("Case %d: ", cs++);

Compute the discriminant d of the quadratic equation.

d = 1 + 8 * n;

Check whether the discriminant is a perfect square. To do this, compute sd = and verify whether sd * sd = d. If the discriminant is not a perfect square, print the string “bad”.

sd = (long long)sqrt(d);

if (sd * sd != d)

{

printf("bad\n");

continue;

}

Compute and print the positive root of the equation.

k = (-1 + sqrt(d)) / 2;

printf("%lld\n", k);

}