Biorąc na wejściu liczbę całkowitą 1 ≤ N ≤ 1 000 000 , wypisz ostatnią niezerową cyfrę N! gdzie ! jest silnią (iloczyn wszystkich liczb od 1 do N włącznie). Jest to sekwencja OEIS A008904 .

Twój program musi zakończyć się w ciągu 10 sekund na rozsądnej maszynie dla każdego ważnego wejścia.

Przypadki testowe

1 => 1
2 => 2
3 => 6
4 => 4
5 => 2
6 => 2
7 => 4
8 => 2
9 => 8
10 => 8
100 => 4
1000 => 2
10000 => 8
100000 => 6
1000000 => 4

To jest golf golfowy, więc wygrywa najkrótszy kod w bajtach!

Rubin - 63 znaki

f=->n{n<2?1:6*[1,1,2,6,4,4,4,8,4,6][n%10]*3**(n/5%4)*f[n/5]%10}

Źródło - http://oeis.org/A008904

Obsługuje f do tysiąc cyfr w ciągu sekundy.

Test

irb(main):014:0> for n in 2..6
irb(main):015:1> puts f[10**n]
irb(main):016:1> end
4
2
8
6
4

Mathematica, 45 36 bajtów

Last@Select[IntegerDigits[#!],#>0&]&

Bardzo czytelny dla zwycięskiej odpowiedzi. :) (Z drugiej strony, nie ma jeszcze zgłoszenia GolfScript & Co.).

To obsługuje wejście 1 000 000 w około 5 sekund na moim komputerze.

Python - 75

n=input()
g=1
while n:
 g*=n
 while g%10<1:g/=10
 g%=10**9
 n-=1
print g%10

PARI / GP - 27 bajtów

Szybkość wymiany zależy od rozmiaru - testowanie zajmuje dużo czasu (~ 6 sekund).

n->n!/10^valuation(n!,5)%10

Ta wersja jest znacznie szybsza (~ 15 mikrosekund), ale zajmuje 81 bajtów:

n->r=1;while(n,r*=Mod(4,10)^(n\10%2)*[1,2,6,4,2,2,4,2,8][max(n%10,1)];n\=5);lift(r)

Możesz użyć tego (nie golfowego) kodu do przetestowania:

[%(10^n) | n <- [1..6]]

Windows PowerShell, 53 56 59 60 63 73 90

($a=1).."$input"|%{$a="$($a*$_)".trim('0')%1e7}
$a%10

Uwagi:

• Zajmuje więcej niż minutę dla liczby bliskiej 100 000. Jednak usunięcie zer na końcu wymaga konwersji na ciąg, wykonywanie obliczeń wymaga liczby, więc konwersje są nieuniknione.

Historia:

• 2011-02-08 10:31 (90) - Pierwsza próba.
• 2011-02-08 10:33 (73) - Moduł jest krótszy niż krojenie i łączenie.
• 2011-02-08 10:34 (63) - Niepotrzebne wykończenie.
• 2011-02-08 10:37 (60) - Niepotrzebna obsada na numer. Moduł już tak dobrze sobie radzi.
• 2011-02-08 10:40 (59) - Niektóre inlining.
• 2011-02-08 11:00 (56) - Co mówiłem wcześniej o tym, że moduł jest krótszy? Dotyczy również wyjścia.
• 2011-02-08 11:01 (53) - $inputWystarczy rzut na sznur; rzutowanie intjest stosowane domyślnie.

Perl, 53 58 61 postacie

Wszystkie białe znaki można usunąć, ale pozostawiłem to dla „czytelności”. Uwaga: nie używanie jakiejś głupiej, jawnej formuły Sloane.

sub f {
    $_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $_[0];
    $1 % 10
}

Oblicza f (10 ^ 6) w 8,7 sekundy na mojej maszynie.

Aktualizacja : OP chciał, aby był to cały program:

$_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $ARGV[0];
print $1 % 10

To daje 55 znaków.

CJam - 28

1ri{I)*_AbW%{}#A\#/1e7%}fIA%

Możesz spróbować na http://cjam.aditsu.net/ dla wartości do około 10000; w przypadku większych liczb należy użyć interpretera Java . 1000000 działa na moim laptopie w około 3 sekundy.

Wyjaśnienie:

Niestety, proste rozwiązanie jest zbyt wolne, więc po każdym pomnożeniu zachowuję tylko ostatnie 7 cyfr (przed końcowymi zerami).

1           push 1 on the stack
ri          read a token and convert to integer
{           loop (for I from 0 to N - 1)
    I)      push I and increment
    *       multiply with the previous value (initially 1)
    _Ab     duplicate and convert to array of digits
    W%      reverse array
    {}#     find the position of the first non-zero digit
    A\#     raise 10 to that power
    /       divide, thus removing all trailing zeros
    1e7%    keep the remainder modulo 10000000
}fI         end for loop
A%          get the last digit

