0285 - X2Y2K

Sursa: [1]

Cerinţa

Se dă un număr natural, k. Să se determine toate perechile de numere naturale nenule x, y (x<=y), cu proprietatea că x2+y2=k .

Date de intrare

Programul citește de la tastatură numărul k.

Date de ieșire

Programul afișează perechile x, y determinate, câte o pereche pe o linie a ecranului, în ordinea crescătoare a valorii lui x.

Dacă datele sunt introduse corect, programul va rula.

În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

2 ≤ k ≤ 1.000.000.000

pentru toate valorile lui k utilizate în teste există cel puţin o soluţie

Exemplul 1

Intrare

1000000

Ieșire

280 960

352 936

600 800

Rezolvare

<syntaxhighlight lang="python" line>

1. 0285

import math

def is_sum_of_squares(x, y, k):

   """
   Returns True if x^2 + y^2 is equal to k, False otherwise.
   """
   return x**2 + y**2 == k

def has_valid_factors(k):

   """
   Returns True if k has only factors of the form 4n+1, False otherwise.
   """
   for i in range(2, int(math.sqrt(k))+1):
       if k % i == 0:
           p = 0
           while k % i == 0:
               k //= i
               p += 1
           if i % 4 == 3 and p % 2 != 0:
               return False
   if k % 4 == 3:
       return False
   return True

def find_sum_of_squares_pairs(k):

   """
   Finds all pairs of natural numbers (x,y) such that x^2 + y^2 is equal to k.
   Returns a list of tuples.
   """
   pairs = []
   for x in range(1, int(math.sqrt(k))+1):
       for y in range(x, int(math.sqrt(k))+1):
           if is_sum_of_squares(x, y, k) and has_valid_factors(k):
               pairs.append((x, y))
   return pairs

if __name__ == '__main__':

   k = int(input("Introduceti valoarea lui k: "))
   if 2 <= k <= 1000000000:
       pairs = find_sum_of_squares_pairs(k)

       if pairs:
           for pair in pairs:
               print(pair[0], pair[1])
       else:
           print("Nu exista perechi (x,y) cu x, y > 0 astfel incat x^2 + y^2 = k.")
   else:
       print("k trebuie sa fie intre 2 si 1000000000, inclusiv.") 

</syntaxhighlight>

Explicatie cod:

Acest cod contine trei functii care lucreaza impreuna pentru a gasi toate perechile de numere naturale (x,y) astfel incat x^2 + y^2 sa fie egal cu k. Mai exact:

is_sum_of_squares(x, y, k) verifica daca x^2 + y^2 este egal cu k si returneaza True sau False in consecinta.

has_valid_factors(k) verifica daca toate factorii lui k sunt de forma 4n+1 si returneaza True sau False in consecinta.

find_sum_of_squares_pairs(k) parcurge toate perechile de numere naturale (x,y) cu x <= y si verifica daca x^2 + y^2 este egal cu k si daca k are doar factori de forma 4n+1. Daca conditiile sunt satisfacute, perechea este adaugata la o lista si, la sfarsit, lista este returnata.

La final, codul verifica daca valoarea k introdusa de utilizator este intre 2 si 1000000000, inclusiv. Daca nu este, se afiseaza un mesaj de eroare. Daca este, se cauta toate perechile (x,y) astfel incat x^2 + y^2 = k si se afiseaza rezultatul, sau un mesaj care indica ca nu exista astfel de perechi. De asemenea, toate acestea se intampla doar daca acest script este rulat direct (if name == 'main':), nu daca este importat ca modul in alt script.