3118 - Tort O

Cerinţa

Un tort dreptunghiular de dimensiuni MxN trebuie împărţit în porţii pătrate de aceeaşi mărime. Găsiţi numărul minim de porţii care se pot obţine şi dimensiunea L a acestora. Atât dimensiunile dreptunghiului cât şi ale pătratelor în care se împarte sunt numere întregi.

Date de intrare

Fişierul de intrare tort.in va conţine pe prima linie numerele M şi N separate printr-un spaţiu.

Date de ieşire

Fişierul de ieşire tort.out va conţine pe o singură linie, două numere naturale separate printr-un spaţiu, primul fiind numărul minim de porţii, iar celălalt dimensiunea L.

Restricții și precizări

• 1 ⩽ M ⩽ N ⩽ 10000

Exemplu

tort.in

20 24

tort.out

Datele introduse corespund restricțiilor impuse.

30 4

Rezolvare

<syntaxhighlight lang="python" line> def validare_date(n):

   flag = False
   if n.isdigit():
       if 0 <= int(n) <= 1_000:
           flag = True
   return flag

def validare_date(m):

   flag = False
   if m.isdigit():
       if 0 <= int(m) <= 1_000:
           flag = True
   return flag

def gcd(a, b):

   #Funcție care calculează CMMD folosind algoritmul Euclid
   while b:
       a, b = b, a % b
   return a

def get_min_squares(m, n):

   #Funcție care calculează numărul minim de pătrate și dimensiunea lor
   cmmd = gcd(m, n)
   min_squares = (m * n) // (cmmd ** 2)
   square_size = cmmd
   return min_squares, square_size

if __name__ == "__main__":

   with open("tort.in") as f:
       m, n = map(int, f.readline().split())

   if validare_date(n) and validare_date(m):
       min_squares, square_size = get_min_squares(m, n)

       with open("tort.out", "w") as f:
           f.write(f"{min_squares} {square_size}\n")
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>