Uwaga: ten język jest znacznie nowszy niż pytanie.

Mathematica, 34 bajty

Mod[#!/10^IntegerExponent[#!],10]&

05AB1E , 4 bajty

!0м¤

Wypróbuj online!

Wyjaśnienie

!0    # Push the factorial of the input and 0
  м   # Remove the occurences of 0 in the factorial
   ¤  # Push the last element, implicit display

Galaretka , 4 bajty

!Ṛȯ/

Wypróbuj online!

Wyjaśnienie

Wykorzystuje fakt, że kiedy Ṛ(odwraca listę; nie wektoryzuje) jest stosowana do liczby całkowitej, Dnajpierw automatycznie pobiera (cyfry).

Z wejściem 8:

!Ṛȯ/
!     Factorial: 8! = 40320
 Ṛ    Reverse: [0,2,3,0,4]
   /  Reduce by...
  ȯ   ...logical OR: ((((0ȯ2)ȯ3)ȯ0)ȯ4) = first truthy element = 2

Nie sądzę, że istnieje jeden bajtowy „pierwszy element zgodny z prawdą” (który ȯ/działa jako), ale jeśli tak, to można go skrócić do trzech bajtów ogółem.

Java (OpenJDK 8) , 62 bajty

n->{long f=n;for(;n>1||f%10==0;)f=n>1?f*--n:f/10;return f%10;}

Wypróbuj online!

Podobne do @Kevin Cruijssen, ale oszczędza 5 bajtów, łącząc pętle.

C, 150 140 135 bajtów

r,d;f(k,x){r=x<5?3:f(k+1,x/5);return(d=x%5)?r*"33436"[d]*(1<<d*k%4)%5:r;}main(int c,char**v){c=atoi(*++v);printf("%d",c<2?1:2*f(0,c));}

To jest wersja dla systemów ASCII; wymienić łańcuch 33436ze 11214dla systemu EBCDIC, lub \1\1\2\1\4na przenośnym programem.

Rozwiązania w C są nieco utrudnione przez wymóg zapewnienia pełnego programu; to jednak w pełni odpowiada na pytanie.

Wypróbuj online (wymaga Javascript):

• Tylko 1000000
• Pętla ze wszystkimi testami

Wyjaśnienie

Opiera się na algorytmie przedstawionym w Najmniej znaczącej niezerowej cyfrze n! , odwrócił się, abyśmy znaleźli najwyższą potęgę pięciu i dokonali obliczeń po wyjściu. Tabele stałych były zbyt duże, więc zmniejszyłem je, znajdując związek między poprzednią resztą r, bieżącą cyfrą di głębokością rekurencji k:

     0    1       2       3    4  =d
  0  0  3×2^k  1×2^2k  3×2^3k  2
  1  1  1×2^k  2×2^2k  1×2^3k  4
r 2  2  2×2^k  4×2^2k  2×2^3k  3
  3  3  3×2^k  3×2^2k  3×2^3k  2
  4  4  4×2^k  4×2^2k  4×2^3k  1

Bo r>0to rozwiązuje się do stałych czasów rrazy 2^dk(mod 5); stałe znajdują się a[]poniżej (wstawione w kodzie golfowym). Obserwujemy również, że (2^4)%5wynosi 1, więc możemy zmniejszyć wykładnik, aby uniknąć przepełnienia zakresu int.

const int a[] = { 1, 1, 2, 1, 4 };
int f(int k, int x){
    int r = x<5 ? 3 : f(k+1,x/5); /* residue - from recursing to higher-order quinary digits */
    int d = x%5;
    if (!d)
        return r;
    return r * a[d] * (1<<d*k%4) % 5;
}

int main(int c, char **v)
{
    c = atoi(*++v);
    printf("%d",
           c<2
           ? 1                  /* special-case 0 & 1 */
           : 2*f(0,c));         /* otherwise, it's 2 times r */
}

Testy:

$ for i in 100 1000 10000 100000; do echo $i: `./694 $i`; done
100: 4
1000: 2
10000: 8
100000: 6
1000000: 4

Wydajność jest również godna szacunku. Oto maksymalne wejście dla systemu z 32-bitami int:

$ time ./694 2147483647
8
real    0m0.001s
user    0m0.000s
sys     0m0.000s

Mam te same czasy przy maksymalnym 64-bitowym int.

PHP - 105

 <?foreach(explode("\n",`cat`)as$n)if($n){$f=rtrim(gmp_strval(gmp_fact($n)),'0');echo substr($f,-1)."\n";}

Działa poniżej 10 sekund z podaną walizką testową.

Python3

Może zrobić 10000 w ~ 3,2 sekundy (Ideone odcina mnie po 8 sekundach, jestem pewien, że zajmie to więcej niż 10 sekund :()

from functools import *
N=100
r=range
s=(p for p in r(2,N)if all(p%n>0for n in r(2,p)))
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=list([p,f(N,p)]for p in s)
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:x[0]**x[1],e))%10)

