https://wiki.universitas.ro/index.php?action=history&feed=atom&title=4196_-_MPF4196 - MPF - Revision history2026-05-01T10:55:56ZRevision history for this page on the wikiMediaWiki 1.42.1https://wiki.universitas.ro/index.php?title=4196_-_MPF&diff=9962&oldid=prevRebecaBud: Pagină nouă: == 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 natura...2024-06-03T15:26:52Z<p>Pagină nouă: == 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 natura...</p>
<p><b>New page</b></p><div>== Enunt ==<br />
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:<br />
<br />
Operația 1: '''X''' se împarte la '''p''' și devine '''X / p''';<br />
Operația 2: '''X''' devine '''X * k''', unde '''k''' este un număr prim și mai mare sau egal decât '''p'''.<br />
== Cerinţa ==<br />
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'''.<br />
== Date de intrare ==<br />
Datele de intrare conțin '''Q + 1''' linii. Pe prima linie se găsește '''Q''' reprezentând numărul de perechi '''(X, Y)'''.<br />
Pe următoarele '''Q''' linii, câte o pereche de numere naturale nenule '''X''' și '''Y''', despărțite printr-un singur spațiu.<br />
== Date de ieșire ==<br />
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.<br />
== Restricţii şi precizări ==<br />
* '''1 ≤ Q ≤ 1.000.000'''<br />
* '''1 ≤ X, Y ≤ 4.000.000'''<br />
Datorită dimensiunii mari a datelor de intrare și de ieșire, doar unele teste au fost adăugate.<br />
== Exemplul 1 ==<br />
; Intrare<br />
<br />
4<br />
4 10<br />
2 9<br />
6 2<br />
12 12<br />
; Ieșire<br />
<br />
2<br />
3<br />
1<br />
0<br />
== Explicație == <br />
Pentru (4, 10): 4 devine 2 utilizând o Operație 1, apoi devine 10 utilizând o Operație 2.<br />
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.<br />
Pentru (6, 2): 6 devine 2 folosind o Operație de tip 1.<br />
Pentru (12, 12): Numerele sunt egale, nu este necesară nicio operație.<br />
<br><br />
<br />
<br />
<br />
== Rezolvare ==<br />
<syntaxhighlight lang="python" line><br />
def max_prime_factor(x):<br />
factor = 2<br />
while factor * factor <= x:<br />
if x % factor == 0:<br />
x //= factor<br />
else:<br />
factor += 1<br />
return x<br />
<br />
with open("input.in", "r") as fin:<br />
q = int(fin.readline())<br />
pairs = [tuple(map(int, line.split())) for line in fin]<br />
<br />
with open("output.out", "w") as fout:<br />
for pair in pairs:<br />
x, y = pair<br />
if x == y:<br />
fout.write("0\n")<br />
elif max_prime_factor(x) == max_prime_factor(y):<br />
fout.write("1\n")<br />
else:<br />
fout.write("2\n")<br />
<br />
</syntaxhighlight></div>RebecaBud