2915 - Sum Square

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≤1015 dacă există mai multe perechi de pătrate perfecte a căror sumă este n, 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