Omówienie zadania Najmniejsza wspólna wielokrotność (I etap XXVII OI)

W zadaniu chcemy dla wielu zapytań \(m_i\) znajdować przedział \([a, b]\) (co najmniej dwuelementowy) taki, że:

\[\text{NWW}[a, b] = \text{NWW}(a, a + 1, \dots, b + 1) = m_i.\]

Jeśli istnieje wiele rozwiązań, wybieramy to, w którym \(a\) jest najmniejsze, a jeśli nadal jest ich wiele, to wybieramy to, w którym \(b\) jest najmniejsze.

Podzadanie \(z \leq 10, m_i \leq 1000\)

Dla tego podzadania możemy zastosować pełny przegląd. W każdym zapytaniu rozważymy kolejno liczby \(j\) od 1 do \(m_i\) jako początki przedziału. Dla każdego takiego \(j\) przejdziemy po liczbach \(j, j+1, j+2, \dots, k\) licząc na bieżąco ich \(\text{NWW}\), więc rozważymy wszystkie przedziały \([j, k]\), takie że \(1 \leq j < k \leq m_i\).

Aby szybko liczyć \(\text{NWW}\) korzystamy ze wzoru:

\[\text{NWW}(x, y) = \frac{x \cdot y}{\text{NWD}(x, y)}\]

gdzie \(\text{NWD}\) to największy wspólny dzielnik. Możemy go policzyć algorytmem Euklidesa w czasie \(O(\log m)\). W naszym przypadku ten wzór rozwija się do następującej postaci:

\[ \text{NWW}[j, k] = \frac{\text{NWW}[j, k-1] \cdot k}{\text{NWD}(\text{NWW}[j, k-1], k)}\]

Licząc \(\text{NWW}\) musimy tylko uważać, aby nie wyjść poza zakres zmiennej 64-bitowej. W takim przypadku rozpoczynamy rozważanie nowego początku przedziału.

Podsumowując, dla każdego z \(z\) zapytań przejdziemy po maksymalnie \(m^2\) przedziałach i dla każdego policzymy \(\text{NWW}\) w złożoności \(O(\log m)\), wykorzystując wynik z policzonego chwilę wczesniej krótszego przedziału. To znaczy, że złożoność czasowa rozwiązania to \(O(z \cdot m^2 \cdot \log m)\), a pamięciowa to jedynie \(O(1)\).

Podzadanie \(z \leq 100, m_i \leq 10^9\)

W tym podzadaniu postaramy się lepiej ograniczyć liczbę rozważanych przedziałów.

Na początek zauważmy, że \(j\), które chcemy rozważać jako początki przedziałów, są stosunkowo małe. Z następującej obserwacji:

\[\text{NWW}[j, k] \geq \text{NWW}(j, j+1) = j \cdot (j + 1)\]

wynika, że wystarczy sprawdzić \(j\), które są nie większe niż \(\sqrt{m_i}\). Dla większych \(j\) już przedział dwuelementowy będzie miał zbyt duże NWW, a wydłużając przedział możemy je tylko zwiększyć.

Zauważmy ponadto, że przedziały, które będziemy rozważać, są dość krótkie. Oznaczmy przez \(K\) maksymalną długość przedziału liczb naturalnych, którego \(NWW\) nie przekracza \(10^{18}\). Łatwo wyznaczyć dobre odgórne oszacowanie na \(K\): w przedziale o długości \(l\) dla każdej liczby pierwszej mniejszej niż \(l\) musi występować liczba przez nią podzielna, więc \(NWW[j, j + l - 1] \geq 2 \cdot 3 \cdot ... \cdot p_l\), gdzie \(p_l\) to największa liczba pierwsza mniejsza od \(l\). Dla \(l = 54\) dostajemy nierówność \(NWW[j, j + 53] \geq 2 \cdot 3 \cdot 5 \cdot ... \cdot 53 > 10^{18}\), więc możemy rozważać tylko przedziały nie dłuższe niż 53. Dokładną wielkość \(K\) możemy wyznaczyć prostym programem, a będzie to \(42\) (oczywiście w tym podzadaniu \(K\) może być mniejsze, bo \(m_i \leq 10^9\)).

