Question

Moisil++, 2015
#1437 Fractii4-pbinfo
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 201034 . O fracție poate fi ireductibilă sau se poate
simplifica. În exemplul precedent, 201034 se simplifică prin 2 și rezultă 100517.

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.

Indicații de rezolvare


Pentru fiecare fracție se calculează cmmdc-ul cu algoritmul lui Euclid.

Pentru cerința 1), numărul de divizori se calculează folosind formula nrdiv(n) = (k1+1)(k2+1)..(kn+1)
unde k1, k2,…, kn sunt puterile factorilor primi din descompunerea cmmdc-ului.

Pentru cerința 2), se împarte numărătorul și numitorul la cmmdc.
Primesc 60 de puncte. La prima cerinta nu ma descurc

Answer 1

Răspuns:

Ai problema atasata mai jos.

Explicație:

7ea658de2aac29994ccc698828839dbb.txt