Aflarea sumei primelor N sume Gauss

Dându-se un număr natural n, ne propunem să aflăm valoarea sumei:

1 +
1 + 2 +
1 + 2 + 3 +
… +
1 + 2 + 3 + … + n

Această rezolvare este inspirată după problema SumaGaussDeSumeGauss #3807 de pe PbInfo, cu cerința:

Cerința Se dau n numere naturale. Pentru fiecare numar x, calculati 1+(1+2)+(1+2+3)+(1+2+3+4)+...+(1+2+3+...x).

Algoritmul naiv

Un algoritm naiv calculează suma dintre sumele Gauss: 1 * 2 / 2, 2 * 3 / 2, 3 * 4 / 2, …, n * (n + 1) / 2. Algoritmul are complexitatea O(n), deoarece trebuie să calculăm cele n sume Gauss și să le adunăm.

Explicarea algoritmului eficient

Ne întrebăm cum putem simplifica problema mai mult. Iată o rezolvare matematică, care se poate verifica prin inducție matematică:

Așadar, este îndeajuns să afișăm formula de mai sus.

Rezolvare în C++

#include <iostream>

using namespace std;

int sumaDeSume(int x) {
    return x * (x + 1) * (x + 2) / 6;
}

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

Alte observații pentru rezolvarea problemei SumaGaussDeSumeGauss #3807

Formula prezentată anterior poate ieși din tipul de date long long în timpul înmulțirii. Așadar, luăm cei termeni de înmulțit (n, n + 1, n + 2) și verificăm care se împarte la 2 și care se împarte la 3 — fiind numere consecutive, minim unul se va împărți la 2 și categoric unul se va împărți la 3. Împărțim unul dintre numere la 2, și la 3, iar la final, afișăm produsul numerelor fără să mai împărțim la nimic, deoarece am împărțit mai devreme la 2 și la 3. Iată rezolvarea problemei:

#include <iostream>

using namespace std;

int n;
unsigned long long x, a, b, c;

int main()
{
  cin >> n;
  while(n--) {
    cin >> x;
    a = x;
    b = x + 1;
    c = x + 2;
    if(a % 2 == 0) a /= 2;
    else if(b % 2 == 0) b /= 2;
    else if(c % 2 == 0) c /= 2;

    if(a % 3 == 0) a /= 3;
    else if(b % 3 == 0) b /= 3;
    else if(c % 3 == 0) c /= 3;

    cout << a * b * c << " ";
  }
  return 0;
}