Editing 2915 - Sum Square

==Cerința==
Se dă numărul natural <span style=“color: red”>n</span>. 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 <span style=“color: red”>n</span>, în ordine crescătoare, sau mesajul <span style=“color: red”>NU</span> în caz contrar.

==Date de intrare==
Programul citește de la tastatură numărul <span style=“color: red”>n</span>;

==Date de ieșire==
Programul va afișa pe ecran cele <span style=“color: red”>2</span> pătrate care alcătuiesc numărul sau mesajul <span style=“color: red”>NU</span> în cazul în care nu există.

==Restricții și precizări==
<span style=“color: red”>1≤n≤1015</span>
dacă există mai multe perechi de pătrate perfecte a căror sumă este <span style=“color: red”>n</span>, poate fi afișată oricare

==Exemplu:==
Intrare
169

Ieșire
25 144

==Rezolvare==
<syntaxhighlight lang="python" line>
import math

def validate_input(n):
    """Functie de validare"""
    if not 1 <= n <= 10**15:
        print("Numarul introdus trebuie sa fie intre 1 si 10^15.")
        return False
    return True

def read_input():
    """Functie de citire"""
    n = int(input("Introduceti numarul: "))
    if not validate_input(n):
        return read_input()
    return n

def main():
    n = read_input()

    for a in range(int(math.sqrt(n))+1):
        b = math.sqrt(n - a*a)
        if b == int(b):
            print(a, int(b))
            return

    print("NU")

if __name__ == '__main__':
    main()
  </syntaxhighlight>

==Explicatie==
Funcția validate_input verifică dacă numărul n se încadrează în restricțiile impuse și returnează True dacă este valid sau False dacă nu este valid.

Funcția read_input primește input-ul de la utilizator și verifică dacă este valid folosind funcția validate_input. Dacă input-ul este valid, funcția returnează valoarea citită, altfel cere utilizatorului să introducă din nou un input valid.

Funcția main citește input-ul folosind funcția read_input. Apoi, parcurgem toate valorile a de la 0 la rădăcina pătrată a lui n, căutând o valoare b astfel încât aa + bb = n. Dacă găsim o astfel de valoare, afișăm cele două pătrate perfecte și ieșim din program cu return. Dacă nu găsim nicio pereche de pătrate perfecte, afișăm "NU".

Pentru a determina dacă un număr poate fi scris ca sumă de două pătrate perfecte, putem folosi teorema lui Fermat: orice număr prim de forma 4k+1 poate fi scris ca sumă de două pătrate perfecte. Mai mult decât atât, un număr întreg pozitiv poate fi scris ca sumă de două pătrate perfecte dacă și numai dacă fiecare factor prim din reprezentarea sa care este congruent cu 3 modulo 4 apare de un număr par de ori. În acest caz, putem găsi cele