Omówienie zadania Liczby kompletne (III etap XXV OI)

Na potrzeby tego zadania liczbę nazwiemy kompletną, jeżeli liczba jej cyfr w zapisie dziesiętnym jest równa liczbie jej dzielników. Na przykład kompletną jest liczba \(13\), ponieważ jest dwucyfrowa oraz jako liczba pierwsza ma dokładnie \(2\) dzielniki. W zadaniu będziemy musieli zliczać, ile jest liczb kompletnych na danych przedziałach. Przedziałów tych może być do \(1000\) i mogą zawierać liczby do \(10^9\).

Uwagi wstępne

W przypadku tego rodzaju zadań, w których dostajemy zapytania, ile jest liczb znajdujących się w przedziale \([a,b]\), które spełniają jakieś własności, możemy się ograniczyć do odpowiadania na zapytania, w których lewy koniec przedziału jest ustalony (na przykład równy 0). Wtedy liczbę szukanych liczb na przedziale \([a,b]\) możemy obliczyć, wyznaczając liczbę tych liczb na przedziale \([0,b]\) i odejmując od tego liczbę liczb na przedziale \([0,a - 1]\).

Z kolei, gdy takich zapytań mamy dużo, warto rozważyć wykonanie pewnych obliczeń wstępnych, czyli tak zwanego preprocessingu, który ułatwi nam potem szybkie odpowiadanie na poszczególne zapytania.

W przypadku gdy prawe końce przedziałów są ograniczone na tyle, że możemy sobie pozwolić na trzymanie tablicy o takiej długości w pamięci, czyli na przykład, jeżeli \(b \leq 10^7\), to możemy rozważyć preprocessing, w którym dla każdej liczby do \(10^7\) obliczamy, czy liczba ta jest kompletna, czy nie, a następnie wyniki umieszczamy w tablicy. Czyli napiszemy, że \(kom[i] = 1\), jeśli \(i\) jest liczbą kompletną. Mając taką tablicę, liczymy na niej w czasie \(O(b)\) sumy prefiksowe i dzięki nim będziemy mogli odpowiadać na zapytanie o przedział w czasie stałym.

Podzadanie 1

Pytanie, w jakim czasie jesteśmy w stanie wyznaczyć tablicę \(kom\). Dla pierwszego podzadania, w którym \(b \leq 1000\), jest to bardzo proste. Możemy sprawdzić kompletność każdej liczby zupełnie niezależnie. Liczbę cyfr danej liczby możemy wyznaczyć w czasie \(O(\log b)\), po prostu zliczając, ile razy musimy ją podzielić przez \(10\) bez reszty, aż do uzyskania zera. Natomiast liczbę dzielników możemy wyznaczyć w czasie \(O(b)\), po prostu sprawdzając dla każdego kandydata od \(1\) do \(b\), czy dzieli on naszą liczbę bez reszty, lub w czasie \(O(\sqrt{b})\), zauważając, że jeżeli jakaś liczba \(d\) jest dzielnikiem liczby \(i\), to również liczba \(\frac{i}{d}\) jest dzielnikiem, więc wystarczy iterować się jedynie do liczby \(\sqrt i\) i dla każdego znalezionego dzielnika zwiększać liczbę dzielników o \(2\). (Musimy jedynie uważać na przypadek szczególny, kiedy liczba \(i\) jest kwadratem.)

Podsumowując, takie rozwiązanie będzie działało w czasie \(O(b^2)\), albo w czasie \(O(b \sqrt{b})\), ponieważ musimy wykonać to obliczenie dla każdej liczby nie większej niż \(b\).

Podzadanie 2

Takie rozwiązanie będzie oczywiście zbyt wolne w przypadku drugiego podzadania, gdy \(b \leq 10^6\). Tutaj przyda nam się wyznaczenie dla każdej liczby jakiegoś jej dzielnika pierwszego. Użyjemy do tego sita Eratostenesa.

Ten algorytm zwykle jest wykorzystywany do tego, żeby wyznaczyć listę początkowych liczb pierwszych. Działa on w ten sposób, że dla każdej znalezionej liczby pierwszej wykreślamy wszystkie jej wielokrotności, a następnie mówimy, że najmniejsza niewykreślona liczba jest kolejną liczbą pierwszą.

