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

Dacă datele sunt introduse corect, în fișier se va afișa: "Datele sunt introduse corect.", apoi 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 /. În cazul în care datele nu respectă restricțiile, se va afișa în fișier: "Datele nu corespund restricțiilor impuse.".

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 sunt introduse corect.

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

Datele de intrare sunt introduse corect.

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

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 sunt introduse corect.\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.")