Задача состоит в том, чтобы вычислить сумму делителей числа с учетом его первичной факторизации.

вход

Два массива (или что-то эквивалентное) длины n , один из которых содержит простой множитель, а другой - соответствующий показатель степени.

Выход

Сумма всех делителей (включая само число).

пример

Число 240 имеет 2, 3 и 5 как простые множители с 4, 1 и 1 как соответствующие показатели. Ожидаемый результат будет 744.

Input: [2,3,5] [4,1,1]
Output: 744

счет

Самый короткий код в байтах побеждает!

Если сложность времени выполнения вашего решения составляет O (сумма показателей), а не O (произведение показателей), ваш результат может быть умножен на 0,8.

Здесь был опубликован похожий вопрос , но это не было проблемой. Я думаю, что проблема в том, чтобы играть в гольф.

Победитель будет выбран в эти выходные

Pyth, 13 байтов * 0,8 = 10,4

*Fms^LhdhedCQ

Демонстрация.

Этот ответ работает несколько иначе, чем выше. Чтобы вычислить сумму факторов простых степеней числа, вместо использования арифметической формулы, факторы явно построены и суммированы.

Так , например, на [премьер, показатель] пары [2, 4], мы отображаем 2 ^ xнад 0, 1, 2, 3, 4, давая [1, 2, 4, 8, 16], который затем суммируется до 31.

Результаты затем умножаются вместе и печатаются.

Если возведение в степень реализовано правильно, или если есть промежуточное кэширование результатов, это будет O(sum of exponents).

CJam, 15 байтов * 0,8 = 12

q~.{_@)#(\(/}:*

Попробуйте онлайн . Порядок ввода - сначала список экспонент, затем список простых чисел (-3 байта благодаря @Dennis) .

Для каждой пары простых чисел (p, e)найти

(p^(e+1) - 1)/(p - 1)

затем найдите продукт всего этого. Например, для 240 это будет

(1 + 2 + 4 + 8 + 16)(1 + 3)(1 + 5) = 31 * 4 * 6 = 744

В зависимости от того, как возведено возведение в степень, это может быть лучше, чем O(sum of exponents).

APL, 18 13 байтов * 0,8 = 10,4

×/(1-⊣×*)÷1-⊣

Это создает цепочку диадических функций, которая принимает массив факторов слева и показатели степени справа.

×/             ⍝ Vector product of
  (1-⊣×*)      ⍝ each factor^(exponent+1)-1
         ÷1-⊣  ⍝ divided by factor-1

Попробуйте онлайн . Обратите внимание, что это тот же подход, что и в удивительно умном ответе CJam на Sp3000 .

Сохранено 5 байтов благодаря Денису!

TI-BASIC, 17 байтов * 0,8 = 13,6

Также использует метод Sp3000, хотя я нашел его независимо. Принимает один список из ввода и один из главного экрана.

