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, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează toate perechile de numere naturale nenule x, y (x<=y), cu proprietatea că x2+y2=k.
În caz contrar, 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
- Datele de intrare
- Introduceti valoarea lui k:
- 1000000
- Datele de ieșire
- Datele sunt introduse corect.
- 280 960
- 352 936
- 600 800
Rezolvare
<syntaxhighlight lang="python" line>
- 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:
print("Datele sunt introduse corect.")
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("Datele nu corespund restricțiilor impuse.")
</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.