1437 - Fractii 4

Enunţ

Se dă un șir de n fracții. Fiecare fracție este dată printr-o pereche de numere reprezentând numărătorul și numitorul fracției. De exemplu 2010 34 reprezintă fracția 2010/34. O fracție poate fi ireductibilă sau se poate simplifica. În exemplul precedent, 2010/34 se simplifică prin 2 și rezultă 1005/17.

Cerinţa

Să se afișeze, pentru fiecare fracție:

1) Prin câte moduri distincte se poate simplifica. 2) Fracția ireductibilă.

Date de intrare

În fișierul de intrare fractii4.in pe prima linie se găsesc numerele P și n, iar pe următoarele n linii se găsesc n perechi de numere, reprezentând numărătorul și numitorul fiecărei fracții, separate printr-un spațiu.

Date de iesire

Pe fiecare din cele n linii ale fișierului fractii4.out se găsesc, pentru fiecare fracție, în ordinea dată în fișierul de intrare:

1) Dacă P = 1, numărul de simplificări distincte posibile. Dacă nu este posibilă nicio simplificare (fracția este ireductibilă) se va afișa -1. 2) Dacă P = 2 , fracția ireductibilă, numărătorul și numitorul fiind separați prin /.

Restricții și precizări

• n ⩽ 100 000
• 0 < numitor, numărător < 2 000 000
• P este 1 sau 2

Exemplul 1

fractii4.in

11 4

8 4

3 2

1 6

12 6

fractii4.out

Datele introduse corespund restricțiilor impuse.

2

-1

-1

3

Explicație

Pentru acest test 'P = 1, deci se va rezolva doar cerinţa 1). Prima fracție se poate simplifica prin 2 moduri: prin 2 și 4. A doua este ireductibilă, deci se va afișa -1. A treia este ireductibilă, deci se va afișa -1. A patra se poate simplifica prin 3 moduri: 2, 3 și 6.

Exemplul 2

fractii4.in

12 3

22 6

11 4

125 25

fractii4.out

11/3

11/4

5/1

Explicație

Pentru acest test P = 2, deci se va rezolva doar cerinţa 2). Prima fracție se simplifică prin 2. A doua fracție este ireductibilă, deci va fi afișată fără schimbare. Ultima fracție poate fi redusă prin 25 și devine ireductibilă. Chiar dacă numitorul este 1, acesta va fi afișat.

Rezolvare

<syntaxhighlight lang="python" line> import math

def prim(n):

   if n == 0 or n == 1:
       return 0
   if n == 2:
       return 1
   if n % 2 == 0:
       return 0
   else:
       for i in range(3, int(math.sqrt(n))+1, 2):
           if n % i == 0:
               return 0
   return 1

def prime(a, b):

   if b == 0:
       return a
   else:
       return prime(b, a % b)

def validare_date(n, p):

   if n <= 100000 and p in [1, 2]:
       return True
   else:
       return False

if __name__ == '__main__':

   fin = open("fractii4.in", "r")
   fout = open("fractii4.out", "w")
   p, n = map(int, fin.readline().split())
   if validare_date(n, p):
       print("\nDatele de intrare corespund restrictiilor impuse.\n")
       for i in range(n):
           a, b = map(int, fin.readline().split())
           x, y = a, b
           if p == 1:
               if prim(a) == 0 and prim(b) == 0 and prime(a, b) == 1:
                   d = 0
                   d1 = prime(a, b)
                   for j in range(1, int(math.sqrt(d1))+1):
                       if d1 % j == 0:
                           d += 2
                           if j * j == d1:
                               d -= 1
                   fout.write(str(d-1) + '\n')
               else:
                   fout.write("-1\n")
           else:
               t = prime(a, b)
               fout.write(str(x//t) + '/' + str(y//t) + '\n')
       fin.close()
       fout.close()
   else:
       print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>