Растављања на збир узастопних - Решење

Испробавање свих могућности за први члан, па за дужину

Први покушај може бити решавање проблема грубом силом, тј. испробавање свих могућих првих чланова збира. Најмањи могући први члан је \(a_0 = 1\). Пошто збир мора да буде бар двочлан, највећи могући први члан је онај број \(a_0\) такав да је \(a_0 + (a_0 + 1) \leq n\). Када смо одредили први члан, одређујемо колико сабирака треба узети да би се добио збир \(n\). Крећемо од двочланог низа и затим додајемо један по један наредни сабирак све док збир не достигне или не престигне збир \(n\). Бројач увећавамо ако је након петље збир једнак вредности \(n\) (тада је успешно нађено једно решење).

#include <iostream>

using namespace std;

int brojNacina(int n) {
  int broj = 0;
  for (int a0 = 1; a0 + (a0+1) <= n; a0++) {
    int zbir = a0 + (a0+1);
    for (int ai = a0 + 2; zbir < n; ai++)
      zbir += ai;
    if (zbir == n)
      broj++;
  }
  return broj;
}


int main() {
  int n;
  cin >> n;
  cout << brojNacina(n) << endl;
  return 0;
}

Испробавање свих могућности за дужину, па за први члан

Редослед петљи може бити другачији. Спољном петљом можемо одређивати број сабирака \(m\), а унутрашњом испробавати вредности почетног сабирка. Крећемо од два сабирка. Највећи могући број сабирака наступа када је \(a_0 = 1\), и пошто је \(a_0 + (a_0 + 1) + \ldots + (a_0 + (m-1)) = m \cdot a_0 + \frac{m(m-1)}{2}\), да би збир могао да евентуално буде \(n\) мора да важи да је \(m + \frac{m(m-1)}{2} \leq n\).

#include <iostream>

using namespace std;

int brojNacina(int n) {
  int broj = 0;
  for (int m = 2; m + m*(m-1)/2 <= n; m++) {
    int a0 = 1;
    int zbir = a0*m + m*(m-1)/2;
    while (zbir < n) {
      a0++;
      zbir = a0*m + m*(m-1)/2;
    }
    if (zbir == n)
      broj++;
  }
  return broj;
}

int main() {
  int n;
  cin >> n;
  cout << brojNacina(n) << endl;
  return 0;
}

Испробавање свих могућности за дужину и израчунавање првог члана

Кључна оптимизација наступа када увидимо да нам унутрашња петља није потребна. Наиме, нема потребе испробавати различите вредности \(a_0\), већ се \(a_0\) може израчунати на основу \(m\) и \(n\). Ако је \(m \cdot a_0 + \frac{m(m-1)}{2} = n\), тада је \(a_0 = \frac{n - \frac{m(m-1)}{2}}{m}\). Збир са \(m\) сабирака постоји ако и само ако је ово цео број (што се може проверити испитивањем остатка при дељењу бројева \(n - \frac{m(m-1)}{2}\) и \(m\)). Услов \(m + \frac{m(m-1)}{2} \leq n\) гарантује да је \(a_0 \geq 1\).

Напоменимо да је редослед провера био веома важан, јер је једначина линеарна по \(a_0\), а квадратна по \(m\), тако да је за фиксирано \(m\), \(a_0\) прилично једноставно израчунати, док за фиксирано \(a_0\) није једноставно израчунати \(m\).

#include <iostream>

using namespace std;

int brojNacina(int n) {
  int broj = 0;
  for (int m = 2; m + m*(m-1)/2 <= n; m++)
    if ((n - m*(m-1)/2) % m == 0)
      broj++;
  return broj;
}

int main() {
  int n;
  cin >> n;
  cout << brojNacina(n) << endl;
  return 0;
}