Omówienie zadania Liczby względnie pierwsze (II etap XXIX OI)

Dana jest lista wszystkich liczb względnie pierwszych z liczbą \(n\). Mamy wypisać jej fragment długości \(c\) zaczynający się na pozycji \(k\).

Podzadanie 1

Skonstruujemy początek listy wprost z definicji, sprawdzając dla każdej kolejnej liczby naturalnej \(x\), jaki jest największy wspólny dzielnik \(x\) oraz \(n\). Jeżeli przez \(M\) oznaczymy największą liczbę, którą musimy wypisać w odpowiedzi, to będziemy musieli przeanalizować \(M\) liczb i dla każdej z nich obliczyć największy wspólny dzielnik z liczbą \(n\), co możemy zrobić algorytmem Euklidesa w czasie \(O(\log n)\).

Wobec tego całe rozwiązanie będzie działać w czasie \(O(M \log n)\).

Podzadanie 2

Zauważmy, że jeżeli liczba \(x\) nie jest względnie pierwsza z \(n\), to mają one jakiś wspólny dzielnik pierwszy \(p\). Jeżeli znajdziemy rozkład liczby \(n\) na czynniki pierwsze \(n=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_s^{\alpha_s}\), co możemy zrobić w czasie \(O(\sqrt{n})\), to będziemy musieli wykreślić wszystkie wielokrotności czynników pierwszych \(p_i\).

Jeżeli przez \(s\) oznaczymy sobie liczbę różnych czynników pierwszych liczby \(n\), to ta część algorytmu zajmie nam czas \(O(s \cdot n)\). Liczba \(s\) jest dość mała, można ją sobie szacować przez \(O(\log \log n)\) lub sprawdzić, czy dla ograniczenia na \(n\) występującego w zadaniu jest nie większe niż \(13\) (dlatego że iloczyn \(14\) najmniejszych liczb pierwszych jest już większy niż \(10^{14}\)).

Zauważmy, że złożoność tego algorytmu będzie można z grubsza szacować przez \(O(\sqrt{n})\) plus liczbę wyrzucanych liczb, to znaczy tych, które nie są względnie pierwsze z \(n\). A w drugim podzadaniu mamy właśnie ograniczenie na liczbę tych liczb.

Jeśli zatem stworzymy sobie zbiór wyrzucanych liczb, a następnie go posortujemy, to całkiem łatwo nam będzie znaleźć \(k\)-tą liczbę nie należącą do tego zbioru. Wystarczy bowiem iterować się po elementach zbioru w kolejności rosnącej i zliczać sobie liczby, które występują pomiędzy kolejnymi wystąpieniami liczb ze zbioru.

Wyznaczanie liczby liczb względnie pierwszych z \(n\) na przedziale

Zanim pokażemy, jak szybko wyznaczyć \(k\)-tą liczbę względnie pierwszą z \(n\), zastanówmy się, czy bylibyśmy w stanie wyznaczyć liczbę liczb względnie pierwszych z \(n\) na jakimś początkowym przedziale liczb naturalnych.

Rozważmy przykład z \(n=10\) i liczbami z przedziału \([1, 15]\). Wszystkich liczb jest \(15\), od czego musimy odjąć \(7\) wielokrotności dwójek oraz \(3\) wielokrotności piątki. Przy czym liczba \(10\) jako zarówno wielokrotność dwójki, jak i piątki została odjęta dwa razy. Wobec tego musimy to poprawić, dodając 1.

Możemy uogólnić tę metodę i pokazać ogólny wzór na liczbę liczb z przedziału \([1,z]\) względnie pierwszych z \(n\). Na początek mamy wszystkie liczby od \(1\) do \(z\), z których musimy wykreślić wszystkie wielokrotności \(p_i\) nie większe od \(z\). Będzie ich oczywiście \(\lfloor \frac{z}{p_i} \rfloor\).

Ale każda liczba, która będzie wielokrotnością dwóch liczb \(p_i\) i \(p_j\), zostanie wykreślona dwa razy. Zatem dla każdej pary różnych czynników \(p_i\) i \(p_j\) musimy poprawić wynik przez dodanie wszystkich wielokrotności \(p_i\) i \(p_j\), czyli \(\lfloor \frac{z}{p_i p_j} \rfloor\). Zastanówmy się jednak, co będzie z liczbami, które są wielokrotnościami trzech czynników \(p_i\). Zostaną one odjęte trzy razy, raz dla \(p_i\), raz dla \(p_j\) i raz dla \(p_k\), a następnie dodane trzy razy, raz dla pary \(p_i\) i \(p_j\), raz dla pary \(p_j\) i \(p_k\) i raz dla pary \(p_i\) i \(p_k\). Trzy minusy i trzy plusy się zniosą, wobec tego musimy jeszcze raz poprawić nasz wynik, tym razem odejmując wszystkie wielokrotności dla iloczynów trzech czynników, co da \(\lfloor \frac{z}{p_i p_j p_k} \rfloor\):

\[z - \sum_i \Big\lfloor \frac{z}{p_i} \Big\rfloor + \sum_{i\neq j} \Big\lfloor \frac{z}{p_i p_j} \Big\rfloor - \sum_{i\neq j\neq k\neq i} \Big\lfloor \frac{z}{p_i p_j p_k} \Big\rfloor + \ldots\]

