Обернені трикутні числа#6008

Обернені трикутні числа (Розбір)

Нехай $k$ — кількість точок на стороні рівностороннього трикутника. Тоді загальне число точок, необхідних для його повної укладки, дорівнює сумі перших $k$ натуральних чисел:

1 + 2 + ... + k = \frac{k \cdot ( k + 1 )}{2}

1 + 2 + ... + k = \frac{k \cdot (k+1)}{2}

Такі числа називаються трикутними.

Нехай задано ціле число $n$ — кількість наявних точок. Необхідно визначити, чи існує таке ціле $k > 0$ k > 0, для якого

\frac{k \cdot ( k + 1 )}{2} = n

\frac{k \cdot (k+1)}{2} = n

Помножимо обидві частини рівняння на $2$ і приведемо його до стандартного квадратного вигляду:

k^{2} + k - 2 n = 0

k^2 + k - 2n = 0

Це квадратне рівняння відносно $k$ . Воно має ціле число розв'язків тоді і тільки тоді, коли його дискримінант є повним квадратом. Дискримінант дорівнює

d = 1 + 8 n

d = 1 + 8n

Отже, число $n$ є трикутним тільки тоді, коли значення $d = 1 + 8 n$ d = 1 + 8n є повним квадратом. У цьому випадку позитивний корінь рівняння задається формулою

k = \frac{- 1 + d}{2}

k = \frac{-1 + \sqrt{d}}{2}

Якщо знайдене значення $k$ є позитивним цілим числом, то число $n$ трикутне, а $k$ — кількість точок на стороні трикутника. В іншому випадку число $n$ не є трикутним.

Приклад

Розглянемо $n = 55$ n = 55. Підставимо це значення в рівняння:

k^{2} + k - 110 = 0

k^2 + k - 110 = 0

Обчислимо дискримінант:

d = 1 + 440 = 441

d = 1 + 440 = 441

Оскільки $441 = 2 1^{2}$ 441 = 21^2 — повний квадрат, рівняння має цілочисельний розв'язок. Позитивний корінь дорівнює

k = \frac{- 1 + 441}{2} = \frac{- 1 + 21}{2} = 10

k = \frac{-1 + \sqrt{441}}{2} = \frac{-1 + 21}{2} = 10

Отже, число $55$ є трикутним і відповідає трикутнику з $10$ точками на стороні.

Реалізація алгоритму

Послідовно обробляємо тести. Читаємо вхідне значення $n$ .

cs = 1;
while (scanf("%lld", &n), n != -1)
{
  printf("Case %d: ", cs++);

Вичислюємо дискримінант квадратного рівняння $d$ .

  d = 1 + 8 * n;

Перевіряємо, чи є дискримінант повним квадратом. Для цього обчислюємо $s d = ⌊ d ⌋$ sd = ⌊\sqrt{d}⌋ і перевіряємо рівність $s d \cdot s d = d$ sd \cdot sd = d. Якщо дискримінант не є повним квадратом, то виводимо рядок "bad".

  sd = (long long)sqrt(d);
  if (sd * sd != d)
  {
    printf("bad\n");
    continue;
  }

Обчислюємо і виводимо позитивний корінь рівняння.

  k = (-1 + sqrt(d)) / 2;
  printf("%lld\n", k);
}