4196 - MPF

Enunt

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.

Exemplul 1

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.

Rezolvare

<syntaxhighlight lang="python" line> def max_prime_factor(x):

   factor = 2
   while factor * factor <= x:
       if x % factor == 0:
           x //= factor
       else:
           factor += 1
   return x

with open("input.in", "r") as fin:

   q = int(fin.readline())
   pairs = [tuple(map(int, line.split())) for line in fin]

with open("output.out", "w") as fout:

   for pair in pairs:
       x, y = pair
       if x == y:
           fout.write("0\n")
       elif max_prime_factor(x) == max_prime_factor(y):
           fout.write("1\n")
       else:
           fout.write("2\n")

</syntaxhighlight>