|
|
| Line 1: |
Line 1: |
| == 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 de intrare 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 de intrare 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 ==
| |
| <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 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.")
| |
|
| |
| </syntaxhighlight>
| |