Nie będzie zaskoczeniem, że ten wzór trzeba będzie jeszcze poprawić, rozważając iloczyny większej liczby czynników \(p_i\). I dla iloczynów parzystej liczby czynników będziemy dodawali odpowiednie liczby wielokrotności, a dla iloczynów nieparzystych liczby czynników będziemy je odejmowali. Technika zliczania, którą tutaj zastosowaliśmy, nosi nazwę metody włączeń i wyłączeń. Powyższy wzór możemy zapisać jako sumę po wszystkich podzbiorach \(J\) czynników z rozkładu liczby \(n\), liczby \(z\) podzielonej przez iloczyn czynników z tego zbioru i zaokrąglonej w dół, pomnożonej przez \(1\) lub \(-1\), co jest zależne od parzystości liczności tego zbioru: \[\sum_J (-1)^{|J|} \Big\lfloor \frac{z}{\prod_{i\in J} p_i} \Big\rfloor.\]

Ponieważ liczba wszystkich zbiorów to będzie \(2^s\) i dla każdego z nich będziemy musieli obliczyć iloczyn co najwyżej \(s\) czynników, więc złożoność obliczania tego wzoru to będzie \(O(2^s \cdot s)\).

Podzadanie 3

Powyższy wzór bardzo nam się przyda w rozwiązaniu naszego zadania, bo pozwoli nam przy szukaniu \(k\)-tej liczby względnie pierwszej z \(n\) zastosować metodę wyszukiwania binarnego po wyniku. Zaczynamy od przedziału \([1,W]\) dla jakiegoś dużego \(W\), a następnie pytamy się, ile jest liczb względnie pierwszych z \(n\) nie większych niż \(\frac{W}{2}\), czyli połowa tego przedziału.

Jeśli jest ich co najmniej \(k\), to wtedy wiemy, że nasza liczba, której szukamy, będzie znajdować się w przedziale \([1,\frac{W}{2}]\). W przeciwnym wypadku wiemy, że będzie znajdować się w pozostałej części przedziału \([\frac{W}{2}+1,W]\). Za każdym razem będziemy zmniejszać długość przedziału, w którym znajduje się nasza odpowiedź, przez \(2\). Wobec tego po logarytmicznie wielu zapytaniach dostaniemy przedział jednoelementowy, który będzie właśnie zawierał szukaną \(k\)-tą liczbę względnie pierwszą z \(n\). Złożoność czasowa będzie zatem równa \(O(2^s \cdot s \cdot \log W)\).

Pytanie, jak duże ograniczenie na \(W\) potrzebujemy wziąć? Okazuje się, że musi to być niezbyt duża wielokrotność liczby \(n\), a wynika to z tego, że liczby względnie pierwsze z \(n\) są dosyć gęsto rozłożone. Aby to pokazać, użyjmy tutaj wzoru na \(\varphi(n)\), to znaczy liczbę liczb względnie pierwszych z \(n\) nie większych niż \(n\). Wzór ten wygląda następująco: \[\varphi(n) = n (1-\tfrac{1}{p_1})(1-\tfrac{1}{p_2})\cdots(1-\tfrac{1}{p_s}).\] Poprawność tego wzoru również można udowodnić, korzystając z metody włączeń i wyłączeń.

Teraz interesuje nas, jaka część liczb mniejszych równych od \(n\) jest względnie pierwsza z \(n\), to znaczy, jaki jest iloraz \(\frac{\varphi(n)}{n}\). Ze wzoru wynika, że aby ten iloraz był jak najmniejszy, liczby \(p_i\) muszą być jak najmniejsze. I znowu, jeżeli skorzystamy z ograniczenia, że \(n \leq 10^{14}\), to najmniejszy iloraz uzyskamy dla \(n\) będącego iloczynem \(13\) najmniejszych liczb pierwszych. I nawet dla takiego najgorszego przypadku okaże się, że liczb względnie pierwszych z \(n\) jest co najmniej \(14\%\). Tak więc w praktyce możemy przyjąć \(W = 8n\).

Ta złożoność czasowa jest to złożoność znalezienia \(k\)-tej liczby względnie pierwszej z \(n\). Wobec tego, jeżeli każdą z \(c\) szukanych liczb będziemy znajdować niezależnie, to tą złożoność musimy jeszcze pomnożyć przez \(c\).

Pełne rozwiązanie

Pełne rozwiązanie jest sprytnym połączeniem algorytmu szybkiego z brutalnym. Najlepiej jest bowiem znaleźć \(k\)-tą liczbę względnie pierwszą z \(n\) za pomocą szybkiego algorytmu (oznaczmy tę liczbę przez \(x\)), a następnie, iterując się kolejno liczbami \(x + 1, x + 2,\ldots\), dla każdej z nich sprawdzać, czy są względnie pierwsze z \(n\), korzystając z algorytmu Euklidesa.

Argument, dlaczego to rozwiązanie zadziała szybko, już przedstawiliśmy i jest związany on z tym, że liczby względnie pierwsze są ułożone dość gęsto i przy ograniczeniach z treści zadania już po przeanalizowaniu \(8c\) liczb, znajdziemy \(c\) liczb względnie pierwszych z \(n\).