Rezolvare PBinfo #1437

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 \over 34\) . O fracție poate fi ireductibilă sau se poate
simplifica. În exemplul precedent, \( 2010 \over 34\) se simplifică prin 2 și rezultă \( 1005 \over 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 ieșire

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

1 4
8 4
3 2
1 6
12 6

fractii4.out

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

2 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.