Informatyczny kącik olimpijski

Liczby

W tym miesiącu omówimy zadanie Liczby, które pojawiło się podczas rundy 72. na portalu codeforces.com.

W zadaniu należy, mając dane liczby naturalne $9 a,b, k⩽ 2 ⋅10 ,$ wyznaczyć liczbę liczb naturalnych w przedziale $[a,b],$ których najmniejszym dzielnikiem, większym od $1,$ jest $k.$ Zauważmy najpierw, że wystarczy umieć obliczać wyniki dla przedziałów postaci $[1,n],$ ponieważ wynik dla przedziału $[a,b]$ jest różnicą wyników dla przedziałów $|[1,b]$ i $[1,a −1].$ Ponadto, jeśli $k$ nie jest liczbą pierwszą, to wynik jest równy 0, ponieważ jeśli liczba jest podzielna przez $k,$ to jest też podzielna przez każdy dzielnik $k,$ a skoro $|k$ nie jest pierwsza, to ma dzielnik większy od $1$ i mniejszy od $k.$ Załóżmy teraz, że $k$ jest pierwsza. Zadanie można rozwiązać w czasie $|O(n$ wyznaczając dla każdej liczby z przedziału $|[1,n]$ jej najmniejszy dzielnik, większy od 1, za pomocą sita Eratostenesa. Rozwiązanie to dla $n ⩽ 2⋅109$ jest dalece niewystarczające. Zauważmy, że można je łatwo usprawnić. Każda liczba, której najmniejszy dzielnik jest równy $k,$ jest postaci $k ⋅m,$ gdzie $m$ nie ma dzielników większych od $1$ i mniejszych od $k.$ Wystarczy zatem zliczyć takie $|m$ -y z przedziału $[1, | ⌊n⌋], k$ które nie mają dzielników pierwszych mniejszych od $k.$ Można to zrobić, iterując kolejne liczby pierwsze mniejsze od $k$ i zaznaczając w tablicy liczby podzielne przez którąś z nich.

Rozwiązanie to wykona dla każdej liczby pierwszej $|p,$ mniejszej od $k,$ $|nkp$ operacji, czyli łącznie

n- 1-= Θ k pQ>P,p@k p

{x ∈[1,n] k x}∖ ⎛ A . ⎝ p>P,p@k

Możemy to zrobić, korzystając z zasady włączeń i wyłączeń. W tym celu musimy umieć obliczyć $A$ Jest to zbiór liczb podzielnych przez $|kp1p2...pi,$ leżących w przedziale $[1,n],$ czyli ma $|⌊kppn...p⌋ 1 2 i$ elementów.

Całe rozwiązanie działa w czasie

O

Na to zadanie można też spojrzeć inaczej. Niech $|F(n,p)$ będzie liczbą liczb w przedziale $[1,n],$ które nie mają dzielników większych od $|1$ i mniejszych od $p.$ Wykażemy, że

n- F(n, p) = n − Q F (⌊q ⌋,q) q> P,q@p

Istotnie, liczb nie większych od $| n,$ których najmniejszym dzielnikiem jest $|q,$ jest $F (⌊nq ⌋,q),$ ponieważ każda taka liczba jest postaci $|q⋅m,$ gdzie $|m$ nie ma dzielników większych od $1 |$ i mniejszych od $q,$ a $|q⋅m$ czyli $|m$ Wszystkich liczb w przedziale $|[1,n]$ jest $n,$ a każda z nich albo ma dzielnik pierwszy mniejszy od $p,$ wówczas zostanie odjęta dokładnie raz, dla $q$ będącego jej najmniejszym dzielnikiem pierwszym, albo nie ma i wtedy nie zostanie odjęta. Liczba liczb w przedziale $| [1,n],$ których najmniejszym dzielnikiem jest $k,$ jest równa $n |F (⌊ k⌋,k) .$ Zadanie można rozwiązać, obliczając wartość funkcji $F,$ rekurencyjnie korzystając z tego wzoru. Niech $|p1,p2,...$ będą kolejnymi liczbami pierwszymi, a $T (n)$ liczbą operacji wykonanych przez algorytm dla liczby pierwszej $| pn.$ Wówczas $n− 1 |T(n) = 1+ P i 1 T (i).$ Rozwiązaniem tego równania jest $T(n) = Θ$ czyli całe rozwiązanie będzie działało w czasie $|O(2$ co jest zdecydowanie za wolne.

Rozwiązanie to można łatwo przyspieszyć. Wystarczy zauważyć, że jeśli $|n < p,$ to jedyną liczbą w przedziale $|[1,n]$ niemającą dzielników większych od $1$ i mniejszych od $p$ jest $1,$ więc $F(n, p) = 1$ i w każdym wywołaniu rekurencyjnym obliczającym wynik dla $n < p$ zwracać $min(1, n)$ bez dalszych wywołań rekurencyjnych. Wykażemy, że rozwiązanie z tą optymalizacją obliczające $F(n, p)$ wykona co najwyżej $|O(n)$ wywołań rekurencyjnych. Rozważmy gałąź w drzewie rekursji, w której algorytm wykonał kolejno dzielenia przez $|p1,p2,...,pi.$ Oznacza to, że w przedostatnim wywołaniu obliczał $F (⌊p1p2n...pi 1⌋,pi−1).$ Skoro nie zwrócił wyniku od razu, tylko wykonał następne wykonanie rekurencyjne, to $---n--- ⌊p1p2...pi 1⌋ ⩾ pi−1,$ skąd wynika, że $---n--- ⩾ pi−1, p1p2...pi 1$ czyli $n > p1p2...pi−2p2i− 1.$ Algorytm w danym wywołaniu przegląda jedynie liczby pierwsze, mniejsze od poprzedniej, zatem $|pi− 1 > pi,$ skąd otrzymujemy $|n > p1p2 ...pi.$ Liczby $pi$ są pierwsze, więc dla różnych wywołań rekurencyjnych iloczyny $p1p2 ...pi$ będą parami różne, więc liczba tych wywołań nie przekroczy $n.$

Prezentowane rozwiązanie potrzebuje listy liczb pierwszych mniejszych od $|min(n, p).$ Można ją, oczywiście, wyznaczyć, używając sita Eratostenesa, w czasie $O(min(n,$ Ostatecznie, całe rozwiązanie obliczające $n F (⌊p⌋,p)$ działa w czasie $|O$