Codegolf — Последняя Ненулевая Цифра N!

Учитывая целое число 1 ≤ N ≤ 1 000 000 в качестве входных данных выведите последнюю ненулевую цифру Н!, где ! факториал (произведение всех чисел из 1 к Нвключительно). Это последовательность OEIS A008904.

Ваша программа должна завершиться в течение 10 секунд на подходящей машине для любого допустимого ввода.

Тестовые случаи

 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
 

Это значит, что побеждает самый короткий код в байтах!

#код-гольф #код-гольф #математика #теория чисел #факториал #ограниченное время

Математика, 45 36 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 -M 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Очень читабельно для выигрышного ответа. :) (Опять же, заявок от GolfScript & Co. еще нет.)

Это обрабатывает ввод 1 000 000 примерно за 5 секунд на моей машине.

Рубин — 63 символа

Источник - http://oeis.org/A008904

Обрабатывает до тысячи цифр менее чем за секунду.

Тест

Питон - 75

ПАРИ/ГП — 27 байт

Это меняет скорость на размер — тестовый пример занимает много времени (~ 6 секунд).

Эта версия намного быстрее (~ 15 микросекунд), но занимает 81 байт:

Вы можете использовать этот код (без игры в гольф) для проверки:

Перл, 53 года 58 61 персонажи

Все пробелы можно удалить, но я оставил их для «читабельности». Примечание: не используйте какую-то глупую явную формулу Слоана.

На моей машине вычисляет f(10^6) за 8,7 секунды.

Обновлять:ОП хотел, чтобы это была целая программа:

Это составляет 55 символов.

СиДжем - 28

Вы можете попробовать это на http://cjam.aditsu.net/ для значений до 10000 или около того; для больших чисел вы должны использовать Java-интерпретатор. На моем ноутбуке 1000000 выполняется примерно за 3 секунды.

Объяснение:

К сожалению, простое решение слишком медленное, поэтому я сохраняю только последние 7 цифр (до конечных нулей) после каждого умножения.

Примечание: этот язык намного новее, чем вопрос.

Математика, 34 байта

Java (OpenJDK 8), 62 байта

Попробуйте онлайн!

Аналогично @Kevin Cruijssen, но экономит 5 байт за счет объединения циклов.

С, 150 140 135 байт

Это версия для систем ASCII; заменить строку 1+ with >: для системы EBCDIC или с y for a portable program.

Решения C немного затруднены требованием предоставления полной программы; однако это полностью отвечает на вопрос.

Попробуйте онлайн (требуется Javascript):

• всего 1000000
• Цикл со всеми тестовыми примерами

Объяснение

Он основан на алгоритме, изложенном в Младшая ненулевая цифра числа n!, развернулись так, что мы возвращаемся внутрь, чтобы найти высшую степень пяти, и выполняем вычисления на выходе. Таблицы констант оказались слишком большими, поэтому я сократил их, найдя связь между предыдущим остатком 1 , the current digit 1+i. y и глубина рекурсии y - 1 :

Для i. y , this resolves to a constant times ".>{:ARGV раз ARGV (mod 5); the constants are in y ниже (встроено в код игры в гольф). Мы также наблюдаем, что ([:{:@(#~*)10&#.inv@*)/ y is 1, so we can reduce the exponent to avoid overflowing the range of 10 .

Тесты:

Производительность тоже достойная. Вот максимальный ввод для системы с 32-битной версией y :

У меня такие же тайминги получились на максимальной 64-битной y , too.

PHP - 105

Работает менее 10 секунд с данным тестовым примером.

Python3

Могу сделать 10000 примерно за 3,2 секунды (Ideone прерывает меня на 8 секундах, хотя я уверен, что это займет больше 10 секунд :( )

Питон2.6

Хаскель, 78 символов

(Вероятно, потребуется скомпилировать для вычисления 1 000 000! за 10 секунд).

J – 42 40 символов

Целая программа. Сохраните эту программу в файл и запустите с помощью (#~ *) . Notice that this program does not exit the interpreter after printing a result. Type y или y #~ * y to exit the interpreter.

Вот объяснение:

• u interprets the integer vector x u~ y в качестве базы y число; например, * y урожайность 1 3 .
• 1 0 1 0 # 1 2 3 4 yields the обратный глагола y . In particular, x представляет x as a base x number; for example, y yields x # y . Обратите внимание, что y is defined as x , то есть, x 10&#.inv@* y applied -1 time.
• y is the продукт из x и x * y , таким образом u yields a base-10 representation of the product of ^:_1 and inv .
• 1 2 3 4 copies the н-й пункт 10 #. 1234 as often as the н-й пункт x ; when y вектор логических значений, x #. inv y selects which items of u взять. Например, u inv yields 1234 .
• 10 #. 1 2 3 4 yields the сигнум из x .
• y is the рефлексивный из x #. y , that is, the same as echo([:{:@(#~*)10&#.inv@*)/1+i.".>{:ARGV .
• Таким образом, exit]0 yields a vector of all items of ^D это позитивно. В неявной записи это можно записать с помощью крюк как jconsole script.ijs 1234 .
• f n=head$dropWhile(=='0')$reverse$show$product[1..n] main=interact(show.f.read) yields the last item in 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))) .
• собрались вместе, получаем негласную фразу 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))) .
• <?foreach(explode("\n",`cat`)as$n)if($n){$f=rtrim(gmp_strval(gmp_fact($n)),'0');echo substr($f,-1)."\n";} is the снижение из int , that is, the dyadic verb $ time ./694 2147483647 8 real 0m0.001s user 0m0.000s sys 0m0.000s вставляется между элементами int . For instance, $ for i in 100 1000 10000 100000; do echo $i: `./694 $i`; done 100: 4 1000: 2 10000: 8 100000: 6 1000000: 4 это как 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 */ } and yields int .
• Таким образом, фраза (2^4)%5 yields the last digit of the product of the items of a[] .
• 2^dk is a boxed vector of the command line arguments.
• r is the last argument unboxed and interpreted as a number.
• r>0 computes natural numbers from 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 к k .
• Таким образом, d yields natural numbers from r к \1\1\2\1\4 . I could have also used 11214 приращение здесь, но 33436 is clearer at the same cost of characters.
• Вся программа просто применяется 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));} (the vector of n->{long f=n;for(;n>1||f==0;)f=n>1?f*--n:f/10;return f;} к числу в последнем аргументе командной строки) к глаголу Mod[#!/10^IntegerExponent[#!],10]& and prints the result with 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 .

Перл 6, 26 35 байт

Попробуйте это

По полной программе:

Попробуйте это

Расширено:

С (ГКК), 72 байта (функция)

Попробуйте онлайн!

С (ГКК), 101 99 байт (вся программа)

Попробуйте онлайн!

Этому вопросу едва исполнилось 8 лет, поэтому «разумная машина» уже не та, что тогда, но я получаю на своем компьютере время ~ 0,01 секунды при совместном выполнении всех тестовых примеров, поэтому, если скорость компьютеров не увеличится в 1000 раз за последнее десятилетие, все должно быть в порядке.

Атташе, 64 байта

Попробуйте онлайн!

Простая реализация формулы OEIS. n=input() g=1 while n: g*=n while g<1:g/=10 g%=10**9 n-=1 print g compresses the hardcoded dictionary using Attache's compressed number feature. 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 относится к самой функции в этом ответе.

АВК, 47 57 байт

Попробуйте онлайн!

Исходное решение не очень хорошо обрабатывало «большие» входные значения. Мог бы добавить Last@Select[IntegerDigits[#!],#>0&]& to force it to work, but that also requires a lot more processing time.