A tarefa é calcular a soma divisória de um número, dada sua fatoração primária.

Entrada

Duas matrizes (ou algo equivalente) de comprimento n , uma contendo o fator primo e a outra contendo o expoente correspondente.

Resultado

A soma de todos os divisores (incluindo o próprio número).

Exemplo

O número 240 tem 2, 3 e 5 como fatores primos, com 4, 1 e 1 como os respectivos expoentes. A saída esperada seria então 744.

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

Pontuação

O menor código em bytes vence!

Se a complexidade do tempo de execução da sua solução for O (soma dos expoentes) em vez de O (produto dos expoentes), sua pontuação poderá ser multiplicada por 0,8.

Havia uma pergunta semelhante postada aqui, mas não era um desafio. Eu acho que o problema é interessante o suficiente para ser jogado.

O vencedor será escolhido neste fim de semana

Pitão, 13 bytes * 0,8 = 10,4

*Fms^LhdhedCQ

Demonstração.

Essa resposta funciona de maneira um pouco diferente das anteriores. Para calcular a soma dos fatores das potências primárias do número, em vez de usar uma fórmula aritmética, os fatores são explicitamente construídos e somados.

Por exemplo, no par [nobre, expoente] [2, 4], mapeamos 2 ^ xmais 0, 1, 2, 3, 4, dando [1, 2, 4, 8, 16], que é então resumido a 31.

Os resultados são então multiplicados e impressos.

Se a exponenciação for implementada corretamente, ou se houver um cache intermediário de resultados, será O(sum of exponents).

CJam, 15 bytes * 0,8 = 12

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

Experimente online . A ordem de entrada é a lista de expoentes primeiro e depois a lista de números primos (-3 bytes graças a @Dennis) .

Para cada par expoente primo (p, e)encontre

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

então encontre o produto de tudo isso. Por exemplo, para 240 isso seria

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

Dependendo de como a exponenciação é implementada, isso pode ser melhor que O(sum of exponents).

APL, 18 13 bytes * 0,8 = 10,4

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

Isso cria um trem de funções diádico que pega a matriz de fatores à esquerda e os expoentes à direita.

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

Experimente online . Observe que esta é a mesma abordagem que a resposta CJam incrivelmente inteligente do Sp3000 .

Economizou 5 bytes graças a Dennis!

TI-BASIC, 17 bytes * 0,8 = 13,6

Também usa o método do Sp3000, embora eu o tenha encontrado de forma independente. Leva uma lista da entrada e uma da tela inicial.

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

Utilizar prod (duas vezes é menor porque nos permite usar os parênteses abertos gratuitamente. Observe que esta resposta não suporta matrizes vazias, porque não existem matrizes vazias no TI-BASIC.

Haskell, 38 * 0,8 = 30,4

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

Uso:

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

A função anônima leva (p,e)à soma do divisor para a soma de p^eséries geométricas. Fechando as duas listas com isso, a união e a retirada do produto dão o resultado.

Não consegui encontrar nada mais curto que a expressão aritmética

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

Talvez haja uma maneira de se livrar do (\p e->_).

A definição da função infix fornece o mesmo comprimento (38):

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

C ++, 111 80 77 bytes * 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;}

Isso calcula (p ^ (e + 1) -1) / (p-1) e multiplica recursivamente todos os fatores. Descobri isso sozinho há um ano.

Obrigado por ajudar, esqueci totalmente o uso booleano do estilo c ++.

Matlab, 53

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

Exemplo:

>> 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]])))

Entrada

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

Resultado

744

Explicação

Este programa recebe uma lista de 2 listas: fatores e expoentes.

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

Em seguida, é criada uma lista de todas as combinações possíveis da lista de expoentes.

[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)]

e zip com os fatores:

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)]]

Calcule os fatores para a potência dos expoentes:

 [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]]

e multiplique cada lista (isso nos dá todos os divisores):

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]

Por fim, some todas as listas e imprima:

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

Python 3, 134 120 117

Entrada: duas matrizes separadas por vírgula, separadas por vírgula.

Exemplo:

(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))

Com NumPy pode ser reduzido para 100 bytes:

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

Gelatina, não concorrente

Essa resposta não é competitiva, pois o desafio antecede a criação do Jelly.

5 bytes (sem bônus)

*PÆDS

Experimente online!

Como funciona

*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 bytes (5,6 bytes após bônus)

*‘}’:’{P

Como funciona

×*’:’{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.

Experimente online!

APL, 12 bytes * 0,8 = 9,6

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

Isso lê duas listas do teclado, primeiro os expoentes, ou seja:

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

Explicação:

• ⎕: lê uma lista do teclado (os expoentes)
• ⍳¨: para cada número na lista, gere uma lista [1..n].
• ⎕*: leia outra lista do teclado (os números primos) e aumente cada número primo para cada um dos expoentes nas listas correspondentes
• +/¨: soma cada lista
• 1+: adicione um a cada resultado, para compensar a falta x^0em cada uma das listas
• ×/: pegue o produto dos resultados

Raquete (esquema), 65 * 0,8 = 52 bytes

A mesma aritmética que todos os outros

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

Explicação:

(λ (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 bytes * 0,8 = 64

Isso pressupõe que a entrada seja recebida uma após a outra. Segue a mesma fórmula descrita na resposta CJam do Sp3000.

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

Se isso não for permitido, usarei isso como uma solução, que obtém uma pontuação de 84 bytes * 0,8 = 67,2. A entrada deve ser separada por vírgula, ie [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. Ei! Esta é uma solução possível no Symbolic, algo em que estou trabalhando:Ƥ(П([~-(x**-~y)/~-xϝx,yϊʐ(Ί,Ί)],1))}

Mathematica, 40 bytes

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

Sem usar nenhum dos inbuilts que lidam com divisores, para diferenciar da outra solução mathematica no encadeamento.

Entrada é (usando o exemplo) [{2, 3, 5}, {4, 1, 1}]

Perl 5, 96 bytes

Obviamente, isso não é vencedor, mas eu decidi escrever por diversão.

É uma sub-rotina:

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

Veja-o em ação assim:

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

Como funciona:

• ($b,$e)=@_lê a matriz de entrada refs $b(bases) e $e(expoentes).
• $s=1 inicializa o produto.
• map$s*=$b->[$_]**$e->[$_],0..@$b-1multiplica $spor sucessivos poderes de expoente base. Agora $sé o número composto.
• $_=1x$sconjuntos $_iguais a uma sequência de unidades, $slonga. $ié inicializado em 0.
• for$j(1..$s){$i+=$j*/^(.{$j})*$/}tenta, para cada número $jentre 1 e $s, terminar $_como $jcaracteres repetidos várias vezes. Se puder, $jdivide $se /^(.{$j})*$/é 1 (caso contrário, é 0) e $ié aumentado por $j. Assim, adicionamos ao $inúmero de partições em uma partição de tamanho igual a $_. Como Omar E. Pol aponta , $ié o número que estamos procurando.
• $ino final retorna $i.

J, 14 bytes * 0,8 = 11,2

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

Uso

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