W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W tym zadaniu rozważamy odległość między dodatnimi liczbami całkowitymi, zdefiniowaną w następujący sposób. Przez pojedynczą operację rozumiemy pomnożenie danej liczby przez liczbę pierwszą1 lub podzielenie jej przez liczbę pierwszą (o ile dzieli się ona bez reszty). Odległość między liczbami i , oznaczana , to minimalna liczba operacji potrzebnych do przekształcenia liczby w liczbę . Na przykład, .
Zauważmy, że faktycznie funkcja ma cechy odległości - dla dowolnych dodatnich liczb całkowitych , i zachodzi:
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (). W kolejnych wierszach znajdują się liczby (), po jednej w wierszu.
W testach wartych łącznie 30% punktów zachodzi dodatkowy warunek .
Twój program powinien wypisać na standardowe wyjście dokładnie wierszy, a w każdym z nich po jednej liczbie całkowitej. W -tym wierszu należy wypisać najmniejsze takie , że: , oraz jest minimalne.
Dla danych wejściowych:
6 1 2 3 4 5 6
poprawną odpowiedzią jest:
2 1 1 2 1 2
Autor zadania: Wojciech Śmietanka.
1. Przypomnijmy, że liczba pierwsza to taka liczba całkowita dodatnia, która ma dokładnie dwa różne dzielniki: jedynkę i siebie samą.