Əks üçbucaq sayılar#6008

Əks üçbucaq sayılar (Həll təhlili)

Qoy $k$ — bərabəryanlı üçbucağın tərəfi üzərindəki nöqtələrin sayıdır. Onda onu tam örtmək üçün lazım olan nöqtələrin ümumi sayı ilk $k$ natural ədədlərinin cəminə bərabərdir:

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

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

Belə ədədlər üçbucaq ədədləri adlanır.

Qoy $n$ tam ədədi — verilmiş nöqtələrin sayı olsun. Mümkündürsə, belə bir müsbət tam $k$ ədədi tapmaq lazımdır ki,

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

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

Tənliyin hər iki tərəfini $2$ -yə vuraq və onu standart kvadrat formasına gətirək:

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

k^2 + k - 2n = 0

Bu $k$ ilə bağlı kvadrat tənlikdir. Onda tam həll olduğu yalnız o halda mümkündür ki, onun diskriminantı tam kvadrat olsun. Diskriminant belə alınır:

d = 1 + 8 n

d = 1 + 8n

Deməli, $n$ ədədinin üçbucaq olması yalnız o halda mümkündür ki, $d = 1 + 8 n$ d = 1 + 8n tam kvadrata bərabər olsun. Bu halda müsbət həll aşağıdakı formul ilə göstərilir:

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

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

Əgər tapılmış $k$ dəyəri müsbət tam ədəddirsə, onda $n$ üçbucaq ədədidir və $k$ üçbucağın tərəfi üzərindəki nöqtələrin sayıdır. Əks halda, $n$ üçbucaq ədədi deyil.

Nümunə

$n = 55$ n = 55-i nəzərdən keçirək. Bu qiyməti tənliyə yerləşdirək:

k^{2} + k - 110 = 0

k^2 + k - 110 = 0

Diskriminantı hesablayırıq:

d = 1 + 440 = 441

d = 1 + 440 = 441

Çünki $441 = 2 1^{2}$ 441 = 21^2 tam kvadrata uyğundur, bu tənlik tam həllə malikdir. Müsbət həll isə aşağıdakı kimi olur:

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

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

Deməli, $55$ ədədi üçbucaq ədədidir və $10$ nöqtəli üçbucaq təşkil edir.

Algoritmin reallaşdırılması

Testləri ardıcıl olaraq işləyirik. Girişdə $n$ dəyərini oxuyuruq.

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

Kvadrat tənliyin diskriminantını $d$ hesablayırıq.

  d = 1 + 8 * n;

Diskriminantın tam kvadrat olub-olmadığını yoxlayırıq. Bunun üçün $s d = ⌊ d ⌋$ sd = ⌊\sqrt{d}⌋ hesablayaraq, $s d \cdot s d = d$ sd \cdot sd = d olduğunu təsdiq edirik. Əgər diskriminant tam kvadrat deyilsə, "bad" sətri çıxılır.

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

Tənliyin müsbət həllini hesablamaq və çıxışa vermək üçün:

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