|
|
| (6 intermediate revisions by 2 users not shown) |
| 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 ==
| |
| 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>
| |
