Omówienie zadania Trudny dylemat przedszkolanina (II etap XXVII OI)

Wstęp

W zadaniu mamy daną liczbę \( m \), i naszym zadaniem jest podać 2 takie liczby naturalne \( x \) oraz \( y \) (\( x, y \in \mathbb{N} \)), że zbiór składający się z dzielników liczb \( x \) i \( y \) jest możliwie najmniejszy.

Najprostsze podejście

Pierwszym rozwiązaniem, które przychodzi nam do głowy, jest sprawdzenie każdej pary liczb, co wystarczy, by zaliczyć pierwsze podejście.

Które liczby opłaca nam się sprawdzać?

Zauważmy, że liczby takie jak liczby pierwsze są bardzo słabymi kandydatami na wynik. Mają bowiem jedynie 2 dzielniki...

Poza liczbami pierwszymi jest wiele takich wartości \( x, y \), które nigdy nie nadawałyby się na wynik. Intuicyjnie chcemy więc zredukować liczbę kandydatów na \( x, y \) i sprawdzić, czy poprawia nam to złożoność.

Dobrze, w takim razie, jakie ograniczenie na ilość dzielników będzie optymalne?

Liczby antypierwsze

Bardziej doświadczeni spośród czytelników mogą pamiętać zadanie Liczby antypierwsze, które niegdyś pojawiło się na Olimpiadzie Informatycznej. Zrozumienie rozwiązania do tamtego zadania jest właściwie niezbędne do rozwiązania tego zadania, toteż odsyłamy czytelników do zapoznania się z jego omówieniem; jest niedługie, lecz bardzo pouczające.

Liczby antypierwsze to takie liczby naturalne, które mają więcej dzielników niż którakolwiek liczba mniejsza od nich. Użyjemy największej liczby antypierwszej mniejszą niż \( n \) do znalezienia ograniczenia dolnego na wynik. Oznaczmy naszą liczbę antypierwszą przez \( \alpha \) i niech \( d(x) \) oznacza liczbę dzielników liczby \( x \).

\[ \alpha = 2^{x_2} \cdot 3^{x_3} \cdot 5^{x_5} \cdot \ldots \cdot p_k^{1} \]

Pomijając poprawki dla bardzo małych \( n \), można założyć, że największy dzielnik pierwszy \( \alpha \) występuje tylko raz w rozkładzie na czynniki pierwsze.

Niech

\[ \beta = \frac{\alpha}{p_k} \cdot p_{k+1}, \]

czyli

\[ \beta = 2^{x_2} \cdot 3^{x_3} \cdot 5^{x_5} \cdot \ldots \cdot p_{k-1}^{x_{k-1}} \cdot p_k^{0} \cdot p_{k+1}^1 \]

Zauważmy, że rozmiar zbioru wszystkich dzielników \( \alpha \) i \( \beta \) jest równy:

\[ d(\alpha) + d(\beta) - d(\text{NWD}(\alpha, \beta)) = 2d(\alpha) - d\left(\frac{\alpha}{p_k}\right) = 2d(\alpha) - \frac{1}{2} d(\alpha) = \frac{3}{2} d(\alpha) \]

Widzimy więc, że w ten prosty sposób znaleźliśmy ograniczenie dolne na nasz wynik. Jednak czy to jest na pewno ograniczenie dolne? W końcu \( \beta \) może być większe niż \(n\). Bardziej sceptyczni mogą mieć użyć ograniczenia \( 1.3 \cdot d(\alpha) \) czy \( 1.4 \cdot d(\alpha) \), lecz okazuje się, że \( 1.5 \cdot d(\alpha) \) jest wystarczająco dobre.

Wykorzystanie ograniczenia

Wróćmy do naszego pierwotnego celu, mianowicie, chcielibyśmy znaleźć takie kryterium, które pozwoli nam znacząco zredukować zbiór kandydatów. Wyznaczmy je na podstawie naszego ograniczenia dolnego na wynik.

Skoro w wyniku możemy uwzględnić \(\alpha \) jaką jedną z liczb, to druga liczba musi mieć co najmniej \( 1.5 \cdot d(\alpha) - d(\alpha) = 0.5 \cdot d(\alpha)\) dzielników. W takim razie przyjmijmy jako zbiór kandydatów liczby spełniające to właśnie kryterium!

Generowanie zbioru

Do wygenerowania zbioru kandydatów użyjemy funkcji rekurencyjnej. W funkcji tej będziemy trzymać liczbę \(x\) oraz ostatnio rozpatrywaną przez nas liczbę pierwszą \(p_k\). Dalsze przejścia rekurencyjne to:

• Domnożenie do \(x\) liczbę \(p_{k+1}\) pewną niezerową ilość razy),
• Niedomnażanie do \(x\) liczby \(p_{k+1}\) ani razu i przejście do rekurencji z liczbą \(x\) z ostatnio rozpatrywaną liczbą pierwszą równą \(p_{k+1}\).

Aby nasza funkcja działała w rozsądnym czasie, musimy znaleźć sposób na ucinanie gałęzi rekurencji zanim dojdziemy do niepotrzebnych liści (tj. w danym wywołaniu, być w stanie od razu stwierdzić, że nie uda nam się osiągnąć żadnej liczby spełniającej kryterium, poprzez kolejne wywołania rekurencyjne, czyli domnożenie pewnego zbioru liczb pierwszych do obecnie rozpatrywanej).

Możemy to zrobić sprawdzając dosłownie to, czy po domnożeniu najbardziej korzystnego zbioru liczb pierwszych, uzyskana liczba spełnia kryterium! Oszacujemy to dosyć luźno. Mianowicie, domnożymy do \(x\) największą liczbę \(p_{k+1}^l\), dla której \(x \cdot p_{k+1}^l \leq n\). Następnie sprawdzimy, czy \(1.5 \cdot d(\alpha) \leq d(x) \cdot 2^l\) i jeżeli tak, to stwierdzamy, że opłaca nam się podążać tą gałęzią rekurencji.

Zauważmy, że wynik \( d(x) \cdot 2^l\) uzyskalibyśmy, gdybyśmy domnożyli do \(x\) dokładnie \(l\) różnych liczb pierwszych. My jednak jedynie szacujemy, więc sprawdzamy ile około dzielników będzie miał najlepszy kandydat w tej gałęzi, potencjalnie nieco zawyżając jego wynik.

Wiemy w takim razie w jaki sposób wyznaczyć rozsądnie zbiór kandydatów. Pozostało jedynie sprawdzić każdą parę kandydatów i wyznaczyć najlepszy wynik. Za takie rozwiązanie otrzymujemy 70 punktów.

Ostatnia prosta

Aby zdobyć maksymalną liczbę punktów z tego zadania, znów posłużymy się intuicją z zadania Liczby Antypierwsze. Mianowicie, tak jak liczb antypierwszych jest bardzo mało w naszym zakresie, tak zbiór różnych wyników wypisywanych przez nasz program dla \(n\) z zakresu jest dość mały.

Możemy więc lokalnie na komputerze policzyć wynik dla największego \(n\) z zakresu, stablicować go, a następnie policzyć wynik dla \(n\) równego większej z wypisanych liczb, pomniejszonej o 1.