Python2.6

from itertools import *
N=100000
r=xrange
def s(c=count(2)):
        while 1:p=c.next();c=ifilter(p.__rmod__,c);yield p
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=[[p,f(N,p)]for p in takewhile(lambda x:x<N,s())]
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:pow(x[0],x[1],10),e))%10)

Haskell, 78 znaków

f n=head$dropWhile(=='0')$reverse$show$product[1..n]
main=interact(show.f.read)

(Prawdopodobnie trzeba go skompilować, aby obliczyć 1 000 000! W 10 sekund).

J - 42 40 znaków

Cały program. Zapisz ten program w pliku i uruchom z jconsole script.ijs 1234. Zauważ, że ten program nie wychodzi z interpretera po wydrukowaniu wyniku. Wpisz ^Dlub, exit]0aby wyjść z interpretera.

echo([:{:@(#~*)10&#.inv@*)/1+i.".>{:ARGV

Oto wyjaśnienie:

• x #. yinterpretuje wektor liczb całkowitych yjako xliczbę podstawową ; na przykład 10 #. 1 2 3 4daje 1234.
• u invzwraca odwrotność czasownika u. W szczególności x #. inv yreprezentuje yjako xliczbę podstawową ; na przykład 10 #. 1234daje 1 2 3 4. Należy zauważyć, że invokreśla się jako ^:_1, że jest ustosowana -1 czasu.
• x * yJest to produkt z xi yw ten sposób x 10&#.inv@* yuzyskuje się bazowym 10 przedstawienie produktu xi y.
• x # ykopiuje n- ty element ytak często, jak n- ty element x; kiedy xjest wektorem wartości logicznych, xwybiera, które przedmioty ywziąć. Na przykład 1 0 1 0 # 1 2 3 4daje 1 3.
• * yotrzymano signum się y.
• x u~ yjest zwrotna od u, czyli taki sam jak y u x.
• W ten sposób y #~ * yuzyskuje się wektor wszystkich elementów, yktóre są dodatnie. W milczącej notacji można to zapisać za pomocą haka jako (#~ *).
• {: ydaje ostatni element w y.
• zebrane razem otrzymujemy milczącą frazę ([:{:@(#~*)10&#.inv@*).
• u/ yJest to zmniejszenie o y, to znaczy dwójkowym czasownik uwstawione pomiędzy elementami y. Na przykład +/1 2 3 4jest podobny 1 + 2 + 3 + 4i daje 10.
• W ten sposób wyrażenie ([:{:@(#~*)10&#.inv@*)/ yzwraca ostatnią cyfrę iloczynu pozycji y.
• ARGV jest zapakowanym wektorem argumentów wiersza poleceń.
• ".>{:ARGV jest ostatnim argumentem rozpakowanym i interpretowanym jako liczba.
• i. yoblicza liczby naturalne od 0do y - 1.
• W ten sposób 1+i. yuzyskuje się liczby naturalne od 1do y. Mógłbym również użyć >: przyrostu tutaj, ale 1+jest jaśniejszy przy tym samym koszcie postaci.
• Cały program po prostu stosuje 1+i.".>{:ARGV(wektor 1do liczby w ostatnim argumencie wiersza poleceń) do czasownika ([:{:@(#~*)10&#.inv@*)/i wypisuje wynik za pomocą echo.

Pyt , 5 bajtów

!₫ą0⦋

Wyjaśnienie:

         Implicit input (n)
!        n!
 ₫       Reverse the digits of (n!) - this disregards leading zeroes after reversal
  ą      Convert to array of digits
   0⦋    Get the first element

Wypróbuj online!

R , 63 55 51 46 bajtów

Oblicza silnię, wyodrębnia ostatnią niezerową cyfrę. Dzięki Giuseppe za zapewnienie podstawowej struktury.

(y=(gamma(scan()+1))%/%10^(0:1e5)%%10)[!!y][1]

Wypróbuj online!

Alternatywnie, moja stara 51-bajtowa odpowiedź:

Oblicza silnię, konwertuje na postać, usuwa wszystkie 0s, a następnie przyjmuje końcowy znak. Zaoszczędzono 2 bajty dzięki Giuseppe.

substring(x<-gsub("0","",gamma(scan())+1),nchar(x))

Wypróbuj online!

> <> , 25 bajtów

v:a%:?n-a,!
1
>$::?!.1-}*

Wypróbuj online!

Obsługuje 0! również poprawnie. Wartość przekazana przez -vflagę.

Perl 6 ,  26  35 bajtów

{[*](1..$_)~~/.*<(<-[0]>/}

Spróbuj

Jako pełny program:

put [*](1..@*ARGS[0])~~/.*<(<-[0]>/

Spróbuj

Rozszerzony:

{
  [*]( 1..$_ ) # reduce using &infix:« * »
  ~~           # match with
  /
    .*         # any number of values (so it matches from the end)
    <(         # only capture the following
    <-[0]>     # any value but 0 (negated character class)
  /
}

C (gcc) , 72 bajty (funkcja)

f(n,d)long long n,d;{for(d=1;n;d%=10000)for(d*=n--;d%10<1;d/=10);d%=10;}

Wypróbuj online!

C (gcc) , 101 99 bajtów (cały program)

main(){long long n,d=1;for(scanf("%lld",&n);n;d%=10000)for(d*=n--;d%10<1;d/=10);printf("%d",d%10);}

Wypróbuj online!

To pytanie jest po prostu nieśmiałe od 8 lat, więc „rozsądna maszyna” nie jest już taka sama jak wtedy, ale otrzymuję czasy ~ 0,01 sekundy na moim komputerze, kiedy wykonuję wszystkie przypadki testowe razem, więc chyba, że ​​komputery przyspieszyły 1000 razy w ciągu ostatniej dekady powinno być w porządku.

Dodaj ++ , 11 bajtów

L,RB*EDBFEZ

Wypróbuj online!

Attache , 26 bajtów

Last@`\&:(All@V)@Digits@`!

Wypróbuj online!

Wyjaśnienie

Last@`\&:(All@V)@Digits@`!

Jest to kompozycja 4 funkcji:

• `! - jest to funkcjonalna wersja operatora silni
• Digits - otrzymuje cyfry silni
• \&:(All@V)- To jest funkcja wyboru. Działa poprzez zostawienie spojenia ( &:) funkcji All@Vdo \, co wybrać. Z kolei All@Vjest krótkim sposobem sprawdzenia, czy liczba nie jest równa 0. Działa poprzez rzutowanie danych wejściowych na wektor, 0 -> [0]a następnie sprawdzanie, czy wszystkie te elementy są zgodne z prawdą (tj. Nie 0). Daje to cyfry liczby bez zer.
• Last - to po prostu uzyskuje ostatniego członka tej tablicy.

APL (Dyalog Unicode) , 18 15 bajtów

{⊢/⍵/⍨0≠⍎¨⍵}⍕∘!

Wypróbuj online!

Funkcja ukrytego przedrostka. Zwraca poprawną cyfrę dla pojedynczego przypadku testowego lub ciąg cyfr dla wielu przypadków testowych.

Dzięki @ Adám i @ErikTheOutgolfer za 3 bajty każdy.

W jaki sposób?

{⊢/⍵/⍨0≠⍎¨⍵}⍕∘! ⍝ Main function. Argument is a number following the !.
              ! ⍝ Factorial
             ∘  ⍝ then
            ⍕   ⍝ Format (stringify)
        ⍎¨⍵}    ⍝ Execute (turn to number) each digit of the argument
      0≠        ⍝ Check if each is ≠0. This returns a boolean vector
     ⍨          ⍝ Swap arguments for the following fn/op
   ⍵/           ⍝ Replicate. This takes a boolean vector as left arg and returns the truthy elements of the right arg. E.g.: 1 1 0/1 2 3 → 1 2.
{⊢/             ⍝ Reduce. This returns the rightmost (last) element of a vector argument.

APL NARS, 28 bajtów, 14 znaków

{↑≠v/v←⌽⍎¨⍕!⍵}

Nie wiem dlaczego, ale ten test zdał:

  q←{↑≠v/v←⌽⍎¨⍕!⍵}       
  q¨1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 6 4 2 2 4 2 8 8 8 6 8 2 

AWK , 47 57 bajtów

{for(p=$1;--$1;p=(p*$1)%1e4)while(!(p%10))p/=10;$0=p%10}1

Wypróbuj online!

Oryginalne rozwiązanie nie radziło sobie dobrze z „dużymi” wartościami wejściowymi. Można dodać, -Maby zmusić go do działania, ale wymaga to również dużo więcej czasu przetwarzania.

Japt , 6 bajtów

Wymyśliłem kilka różnych 6-bajtowych, ale ten najbardziej mi się podobał. Jestem jednak przekonany, że musi być sposób, aby to zrobić w 5.

Êsw ìv

Spróbuj

Wyjaśnienie

Êoblicza silnię danych wejściowych, skonwertuje ją na ciąg znaków i wraca do liczby całkowitej po wodwróceniu go, ìkonwertuje wynik na tablicę cyfr i vzwraca pierwszy element.

Alternatywy

Êì w æ
ÊìÈf Ì
Êì f o
Êsw sg
Êìf ìo
Êìf ìÌ

Perl 5 , 36 + 10 ( -p -Mbigint) = 46 bajtów

$"=$_;$_*=$"while$"-=1;($_)=/(.)0*$/

Wypróbuj online!