# PBinfo #1437 – Fractii4 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## 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 \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.

## Cod sursă C++

```cpp
#include <cstdio>
using namespace std;
int P, N, a, b;
int main() {
    freopen("fractii4.in","r",stdin);
    freopen("fractii4.out","w",stdout);
    scanf("%d %d\n", &P, &N);
    for(int i = 1; i <= N; ++i) {
        scanf("%d %d\n", &a, &b);
        int r = a % b;
        int auxA = a, auxB = b;
        while(r) {
            auxA = auxB;
            auxB = r;
            r = auxA % auxB;
        }
        if(P == 2) {
            printf("%d/%d\n", a / auxB, b / auxB);
        }
        else {
            if(auxB == 1) {
                printf("-1\n");
            }
            else {
                int d = 2;
                int answer = 1;
                int putere = 0;
                while(d <= auxB) {
                    while(auxB % d == 0) {
                        ++putere;
                        auxB /= d;
                    }
                    if(d == 2) {
                        ++d;
                    }
                    else {
                        d += 2;
                    }
                    answer *= putere + 1;
                    putere = 0;
                }
                printf("%d\n", answer - 1);
            }
        }
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1437)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1437/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1437/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)