Przeskocz do treści

Delta mi!

Informatyczny kącik olimpijski

Kwadraty liczb naturalnych

Bartosz Łukasiewicz

o artykule ...

  • Publikacja w Delcie: sierpień 2019
  • Publikacja elektroniczna: 1 sierpnia 2019
  • Wersja do druku [application/pdf]: (297 KB)

W tym odcinku omówimy rozwiązanie zadania "Kwadraty liczb naturalnych", które pojawiło się na finale Zawodów Indywidualnych XIII Młodzieżowej Olimpiady Informatycznej.

Zadanie (Kwadraty liczb naturalnych). Piotr jest zafascynowany kwadratami liczb naturalnych, czyli liczbami: 1,4,9,16,25,... Chłopiec ma przed sobą ciąg n liczb naturalnych a = (a1,a2,...,an). Ile jest takich par liczb naturalnych w ciągu |a, że ich iloczyn jest kwadratem liczby naturalnej?

Niech m oznacza wartość największej liczby w ciągu a, | zaś M niech oznacza największy iloczyn pary liczb w ciągu a.

Rozwiązanie |O
Zacznijmy od rozwiązania, w którym obliczamy iloczyn każdej z |n n−1- 2 par elementów ciągu a. Następnie zliczamy te iloczyny, które są kwadratami liczb naturalnych. Załóżmy, że chcemy sprawdzić, czy x jest kwadratem. W tym celu przeglądamy kwadraty kolejnych liczb naturalnych: 22,33,42,... Jeśli trafimy na x, to odpowiedź jest pozytywna. Jeśli trafimy na liczbę większą niż x, wtedy przerywamy działanie i odpowiedź jest negatywna. Tym sposobem rozważymy O kwadratów. Zatem rozwiązanie działa w czasie O

Rozwiązanie |O
Przyspieszmy sprawdzanie, czy x jest kwadratem. Zaaplikujmy algorytm wyszukiwania binarnego na ciągu kwadratów:  2 2 2 1 ,2,...,x . Algorytmy wykona |O(log(x)) operacji. Całe rozwiązanie działa w czasie O(n2 |

Szkic rozwiązania optymalnego
Zauważmy, że w rozkładzie na czynniki pierwsze kwadratu liczby naturalnej każdy czynnik pierwszy występuje parzyście wiele razy. Zatem iloczyn dwóch liczb jest kwadratem, jeśli zbiory czynników pierwszych występujących nieparzyście wiele razy w rozkładzie obu liczb są takie same. Niech więc b = (b1,b2,...,bn), gdzie |bi oznacza iloczyn czynników pierwszych, które występują nieparzyście wiele razy w rozkładzie a . i Innymi słowy, b i to a i podzielone przez swój największy dzielnik będący kwadratem. Wówczas ai⋅a j jest kwadratem, jeśli |bi = b j. Zatem wynikiem jest liczba par takich samych elementów w ciągu |b.

Zliczanie par
Załóżmy przez chwilę, że znamy ciąg b i chcemy policzyć liczbę par elementów o takich samych wartościach. W tym celu wystarczy posortować ciąg niemalejąco. Wówczas elementy o tych samych wartościach znajdą się obok siebie (będą tworzyły bloki). Następnie przeglądamy kolejne bloki elementów i zliczamy pary. W |k-elementowym bloku można wybrać |k -k− 1- 2 par. Sortowanie realizujemy w czasie |O(n podział na bloki odbywa się w czasie |O(n). Zatem zliczanie par tych samych elementów w ciągu |b odbywa się w czasie O(n

Wyznaczenie ciągu |b w O
Wartość bi dla każdego i od 1 do n liczymy niezależnie. Początkowo niech |bi = ai dla każdego |i. Następnie przeglądamy kolejne kwadraty |(22,32,...,(⌊√ a-⌋)2) i jako kandydatów na dzielniki |ai. Jeśli rozpatrywany kwadrat jest dzielnikiem bi, to dzielimy |bi przez ten kwadrat. W ten sposób z rozkładu na czynniki pierwsze usuniemy kwadraty.

Wyznaczenie ciągu |b w O
Zauważmy, że nie ma potrzeby przeglądania wszystkich kwadratów. Wystarczy rozważać kwadraty liczb pierwszych | 2 2 2 (2 ,3 ,5 ,...). Pamiętajmy o tym, że kwadrat może wielokrotnie występować w rozkładzie na czynniki pierwsze. Wtedy musimy usunąć wszystkie jego wystąpienia. Przykładowo: liczbę 48 = 2⋅2 ⋅2⋅2 ⋅3 musimy dwukrotnie podzielić przez |22. Każda liczba zostanie podzielona co najwyżej | O(log(m)) razy. Liczbę liczb pierwszych w przedziale  √ --- |[1;⌊ m]⌋ szacujemy jako  m- |lg -m. Stąd całkowita złożoność wynosi O

Wyznaczenie ciągu |b w O
Na początku zliczmy wystąpienia liczb w ciągu a. Niech Zw= {i ai = w} (zbiór indeksów elementów ciągu a o wartości w ). Następnie przeglądamy kwadraty liczb pierwszych z przedziału [1;m] jako potencjalne dzielniki. Załóżmy, że rozpatrujemy kwadrat p2. Wiemy, że jest on dzielnikiem:  2 2 2 m- 2 1 ⋅p ,2⋅p ,3 ⋅p ,...,⌊ p2⌋⋅p . Dla każdej z tych wartości, korzystając z tablicy zliczającej |Z, odwołujemy się bezpośrednio do elementów, które są podzielne przez p2, i te elementy dzielimy przez |p2. Po zakończeniu otrzymane wartości tworzą ciąg b. Do każdego elementu ciągu odwołamy się co najwyżej |O(log(m)) razy. Liczba rozpatrywanych wielokrotności wynosi:  m m m |22-+ 32-+ 52-+..., co w sumie wynosi |O(m). Zatem otrzymaliśmy rozwiązanie działające w czasie |O(n

Wyznaczenie ciągu |b w O
Połączmy dwa poprzednie rozwiązania | (∗ ) i | (∗∗). Najpierw, podobnie jak w (∗), dla każdego elementu ciągu a rozważmy jego potencjalne dzielniki (kwadraty liczb pierwszych), nie większe niż  √ --- | m. Takich dzielników jest O( Następnie zaaplikujmy rozwiązanie |(∗∗) z drobną zmianą. Rozpatrujmy tylko wielokrotności kwadratów liczb pierwszych większych od √ --- | m. Niestety, tak opisane rozwiązanie nadal wymaga utworzenia tablicy zliczającej rozmiaru |O(n Do implementacji tablicy zliczającej wystarczy użyć tablicy mieszającej (tablicy z haszowaniem) i problem zostaje rozwiązany. Otrzymujemy algorytm, który działa w czasie |O(n . Dowód tego oszacowania pozostawiam Czytelnikowi. Jednocześnie zachęcam do pomyślenia nad lepszym oszacowaniem.