Rezolvare completă PbInfo #1437 Fractii4

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Fractii4:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1437 Fractii4

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1437 Fractii4 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!