# PBinfo #4196 – MPF – Rezolvare C++

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

## Enunț

Fie X un număr natural nenul și p cel mai mare factor prim din descompunerea în factori primi a lui X. Pentru X = 1, considerăm p = 1. Asupra lui X se pot efectua următoarele două operații:


Operația 1: X se împarte la p și devine X / p;
Operația 2: X devine X * k, unde k este un număr prim și mai mare sau egal decât p.

Cerința
Se dau Q perechi de numere naturale nenule (X, Y). Să se determine, pentru fiecare pereche, numărul minim de operații necesare pentru a-l transforma pe X în Y.

Date de intrare
Datele de intrare conțin Q + 1 linii. Pe prima linie se găsește Q reprezentând numărul de perechi (X, Y).
Pe următoarele Q linii, câte o pereche de numere naturale nenule X și Y, despărțite printr-un singur spațiu.

Date de ieșire
Ieșirea va conține Q linii. Pe fiecare linie i se va scrie câte un număr natural reprezentând, numărul de
operații determinat pentru a i-a pereche.

Restricții și precizări

1 ≤ Q ≤ 1.000.000
1 ≤ X, Y ≤ 4.000.000
Datorită dimensiunii mari a datelor de intrare și de ieșire, doar unele teste au fost adăugate.

Exemplu:
Intrare

4
4 10
2 9
6 2
12 12
Ieșire

2
3
1
0
Explicație
Pentru (4, 10): 4 devine 2 utilizând o Operație 1, apoi devine 10 utilizând o Operație 2.
Pentru (2, 9): 2 devine 1 utilizând o Operație 1, apoi devine 3 folosind o Operație 2 și devine 9 folosind o Operație 2.
Pentru (6, 2): 6 devine 2 folosind o Operație de tip 1.
Pentru (12, 12): Numerele sunt egale, nu este necesară nicio operație.

## Cod sursă C++

```cpp
#include <iostream>
#include <cstdio>
#define XMAX 4000000
#define PMAX 500000
#define FMAX 50
using namespace std;
//FILE * fin=fopen("mpf.in","r");
//FILE * fout=fopen("mpf.out","w");
//ifstream fin("308.in");
//ofstream fout("mpf.out");
bool ciur[XMAX];
int prime[PMAX];
int nrp, nrx, nry, nrmin;
int fx[FMAX];
int mx[FMAX];
int fy[FMAX];
int my[FMAX];
void eratostene();
void desc(int x, int&nrx, int fx[], int mx[]);
int rezolva();
int main()
{int i, q, x, y;
ios_base :: sync_with_stdio(false);  
   cin.tie(nullptr);  
 //cin>>q;
 scanf("%d", &q);
 eratostene();
 for (i=0; i<q; i++)
     {
      //cin>>x>>y;
      scanf("%d %d", &x, &y);
      desc(x,nrx,fx,mx);
      desc(y,nry,fy,my);
      nrmin=rezolva();
      //cout<<nrmin<<'\n';
      printf("%d\n",nrmin);
     }
  //fout.close();
//  fclose(fout);
  return 0;
}
void eratostene()
{int i, j;
 ciur[0]=ciur[1]=1;
 for (i=2; i*i<XMAX; i++)
     if (ciur[i]==0)
         for (j=i*i; j<XMAX; j+=i) ciur[j]=1;
 prime[1]=2; nrp=1;
 for (i=3; i<XMAX; i+=2)
      if (ciur[i]==0) prime[++nrp]=i;
 }
 void desc(int x, int& nrx, int fx[], int mx[])
 {int i, m;
  if (ciur[x]==0) {nrx=1; fx[nrx]=x; mx[nrx]=1; return;}
  nrx=0;
  for (i=1; prime[i]*prime[i]<=x; i++)
      {
        m=0;
        while (x%prime[i]==0) {x/=prime[i]; m++;}
        if (m) {++nrx; fx[nrx]=prime[i]; mx[nrx]=m;}
      }
 if (x>1) {++nrx; fx[nrx]=x; mx[nrx]=1;}
 }
 int rezolva()
 {int rez=0;
  int i, j, unde;
  if (nrx==0) {for (i=1; i<=nry; i++) rez+=my[i]; return rez;}
  if (nry==0) {for (i=1; i<=nrx; i++) rez+=mx[i]; return rez;}
  unde=nrx; if (nry<unde) unde=nry;
  for (i=1; i<=unde; i++)
       if (fx[i]!=fy[i] || fx[i]==fy[i] && mx[i]!=my[i]) break;
  if (i<=nrx && i<=nry && fx[i]==fy[i]) if (mx[i]<my[i]) rez+=my[i]-mx[i];
                         else rez+=mx[i]-my[i];
      else i--;
   for (j=i+1; j<=nrx; j++) rez+=mx[j];
   for (j=i+1; j<=nry; j++) rez+=my[j];
   return rez;
 }
```

## Resurse

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