Răspuns:
#include <iostream>
using namespace std;
long long n, aux;
int main()
{
cin >> n;
long long left = 1, right = n;
for(int i = 1; i <= right; i++) {
if(1LL * i * (i + 1) / 2 > n) { // am folosit 1LL deoarece i * (i + 1) / 2 poate sa fie long long, si long long nu poate fi stocat de acel if daca noi nu ii zicem dinainte ca este long long, si de accea 1LL atentioneaza if-ul ca avem un rezultat long long
right = i;
break;
}
}
while(left <= right) {
aux = left * (left + 1) / 2 + right * (right + 1) / 2;
if(aux == n) {
cout << left * (left + 1) / 2 << " " <<right * (right + 1) /2;
return 0;
}
if(aux > n) {
right--;
} else if(aux < n) {
left++;
}
}
cout <<"NU";
return 0;
}
Explicație:
Formula unui numar triangular este n * (n + 1) / 2, n fiind sursa de unde provine numarul triangular, de exemplu sursa lui 15 este 5
Generam primele n numere triunghiulara pana la n, pentru a stii la ce indice ne oprim, apoi folosim un fel.. de cautare binara
In aceasta "cautare binara" folosim urmatoarea idee
Stanga va fi egal cu 1, ca e inceputul, iar Dreapta va fi egala cu indicele calculat de noi mai sus
Cat timp Stanga <= Dreapta incepem cautarea, daca sursele noastre(stanga + dreapta) au alcatuit numarul nostru triangular , ne oprim si AFISAM NUMERELE TRIANGULARE, atentie, nu sursele! adica st * (st + 1) / 2 si dr * (dr + 1) / 2. Daca nu verificam, numarul format este mai mare ca n? daca e mai mare inseamna ca sursa dreapta e mult prea mare si o micsoram cu 1, daca numarul format e mai mic, inseeamna ca sursa dreapta e deja la maximul ei, si noi tot ce putem face e sa incrementam sursa stanga pentru a incerca sa obtinem rezultatul dorit.
Intr-un final, daca nimic nu s-a intamplat, si programul inca functioneaza inseamna ca numarul nu e triangular si afisam NU