Input E
prod(AnsAns^∟E-1)/prod(Ans-1

Использование prod (вдвое меньше, потому что позволяет бесплатно использовать круглые скобки. Обратите внимание, что этот ответ не поддерживает пустые массивы, поскольку в TI-BASIC нет пустых массивов.

Haskell, 38 * 0,8 = 30,4

product$zipWith(\p e->(p*p^e-1)/(p-1))

Использование:

product$zipWith(\p e->(p*p^e-1)/(p-1)) [2,3,5] [4,1,1]
744.0

Анонимная функция сводится (p,e)к сумме делителей для суммы p^eчерез геометрические ряды. Объединение двух списков с этим, так как соединение и получение продукта дает результат.

Я не смог найти ничего короче, чем арифметическое выражение

(p*p^e-1)/(p-1)
sum$map(p^)[0..e]

Может быть, есть способ избавиться от (\p e->_).

Определение инфиксной функции дает ту же длину (38):

p%e=(p*p^e-1)/(p-1)
product$zipWith(%)

C ++, 111 80 77 байт * 0,8 = 61,6

int g(int*p,int*e,int n){return n?g(p+1,e+1,n-1)*(pow(*p,*e-1)-1)/(*p-1):1;}

Это вычисляет (p ^ (e + 1) -1) / (p-1) и рекурсивно умножает все факторы. Узнал об этом сам год назад.

Спасибо за помощь, полностью забыл про использование логического стиля в c ++.

Матлаб, 53

function t=f(x,y)
s=1:prod(x.^y);t=s*~mod(s(end),s)';

Пример:

>> f([2 3 5], [4 1 1])
ans =
   744

Python 2,156

from itertools import*
from operator import*
i=input()
print sum(reduce(mul,[a**b for a,b in zip(i[0],p)])for p in product(*map(range,[x+1 for x in i[1]])))

вход

[[2,3,5],[4,1,1]]

Выход

744

объяснение

Эта программа получает список из 2 списков: факторы и показатели.

i=input() # Receive list of 2 lists: i[0] for factors i[1] for exponents

Затем создайте список всех возможных комбинаций списка экспонентов.

[x+1 for x in i[1]] # [4,1,1]->[5,2,2] (to include last element)
map(range,[x+1 for x in i[1]]) # [[0, 1, 2, 3, 4], [0, 1], [0, 1]]
product(*map(range,[x+1 for x in i[1]])) # [(0, 0, 0), (0, 0, 1), ..., (4, 1, 1)]

и застегните это с факторами:

zip(i[0],p) for p in product(*map(range,[x+1 for x in i[1]])) # [[(2, 0), (3, 0), (5, 0)], ..., [(2, 4), (3, 1), (5, 1)]]

Рассчитаем факторы на степень показателей:

 [a**b for a,b in zip(i[0],p)]for p in product(*map(range,[x+1 for x in i[1]])) # [[1, 1, 1], ..., [16, 3, 5]]

и умножим каждый список (это дает нам все делители):

reduce(mul,[a**b for a,b in zip(i[0],p)])for p in product(*map(range,[x+1 for x in i[1]])) # [1, 5, 3, 15, ..., 240]

Наконец, суммируйте все списки и напечатайте:

print sum(reduce(mul,[a**b for a,b in zip(i[0],p)])for p in product(*map(range,[x+1 for x in i[1]]))) # 744

Питон 3, 134 120 117

Ввод: два массива, разделенных запятыми.

Пример:

(2,3,7,11),(4,2,3,2)
21439600

from functools import*
a=eval(input())
print(reduce(int.__mul__,(sum(x**j for j in range(y+1))for x,y in zip(*a)),1))

С помощью NumPy можно уменьшить до 100 байт:

import numpy
a=eval(input())
print(numpy.product([sum(x**j for j in range(y+1))for x,y in zip(*a)]))

Желе, неконкурентоспособное

Этот ответ не конкурирует, так как задача предшествует созданию желе.

5 байт (без бонуса)

*PÆDS

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

Как это работает

*PÆDS    Main link. Left input: p (prime factors). Right input: e (exponents).

*        Elevate the prime factors to the corresponding exponents.
 P       Take the product of all powers.
  ÆD     Find all divisors of the product.
    S    Compute the sum of the divisors.

7 байт (5,6 байт после бонуса)

*‘}’:’{P

Как это работает

×*’:’{P  Main link. Left input: p (prime factors). Right input: e (exponents).

 *       Elevate the prime factors to the corresponding exponents.
         This yields p ** e.
×        Multiply the prime factors with the corresponding powers.
         This yields p ** (e + 1).
  ’      Decrement the resulting products.
         This yields p ** (e + 1) - 1.
    ’{   Decrement the prime factors.
         This yields p - 1.
   :     Divide the left result by the right one.
         This yields (p ** (e + 1) - 1) / (p - 1).
      P  Take the product of all quotients.

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

APL, 12 байтов * 0,8 = 9,6

×/1++/¨⎕*⍳¨⎕

Это читает два списка с клавиатуры, сначала экспоненты, то есть:

      ×/1++/¨⎕*⍳¨⎕
⎕:
      4 1 1
⎕:
      2 3 5
744

Объяснение:

• ⎕: прочитать список с клавиатуры (экспоненты)
• ⍳¨: для каждого номера в списке, создать список [1..n] .
• ⎕*: прочитать другой список с клавиатуры (простые числа) и поднять каждое простое число до каждого из показателей в соответствующих списках
• +/¨: суммировать каждый список
• 1+: добавьте один к каждому результату, чтобы компенсировать недостающие x^0 в каждом из списков
• ×/: взять произведение результатов

Ракетка (схема), 65 * 0,8 = 52 байта

Та же арифметика, что и у всех остальных

(λ(x y)(foldl(λ(m n o)(*(/(-(expt m(+ n 1))1)(- m 1))o))1 x y))

Объяснение:

(λ (x y)    ;defines anonymous function with two inputs
    (foldl    ;recursively applies the following function to all elements of the lists given to an argument given (foldl function argument lists lists lists...)
        (λ (m n o) (* (/ (- (expt m (+ n 1)) 1) (- m 1)) o))    ;an anonymous function representing the same arithmetic used in the CJam answer, then multiplying it with our incrementor
        1 x y))    ;the incrementor argument is 1, and the input lists are the ones provided into the original function

Python 2, 80 байт * 0,8 = 64

Это предполагает, что вход поступает один за другим. Следует той же формуле, которая описана в ответе CJam на Sp3000.

print(reduce(float.__mul__,[~-(x**-~y)/~-x for x,y in zip(input(),input())],1)) 

Если это не разрешено, тогда я буду использовать это как решение, которое получит оценку 84 байта * 0,8 = 67,2. Входные данные должны быть разделены запятой, то есть [2,3,5],[4,1,1].

k=input()
print(reduce(float.__mul__,[~-(x**-~y)/~-x for x,y in zip(k[0],k[1])],1))

^{Psst. Привет! Это возможное решение в Symbolic, над которым я работаю:Ƥ(П([~-(x**-~y)/~-xϝx,yϊʐ(Ί,Ί)],1))}

Mathematica, 40 байт

Total[Outer@@{*}~Join~(#^0~Range~#2),3]&

Без использования каких-либо встроенных функций, которые имеют дело с делителями, чтобы отличаться от других решений Mathematica в потоке.

Ввод (на примере) [{2, 3, 5}, {4, 1, 1}]

Perl 5, 96 байт

Очевидно, что это не выигрыш, но я решил написать это для удовольствия.

Это подпрограмма:

{($b,$e)=@_;$s=1;map$s*=$b->[$_]**$e->[$_],0..@$b-1;$_=1x$s;for$j(1..$s){$i+=$j*/^(.{$j})*$/}$i}

Посмотрите на это так:

perl -e'print sub{...}->([2,3,5],[4,1,1])'

Как это работает:

• ($b,$e)=@_читает входные массивыrefs $b(базисы) и $e(экспоненты).
• $s=1 инициализирует продукт.
• map$s*=$b->[$_]**$e->[$_],0..@$b-1умножается $sна последовательные базовые экспоненты. Теперь$s это составной номер.
• $_=1x$sустанавливает $_равным строке единиц, $slong. $iинициализируется в 0.
• for$j(1..$s){$i+=$j*/^(.{$j})*$/}пытается, для каждого числа $jот 1 $sдо, разбить $_, так как $jсимволы повторяются любое количество раз. Если это возможно, то $jделит $s, и /^(.{$j})*$/равен 1 (в противном случае это 0), и $iувеличивается на $j. Таким образом, мы добавляем к $iчислу разделов равного размера раздел $_. Как указывает Омар Э. Пол , $iэто число, которое мы ищем.
• $iв конце возвращается $i.

J 14 байтов * 0,8 = 11,2

[:*/(^>:)%&<:[

использование

   f =: [:*/(^>:)%&<:[
   2 3 5 f 4 1 1
744