SumTriunghiular


Rezolvarea problemei  SumTriunghiular (https://www.pbinfo.ro/probleme/2904/sumtriunghiular) de pe site pbinfo cu explicatii:

Cerința

Se dă un număr natural n. Să se determine dacă numărul se poate scrie ca sumă de două numere triunghiulare.
Dacă este posibil se vor afișa două numere triunghiulare a căror sumă este egală cu n, în orice ordine, respectiv mesajul NU în caz contrar.

Un număr triunghiular este numărul de puncte dintr-un triunghi echilateral umplut uniform cu puncte. De exemplu, 1361015 sunt numere triunghiulare.

Date de intrare

Programul citește de la tastatură numărul n;

Date de ieșire

Programul va afișa pe ecran cele 2 pătrate care alcătuiesc numărul sau mesajul NU în cazul în carProgramul va afișa pe ecran, în orice ordine, două numere triunghiulare care însumate dau numărul n, separate printr-un spațiu, sau mesajul NU dacă numărul nu poate fi scris ca suma de două numere triunghiulare.

Restricții și precizări

  • 1 ≤ n ≤ 10^12
  • numerele triunghiulare determinate pot fi identice.

Conform https://ro.wikipedia.org/wiki/Num%C4%83r_triunghiular:

Un număr triunghiular este numărul de puncte dintr-un triunghi echilateral umplut uniform cu puncte. De exemplu, trei puncte pot forma un triunghi și deci 3 este un număr triunghiular. Al n-lea număr triunghiular este numărul de puncte dintr-un triunghi cu n puncte pe latură.

Echivalent, un număr triunghiular este suma primelor n numere naturale de la 1 la n.

{\displaystyle T_{n}=1+2+3+\dotsb +(n-1)+n={\frac {n(n+1)}{2}}}

Deci trebuie sa vedem daca un numar n dat poate fi scris ca o suma

n = a + b

unde a si b sunt ambele numere triunghiulare.

Vom parcurge bucla dupa a dar acesta este ales numai dintre numerele triunghiulare si vom calcula b ca fiind:

b = n – a

Problema care trebuie avuta in vedere este ca si b sa fie de asemenea triunghiular. Verificam acest lucru folosind o functie care va raspunde cu 0 daca numarul nu este triughiular sau cu 1 daca este triunghiular.

Codul programului ar fi:

#include <iostream>
#include <cmath>

#define ll long long

using namespace std;
int triunghiular(ll m){
    ll k = sqrt(2*m);
    return k*(k+1) == 2*m;
}

int main() {
    ll n;
    cin >> n;

    for (ll i=1, a=1; 2*a<=n; i++, a+=i) {
        ll b = n-a;
        if (triunghiular(b)) {
           cout<<a<<" "<<b; return 0;
        }
    }
        
   	cout<<"NU";
    return 0;
}

Incearca sa rezolvi si tu si vezi daca obtii rezultatele corecte!

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

Acest site folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.