Zmodyfikujemy teraz ten algorytm, żeby w przypadku wykreślania wielokrotności jakiejś liczby pierwszej \(p\) dla każdej z tych wielokrotności zapisywać w tablicy, że liczba \(p\) jest jej dzielnikiem. Czyli jako najmniejszą liczbę pierwszą zaznaczamy \(2\), a następnie wykreślamy jej wielokrotności i przy każdej wielokrotności zapisujemy, że \(2\) jest jej dzielnikiem. Dalej najmniejszą niewykreśloną liczbą jest \(3\), wobec tego zaznaczamy, że to jest kolejna liczba pierwsza i dla każdej jej wielokrotności (nawet kiedy już była wcześniej wykreślona) zaznaczamy, że \(3\) jest jej dzielnikiem. I dalej postępujemy tak samo. W ten sposób powstała nam tabelka, w której dla każdej liczby zapamiętaliśmy sobie jej największy dzielnik pierwszy. (Analogicznie moglibyśmy zapisywać sobie najmniejsze dzielniki pierwsze, gdybyśmy nie nadpisywali już raz zapisanych liczb.)

Całość operacji wykonujemy w takim samym czasie, jak czas działania sita Eratostenesa, czyli \(O(b \log \log b)\). Dzięki tabelce z dzielnikami pierwszymi jesteśmy teraz w stanie dość szybko dla każdej liczby wyznaczyć jej rozkład na dzielniki pierwsze. Przykładowo, jeżeli chcemy wykonać ten rozkład dla liczby \(i\), to patrzymy sobie do tabelki, jaki ona ma dzielnik pierwszy \(p\) i zapisujemy, że jest to jeden z jej dzielników w rozkładzie, a następnie rekurencyjnie znajdujemy rozkład liczby \(i/p\).

Zauważmy, że w każdym kroku tego algorytmu dzieliliśmy naszą wyjściową liczbę co najmniej przez \(2\). Wobec tego widać, że do jedynki dojdziemy po co najwyżej \(\log b\) krokach. I taka też będzie złożoność czasowa znalezienia rozkładu liczby nie większej niż \(b\).

A mając rozkład liczby na czynniki pierwsze, możemy już łatwo wyznaczyć liczbę jej dzielników. Jeżeli znamy rozkład liczby \(i\) na czynniki: \[i = p_1 ^ {\alpha_1} \cdot p_2 ^ {\alpha_2} \cdots p_k ^ {\alpha_k},\] to liczba dzielników \(i\) wynosi \[d(i) = (\alpha_1 + 1) \cdot (\alpha_2 + 1) \cdots (\alpha_k + 1).\] Skorzystanie z tego wzoru pozwoli nam wyznaczyć liczbę dzielników w czasie logarytmicznym. Wobec tego drugie podzadanie będziemy mogli rozwiązać w czasie \(O(b \log b)\).

Pełne rozwiązanie

Przejdźmy teraz do rozwiązania ostatniego podzadania, w którym \(b \leq 10^9\). Tutaj nie będziemy mogli pozwolić sobie na wypisanie tablicy wszystkich liczb, wobec tego będziemy potrzebowali jakiegoś innego pomysłu. Istotna obserwacja jest taka, że skoro liczby są ograniczone do miliarda, to mają one co najwyżej \(10\) cyfr, więc liczby kompletne z tego przedziału mają co najwyżej 10 dzielników.

Co więcej, miliard jest jedyną liczbą \(10\)-cyfrową, a z jego rozkładu na czynniki pierwsze \(10^9 = 2^9 \cdot 5^9\) wynika, że ma \(d(10^9) = (9+1)(9+1) = 100\) dzielników, zatem nie jest liczbą kompletną. Ponadto liczba 1 jest jedyną liczbą, która ma jeden dzielnik (i jest ona kompletna).

Pozostałych liczb kompletnych będziemy poszukiwali wśród liczb, które mają od \(2\) do \(9\) dzielników. Wypiszmy sobie wszystkie możliwości uzyskania liczb od \(2\) do \(9\) jako iloczyny pewnych krotności zwiększonych o \(1\):

