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

Posty: 3383
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?
Góra
Mężczyzna Online
PostNapisane: 20 lip 2017, o 23:53 
Użytkownik
Avatar użytkownika

Posty: 11187
Lokalizacja: Wrocław
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 10:41 
Użytkownik
Avatar użytkownika

Posty: 3383
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 
 Rozłożenie wielomianu na czynniki i podzielność  topos  3
 podzielność - udowodnij że... (łatwe)  aniu_ta  10
 Podzielnosc pierwiastków wielomianiu i kongruencja  fxxn  1
 Dowód na podzielność - zadanie 4  bobokaboboka  2
 Podzielność liczby binarnej przez 4  Niewpisze  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl