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

#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.")

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.