Z tej listy wynika, że jeżeli \(n\) ma co najwyżej \(9\) dzielników, to ma albo \(1\), \(2\), albo \(3\) liczby pierwsze w rozkładzie na czynniki pierwsze. Możemy zatem nasze zadanie rozbić na trzy podzadania i niezależnie szukać liczb kompletnych, które mają \(1\) czynnik pierwszy, \(2\) czynniki pierwsze i \(3\) czynniki pierwsze. Przy czym nasze rozwiązanie będzie nieco inżynierskie i będziemy starali się wykonać tylko tyle obliczeń, ile nam jest potrzebne do wyznaczenia rozkładów z tabelki. Możemy również skupić się na rozkładach dla \(7\), \(8\) i \(9\) dzielników, ponieważ dla mniejszej liczby dzielników działa nasze rozwiązanie z podzadania 2.

Na początek przeanalizujmy liczby, które mają jeden czynnik w rozkładzie, czyli liczby postaci \(p^\alpha\). Zauważmy, że ze wzrostem \(\alpha\) liczba \(p^\alpha\) rośnie bardzo szybko, więc o ile dla \(\alpha = 1\) liczb pierwszych do \(10^9\) będziemy mieli kilkadziesiąt milionów, to już dla \(\alpha = 2\) wystarczy nam rozpatrywać przedział do \(\sqrt{10^9}\). A i tak w przypadku \(\alpha \leq 2\) takie duże przedziały nie są potrzebne, ponieważ interesują nas tu tylko liczby dwu- i trzycyfrowe. W przypadku liczb więcej-cyfrowych pula kandydatów szybko się kończy i generalnie liczb kompletnych w postaci \(p^\alpha\) mamy jedynie kilkadziesiąt.

Przypadek dla dwóch liczb pierwszych również nie jest bardzo trudny. Ponieważ kwadratów liczb pierwszych będziemy mieli jedynie kilka tysięcy, a sześcianów kilkaset, więc możemy sobie pozwolić na zrobienie podwójnej pętli, która będzie przeglądać wszystkie iloczyny. Warto w wewnętrznej pętli przeglądać liczby rosnąco i ilekroć iloczyn przekroczy \(10^9\), możemy przerwać wewnętrzną pętlę. Ogólnie liczb kompletnych tego rodzaju będzie nieco ponad milion.

Pozostał do rozważenia ostatni przypadek, w którym mamy iloczyn trzech liczb pierwszych, wszystkie z wykładnikiem \(1\). Okazuje się, że dobrze zoptymalizowana potrójna pętla poradzi sobie również w tym przypadku. Ponieważ ten przypadek dotyczy tylko liczb ośmiocyfrowych, więc możemy odcinać przeszukiwanie, gdy iloczyn przekroczy \(10^8\). Liczb kompletnych tego rodzaju jest najwięcej, bo powyżej \(18\) milionów.

W sumie wszystkich liczb kompletnych do miliarda jest nieco poniżej \(20\) milionów i możemy pozwolić sobie, że po ich wygenerowaniu będziemy je trzymać w posortowanej tablicy. Dzięki temu każde zapytanie zrealizujemy prostym wyszukiwaniem binarnym.

Złożoność czasowa

Ostatecznie do złożoności czasowej naszego rozwiązania znaczący wkład będzie miało uruchomienie sita Eratostenesa, którym wyznaczymy potrzebne nam liczby pierwsze. Najwięcej liczb pierwszych będziemy potrzebowali w ostatnim przypadku. Tutaj iloczyn jest ograniczony przez \(10^8\), ale ponieważ musimy wziąć trzy liczby pierwsze, więc jedna z nich musi być co najmniej równa \(2\), a druga co najmniej równa \(3\), więc największa liczba pierwsza, której będziemy potrzebować, to jest \(\frac{10^8}{6}\). I na tablicy takiej długości będziemy uruchamiać sito.

Okazuje się jednak, że najwięcej czasu w naszym rozwiązaniu zajmie nam ostateczne posortowanie \(20\) milionów liczb kompletnych. Zauważmy jednak, że możemy uniknąć sortowania tak dużej ilości liczb, ponieważ sortowanie będzie nam jedynie potrzebne dla liczb dziewięciocyfrowych. Pozostałe liczby mające do \(8\) cyfr możemy po prostu zaznaczać w tablicy o wielkości \(10^8\), a po ich wyznaczeniu przeglądamy tę tablicę i wypisujemy liczby kompletne już posortowane.