W takim razie wystarczy, że sprawdzimy tylko przedziały nie dłuższe niż \(K\) zaczynające się nie później niż w \(\sqrt{m_i}\). Ponieważ dla \(z\) zapytań przejdziemy po \(\sqrt{m_i} \cdot K\) przedziałach licząc \(NWW\), otrzymamy złożoność czasową \(O(z \cdot \sqrt{m} \cdot K \cdot \log m)\). Pamięci, której potrzebujemy, jest wciąż \(O(1)\).

Podzadanie \(z \leq 100, m_i \leq 10^{18}\)

Tutaj nie możemy już sprawdzać wszystkich liczb do \(\sqrt{m_i}\). Okazuje się jednak, że poprzednie rozwiązanie jest wciąż podatne na usprawnienia.

Tym razem osobno sprawdzimy przedziały dwuelementowe i te, które mają co najmniej trzy elementy. Zauważmy, że ponieważ dwie kolejne liczby naturalne są względnie pierwsze, zawsze możemy łatwo wyznaczyć jedynego kandydata na początek przedziału dwuelementowego, którego \(\text{NWW}\) jest równe \(m_i\). Można go wyszukać binarnie \(\log m_i\) razy sprawdzając warunek \(j \cdot (j + 1) > m_i\).

Dla dłuższych przedziałów znowu będziemy rozważać tylko te, dla których \(j\) jest względnie niewielkie. Ponieważ:

\[\text{NWW}[j, k] \geq \text{NWW}(j, j+1, j+2) \geq \frac{j \cdot (j+1) \cdot (j+2)}{2}\]

możemy rozpatrywać tylko \(j\), które są nie większe niż około \(2 \cdot \sqrt[3]{m_i}\). Rozumowanie jest tutaj identyczne jak w szacowaniu z poprzedniego podzadania. Druga nierówność wynika z faktu \(\text{NWD}(j, j + 1, j + 2) \leq 2\).

Policzenie odpowiedzi na wszystkie zapytania zajmuje \(O(z \cdot \sqrt[3]{m} \cdot K \cdot \log m)\). Wciąż potrzebujemy tylko \(O(1)\) pamięci.

Pełne rozwiązanie \(z \leq 10,000, m_i \leq 10^{18}\)

Jeśli dobrze zastanowimy się nad tym, co robiliśmy w poprzednich podzadaniach, to okaże się, że \(z\) razy wykonywaliśmy dokładnie te same obliczenia. Aby usprawnić ostatni algorytm, zastosujemy rozwiązanie offline - na początku wczytamy wszystkie zapytania, następnie policzymy odpowiedzi, a na koniec wypiszemy je w dobrej kolejności.

Nasze zapytania możemy po wczytaniu zapisać w pewnej strukturze danych. Następnie jeden raz uruchomimy procedurę wyliczania \(\text{NWW}\) dla przedziałów o długości co najmniej trzy opisanej powyżej. Kiedy obliczymy jakieś \(\text{NWW}\), sprawdzimy w naszej strukturze, czy odpowiada ono jakiemuś zapytaniu. Jeśli tak, to zapiszemy odpowiedź i usuniemy zapytanie ze struktury. Na koniec dla każdego zapytania sprawdzimy, czy nie dostaniemy lepszej odpowiedzi dla przedziału dwuelementowego. Jeśli tak, zaktualizujemy odpowiedź.

Strukturą danych, której możemy użyć, jest hashmapa (w C++ znana jako unordered_map). Dorzucenie do niej elementu oraz odczytanie wartości dla klucza (sprawdzenie, czy było pytanie o \(\text{NWW}\)) zajmuje średnio czas stały. A więc nasze rozwiązanie zajmie łącznie \(O(z \cdot \log m + \sqrt[3]{m} \cdot K \cdot \log m)\) czasu oraz \(O(z)\) pamięci.