Ile reszt modulo

[mkt]

Cześć, mam problem z zadaniem.
Niech n będzie pewną liczba naturalną. Ile reszt modulo n jest względnie pierwszych z liczbą 30? Obliczenia przeprowadź dla n=1000.

Bardzo proszę o pomoc bo kompletnie nie wiem jak się wziąć za to zadanie.
Z góry dzięki za pomoc.

[Premislav]

\(\displaystyle{ 30=3\cdot 2\cdot 5}\), więc należy policzyć liczby spośród \(\displaystyle{ 0,1,2\ldots 999}\), które nie dzielą się przez \(\displaystyle{ 2}\), przez \(\displaystyle{ 3}\) lub przez \(\displaystyle{ 5}\).
Można to zrobić z użyciem zasady włączeń i wyłączeń. Znasz ją?

[mkt]

Znam, ale nadal nie wiem jak ją wykorzystać na tym konkretnym przykładzie.

[PoweredDragon]

\(\displaystyle{ 30 = 3 \cdot 2 \cdot 5}\)

Ogólnie to można to zrobić ze znanej zależności, że liczb podzielnych przez \(\displaystyle{ k}\) w zbiorze \(\displaystyle{ N = \left\{0, 1, 2, ..., n-1}\right\}}\) jest \(\displaystyle{ \lfloor {\frac{n-1} {k}} \rfloor + 1}\)
Rozwiązanie (Nie patrz, dopóki nie rozwiążesz )

Ukryta treść:    

Liczb podzielnych przez 2 w zbiorze \(\displaystyle{ N}\) jest \(\displaystyle{ \lfloor {\frac{n-1}{2}} \rfloor+ 1}\)
Liczb podzielnych przez 3 w zbiorze \(\displaystyle{ N}\) jest \(\displaystyle{ \lfloor {\frac{n-1}{3}} \rfloor+ 1}\)
Liczb podzielnych przez 5 w zbiorze \(\displaystyle{ N}\) jest \(\displaystyle{ \lfloor {\frac{n-1}{5}} \rfloor+ 1}\)
Liczb podzielnych przez 6 w zbiorze \(\displaystyle{ N}\) jest \(\displaystyle{ \lfloor {\frac{n-1}{6}} \rfloor+ 1}\)
Liczb podzielnych przez 10 w zbiorze \(\displaystyle{ N}\) jest \(\displaystyle{ \lfloor {\frac{n-1}{10}} \rfloor+ 1}\)
Liczb podzielnych przez 15 w zbiorze \(\displaystyle{ N}\) jest \(\displaystyle{ \lfloor {\frac{n-1}{15}} \rfloor+ 1}\)

A zatem liczb względnie pierwszych z 30 mniejszych od \(\displaystyle{ n}\) jest \(\displaystyle{ R_{30}(n) = (n-1)-(\lfloor {\frac{n-1}{2}} \rfloor+\lfloor {\frac{n-1}{3}} \rfloor+\lfloor {\frac{n-1}{5}} \rfloor-\lfloor {\frac{n-1}{6}} \rfloor-\lfloor {\frac{n-1}{10}} \rfloor-\lfloor {\frac{n-1}{15}} \rfloor)}\)