[Algorytmy] Szybki test liczby koniecznych dzieleń w n!

Ginden · Post autor: **Ginden** » 25 lip 2012, o 12:37

Rozwiązując ...
Najpierw spróbowałem brute forcem, ale szybko odkryłem, że jest to metoda zbyt mało wydajna.
Próbowałem innych prostych metod, ale okazały się i tak zbyt złożone obliczeniowo.
W końcu stwierdziłem, że jako że w trójkącie Pascala n-ty wyraz (licząc od zera) w wierszu r to \(\displaystyle{ {r \choose n} = \frac{r!}{n!(r-n)!}}\), stwierdziłem, że muszę policzyć, ile wyrazów \(\displaystyle{ { 10^{9} \choose n}}\) dla \(\displaystyle{ n \epsilon \{0, 1, 2, ..., 10^{9}-1\}}\) jest podzielnych przez 7.
Łatwo stwierdzić, że \(\displaystyle{ 10^{9}!}\) zawiera w sobie 166666661 mnożeń przez 7. Kryterium, czy wyrażenie \(\displaystyle{ { 10^{9} \choose n}}\) też jest podzielne przez 7, jest proste - czy suma liczby mnożeń przez 7 w \(\displaystyle{ n!}\) i \(\displaystyle{ (10^{9}-n)!}\) są mniejsze od 166666661. Tylko jak to sprawdzić z naprawdę dużą szybkością (to jest miliard wyrazów i to naprawdę olbrzymich)?
Istnieje tez inna metoda, o której wiem, że można ją policzyć w ciągu sekund, ale przerasta mnie ona (sprowadza się do znalezienia prawidłowości rządzącej ).

ksisquare · Post autor: **ksisquare** » 26 lip 2012, o 00:32

Mimo absurdalność tematu (nie mimo a dzięki) zapiszę sobie. Ciekawska suma, jutro ja ugryzę (postaram się).
Często potrafię znaleźć silny dowód eksperymentalny, ale inni potrafią zakląć godziny (dni) obliczeń w kilku prostych równaniach.

Zawsze mam nadzieję, że nie dadzą rady, ale...

Zordon · Post autor: **Zordon** » 26 lip 2012, o 18:13

Da się to dosyć szybko policzyć z tw. Lucasa. Bez żadnych sprytnych sztuczek w kilka minut przemielisz.

ksisquare · Post autor: **ksisquare** » 26 lip 2012, o 18:17

i znowu.
daj jakąś linkę bo gugiel bzdurzy.

Zordon · Post autor: **Zordon** » 26 lip 2012, o 18:22

W polskiej wiki nie ma, jest tu:

edit: accept, przemieliło mi w 73 sekundy

ksisquare · Post autor: **ksisquare** » 26 lip 2012, o 19:00

jasna zupa, przepraszam.
czasem coś znanego wydaje się zbyt..., no kurde przecie to wszyscy wiedzą.
kurczę.
A z innej beczki
a jak to jest z wolnym słuchaczem?
jestem stary koń, a za oknem mam uczelnię
mogę tam wpadać na wykłady, czy też umundurowani emeryci będą starali się mnie wyprowadzić?
(pewnie, że mogę poczekać do rozpoczęcia roku.) smolę dyplomy, ale tak po prostu, mogę?

Zordon · Post autor: **Zordon** » 26 lip 2012, o 20:09

Na mojej uczelni (UWr) każdy jest mile widziany na wykładzie, z ćwiczeń też raczej nikogo się nie wyprasza.

ksisquare · Post autor: **ksisquare** » 26 lip 2012, o 20:13

planuję przeprowadzkę, właśnie tam fajnie.
ale jak to jest formalnie?

Zordon · Post autor: **Zordon** » 26 lip 2012, o 21:18

Hmm, wydaje mi się, że wykłady są po prostu otwarte, ale głowy nie dam. Na forum aktywnie udziela się Jan Kraszewski (pod takim właśnie nickiem), który jest wykładowcą w Instytucie Matematycznym, więc możesz się go spytać jak to jest formalnie.

ksisquare · Post autor: **ksisquare** » 27 lip 2012, o 19:15

Z pewnością, można to analitycznie, a nie iteracyjnie. Może wystarczy iteracja po wierszach i to po 7 na raz?

Kod: Zaznacz cały

0
00
000
0000
00000
000000
0000000
01111110
001111100
0001111000
00001110000
000001100000
0000001000000
00000000000000
011111101111110
0011111001111100
00011110001111000
000011100001110000
0000011000001100000
00000010000001000000
000000000000000000000
0111111011111101111110
00111110011111001111100
000111100011110001111000
0000111000011100001110000
00000110000011000001100000
000000100000010000001000000
0000000000000000000000000000
01111110111111011111101111110
001111100111110011111001111100
0001111000111100011110001111000
00001110000111000011100001110000
000001100000110000011000001100000
0000001000000100000010000001000000
00000000000000000000000000000000000
011111101111110111111011111101111110
0011111001111100111110011111001111100
00011110001111000111100011110001111000
000011100001110000111000011100001110000
0000011000001100000110000011000001100000
00000010000001000000100000010000001000000
000000000000000000000000000000000000000000
0111111011111101111110111111011111101111110
00111110011111001111100111110011111001111100
000111100011110001111000111100011110001111000
0000111000011100001110000111000011100001110000
00000110000011000001100000110000011000001100000
000000100000010000001000000100000010000001000000
0000000000000000000000000000000000000000000000000
01111111111111111111111111111111111111111111111110
001111111111111111111111111111111111111111111111100
0001111111111111111111111111111111111111111111111000
00001111111111111111111111111111111111111111111110000
000001111111111111111111111111111111111111111111100000
0000001111111111111111111111111111111111111111111000000
00000001111111111111111111111111111111111111111110000000
011111101111111111111111111111111111111111111111101111110
0011111001111111111111111111111111111111111111111001111100
00011110001111111111111111111111111111111111111110001111000
000011100001111111111111111111111111111111111111100001110000
0000011000001111111111111111111111111111111111111000001100000
00000010000001111111111111111111111111111111111110000001000000
000000000000001111111111111111111111111111111111100000000000000
0111111011111101111111111111111111111111111111111011111101111110
00111110011111001111111111111111111111111111111110011111001111100

Zordon · Post autor: **Zordon** » 28 lip 2012, o 13:10

Nie wiem o co pytasz w tej chwili, podałem wyżej, że tw. Lucasa daje rozwiązanie. Co prawda nie najszybsze, ale jak już dostaniesz akcepta będziesz mógł przeczytać o innych na forum zadaniowym.