szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 00:33 
Użytkownik
Avatar użytkownika

Posty: 3400
Lokalizacja: Krk
Witam, mam pewien problem przy implementacji kodu. Muszę policzyć resztę z pewnego wyrażenia. Generalnie działanie postaci (x-1)^n \mod x^2. Czy da się to zrobić jakoś prościej, to znaczy nie podnosząc na starcie do n-tej potęgi?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 00:53 
Użytkownik
Avatar użytkownika

Posty: 12431
Lokalizacja: czasem Warschau, czasem Breslau
Na programowaniu się nie znam, mimo że niby chodziłem na programowanie obiektowe, nawet zdałem, natomiast rzeczywiście można to chyba nieco uprościć. Ze wzoru dwumianowego Newtona mamy
(x-1)^n= \sum_{k=0}^{n} {n \choose k}x^{k}(-1)^{n-k}
i zauważmy, że wszystkie wyrazy tego rozwinięcia prócz dwóch pierwszych dzielą się przez x^2, zatem
(x-1)^n\equiv (-1)^n+nx(-1)^{n-1}\pmod{x^2}
Jak n jest ustalone (czy choćby ustalonej parzystości), zaś x się zmienia, to jest z tego jakaś korzyść... Ale nie wiem, czy konkretnie coś to daje.
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 11:41 
Użytkownik
Avatar użytkownika

Posty: 3400
Lokalizacja: Krk
Zatrzymałem się na zapisaniu sumy, nie wywnioskowałem, że faktycznie tylko 2 wyrazy będą resztą. Dokładnie o to mi chodziło. Dzięki za pomoc.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podzielność sumy elementów zbioru  Hayran  1
 "Udowodnij"... Podzielność z niewiadomymi  NephilimV  4
 podzielnosc liczb?  Anonymous  3
 Podzielność przez 19  Leeq3  2
 wykaz podzielnosc przez 24  Rafix_  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl