Mod przez moc 2 [duplikat]

Question

Na zajęciach z informatyki musiałem rozwiązać następujący problem z Codeforces: https://codeforces.com/problemset/problem/55/A Chodzi o poduszki umieszczone na okręgu i przeskakującą muchę $n$ poduszki, gdzie $n = \overline{0,k}$. Mucha robi to przez nieskończoną ilość czasu. Czy mucha dotrze do wszystkich poduszek dla określonej liczby poduszek$z$?

Bawiąc się odkryłem, że mucha może dosięgnąć wszystkich poduszek przy początkowej liczbie poduszek $z$jest potęgą 2 i program został rozwiązany, ale chcę to matematycznie udowodnić. Udało mi się opisać ruchy muchy następującą sekwencją:$a_n = (a_{n-1} + n)mod\ z, a_0 = 1;$ Szukając informacji w internecie, dowiedziałem się, że umiem pisać $a_n = (a_{n-1} + n)$ jako ta jawna funkcja $\frac{n(n+1)}{2} + 1$. Tutaj utknąłem. Czy jest jakaś metoda, aby to udowodnić w przystępny sposób (dla studenta pierwszego roku informatyki)?

Answer 1

Kontynuując twój tok myślenia, pytanie sprowadza się do pytania, czy wszystkie pozostałe modyfikacje $z$ ma postać $\tfrac{n(n+1)}{2}+1$ dla niektórych nieujemnych liczb całkowitych $n$. Zauważ, że jeśli$n\equiv m\pmod{z}$ również wtedy $$\frac{n(n+1)}{2}+1\equiv\frac{m(m+1)}{2}+1,$$więc jeśli reszta ma postać$\tfrac{n(n+1)}{2}+1$ dla niektórych nieujemnych liczb całkowitych $n$, to też ma formę $\tfrac{n(n+1)}{2}+1$ dla niektórych nieujemnych liczb całkowitych $m<z$. To pokazuje, że mucha dociera do każdej poduszki wtedy i tylko wtedy, gdy mapa$$\Bbb{Z}/z\Bbb{Z}\ \longrightarrow\ \Bbb{Z}/z\Bbb{Z}:\ n\ \longmapsto\ \frac{n(n+1)}{2}+1,$$jest surjektywna. Dlatego$\Bbb{Z}/z\Bbb{Z}$jest skończona, dzieje się tak wtedy i tylko wtedy, gdy mapa jest iniekcyjna. Czy możesz dowiedzieć się, do czego$z$ mapa jest iniekcyjna?

Nawiasem mówiąc, należy zachować ostrożność na piśmie $\tfrac{n(n+1)}{2}+1$ w $\Bbb{Z}/z\Bbb{Z}$. Gdyby$z$ nawet wtedy nie jest jasne, przez jaki podział $2$powinno znaczyć. W powyższym tylko pamiętaj, że otrzymaliśmy to wyrażenie z$$\tfrac{n(n+1)}{2}=1+2+3+\ldots+n.$$

---

Bez konieczności dokładnego określania, dla jakich wartości $z$ta mapa jest surjektywna, ta idea już pomaga w pisaniu programu; to pokazuje, że jeśli mucha w końcu dociera do wszystkich poduszek, potem dotrze wszystkie poduszki wewnątrz$z$minuty. Musisz więc tylko sprawdzić pozycję muchy w pierwszej$z$minuty; jeśli dwukrotnie odwiedzi tę samą poduszkę, gotowe. Jeśli nie, to odwiedza każdą poduszkę.