[RysiuFujara]

Zadanie ze SPOJ dwie cyfry silni
http://pastebin.com/0ZfxqqKD
SPOJ nie przyjmuje i zwraca "przekroczono limit czasu"
Dlaczego?
W ogóle to warto bawić się w tego SPOJ'a, bo słyszałem że jest mocno zabugowany?
#naukaprogramowania

[KamilAC]

@RysiuFujara: Wypisz sobie wszystkie wartości silni od 0 do 10 i zastanów się jak zrobić to łatwiej

[phoe]

@RysiuFujara: ale chwila moment, przecież to można zrobić w czasie stałym
dla 0! to będzie 00
dla 1! to będzie 01
dla 2! to będzie 02
dla 3! to będzie 06
dla 4! to

[phoe]

@RysiuFujara dodatkowo - twój int nie jest w stanie pomieścić tak dużych liczb, jakimi są silnie z miliarda, a samo policzenie silni z miliarda będzie ci trwało wieki ( ͡° ͜ʖ ͡°)

[RysiuFujara]

@phoe: @KamilAC: Ok dzięki wielkie ( ͡° ͜ʖ ͡°) Z tym intem to faktycznie z------m

[phoe]

@RysiuFujara: jak pomogłem to dej plusa ( ͡° ͜ʖ ͡°)

[RysiuFujara]

@phoe: Taa wiem co to silnia :D studbaza here, zacząłem się programowania uczyć z parę dni temu chociaż jest praktycznie nie związany z moim kierunkiem.
No i nie wpadłem na to ze po 10! zawsze jest 0 0

[matrix929]

@RysiuFujara: wskazówka: rozpatrz ile masz 5 i 2 w rozkładzie silni, nawet same piątki ci wystarczą. Ile masz piątek tyle masz zer, bez dobrego sposobu nie policzysz np. ostatnich cyfr 1000000000!

[matrix929]

@RysiuFujara: a dobra p------y mi się zadania, myślałem że ostatnia niezerowa cyfra XD

[B.....c]

@phoe 0! to jest 1 ( ͡° ͜ʖ ͡°)

[phoe]

@BazaltowyTubylec: ayy, masz rację :D

[RysiuFujara]

@phoe: @matrix929: Dobra mam kolejne pytanie, nie będę tworzył nowego wątku bo pewnie odpowiedz jest trywialna. Co jest nie tak z moją odpowiedzią w tym zadaniu?
Z tego co wyczytałem pow() zwraca czasem floata np 10^2 to 99.9999... no to go zaokrąglam zmieniam z powrotem na inta (wszystko tu ok?) i wyznaczam cyfre jedności. Jak sprawdzam czy dziala poprawnie to wszystko ok, a w SPOJu jest lipa.

[matrix929]

@RysiuFujara: Jeśli mam dać wskazówkę, to wszystko zależy od ostatniej cyfry liczby potęgowanej, nie optymalizując zmiennych możesz wykroczyć poza ich zakres co automatycznie spowoduje błędny wynik, pierwsze co masz zrobić to zoptymalizuj zmienną. Jeszcze jedna wskazówka, jeśli chodzi o ostatnią cyfrę to istnieje pewna zależność, pewnie okres, spróbuj to zauważyć ;)

[phoe]

@RysiuFujara: nie rób tego za pomocą pow().
jest twierdzenie, które mówi o potęgowaniu modulo.
wyznaczanie ostatniej cyfry - to nic innego jak potęgowanie jakiejś liczby modulo 10.
znajdź je, poczytaj o nim, i zrób to zadanie nie korzystając w ogóle z floatów.

[phoe]

@matrix929: w skrócie, dla liczb całkowitych:
jak potęgujesz a^b, gdzie b = c\*d\*e\*f\*g, to:
a^b mod x = ((((a^c mod x)^d mod x)^e mod x)^f mod x)^g mod x
możesz to wykorzystać i tak naprawdę zamiast całej liczby, potęgować tylko jej ostatnią cyfrę, a z otrzymanego wyniku też zawsze brać tylko ostatnią cyfrę do przyszłych obliczeń. a to jest proste i da się zrobić w czasie logarytmicznym od potęgi, czyli

[RysiuFujara]

@phoe: Hah okey, to chyba jednak jak na piąty dzień nauki to trochę za daleko poleciałem, ale dzięki wielkie poczytam o tym twierdzeniu. Możesz mi tylko powiedzieć co jest złego w moim rozumowaniu i co tam się dzieje źle? :D

[phoe]

@RysiuFujara: pow() zwraca Ci przybliżenie jakiejś potęgi, a przybliżenie dużej liczby nie zachowuje ostatnich jej cyfr.