szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 23 sty 2018, o 00:51 
Użytkownik

Posty: 29
Lokalizacja: A kto to wie
Określ postac liczb podzielnych przez 13, które leżą najbliżej liczby utworzonej z jedynki i miliona zer. A może ta liczba jest podzielna przez 13?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 23 sty 2018, o 00:58 
Gość Specjalny
Avatar użytkownika

Posty: 18423
Lokalizacja: Cieszyn
Krótko mówiąc, musimy wyznaczyć resztę z dzielenia tej liczby przez 13. Wskazówka: 10^6\mod 13=1.

Ukryta treść:    
Góra
Mężczyzna Offline
PostNapisane: 23 sty 2018, o 01:29 
Użytkownik

Posty: 29
Lokalizacja: A kto to wie
Dla 10^{6} jestem jeszcze w stanie znaleźć resztę modulo 13. Sposób z którego korzystam polega na policzeniu najpierw reszty modulo 13 liczby 10, potem będę w stanie policzyć 10^{10} jako iloczyn 5 tych poprzednich wyników itd. Sposób ten jest jednak chyba niezbyt optymalny przy próbie policzenia reszty modulo 13 liczby utworzonej z jedynki i miliona zer. Dlatego mam, pytanie jak powinno to się robic optymalnie?
Góra
Mężczyzna Offline
PostNapisane: 23 sty 2018, o 16:20 
Gość Specjalny
Avatar użytkownika

Posty: 18423
Lokalizacja: Cieszyn
Optymalnie jest tak, że reszty zachowują się w mnożeniu: (ab)\mod n = \bigl((a\mod n)\cdot(b\mod n)\bigr)\mod n. Aby wyznaczyć resztę z iloczynu, wystarczy pomnożyć reszty czynników i ewentualnie wziąć kolejną resztę. Komfortowo jest, gdy reszta jakiegoś czynnika to 1. Wtedy bezpośrednio przenosi się to na dowolnie wysokie potęgi.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile sposobow - wybor trzech liczb, aby suma byla parzysta  Anonymous  2
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 Układanie liczb o różnych cyfrach podzielnych przez...  birdy1986  4
 Na ile sposobów... (suma 3 liczb rowna 11)  Anonymous  3
 losowanie cyfr - ile liczb mozna utworzyc?  Banan  8
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl