SumSquare


Rezolvarea problemei SumSquare (https://www.pbinfo.ro/probleme/2915/sumsquare) de pe site pbinfo cu explicatii:

Cerința

Se dă numărul natural n. Determinați dacă numărul se poate scrie ca sumă de două pătrate perfecte. Dacă da, afișați două pătrate perfecte a căror sumă este n, în ordine crescătoare, sau mesajul NU în caz contrar.

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 care nu există.

Restricții și precizări

  • 1 ≤ n ≤ 10^15
  • dacă există mai multe perechi de pătrate perfecte a căror sumă este n, poate fi afișată oricare

Daca se incearca scrierea lui n ca suma de 2 patrate perfecte, atunci in prima rezolvare te vei gandi sa mergi cu a de la 1 pana la radacina patrata din n si cu b la fel.

Ca sa reduci numarul de iteratii care pentru limitele problemei va fi foarte mare, iti recomand sa te gandesti ca daca in suma a*a+b*b a creste pana la o limita l atunci b scade pana la acea limita. Deci putem scrie:

n = 2 * l * l deci l = sqrt(n / 2)

Parcurgi deci o bucla repetitiva cu a de la 1 la l in care il determini pe b ca fiind:

b = sqrt(n – a * a)

Codul programului ar fi:

#include <iostream>
#include <cmath>

#define ll long long

using namespace std;

int main() {
    ll n, a, b, l;
    cin >> n;
    l = (ll)(sqrt(n / 2));

    for (a = 1; a <= l; a++)
    {
        b = sqrt(n - a * a);
        if (a * a + b * b == n)
        {
          cout<<a*a<<" "<<b*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.