Zadanie polega na obliczeniu sumy dzielnika liczby, biorąc pod uwagę jej pierwszą faktoryzację.

Wejście

Dwie tablice (lub coś równoważnego) o długości n , jedna zawiera współczynnik pierwszy, a druga zawiera odpowiedni wykładnik.

Wynik

Suma wszystkich dzielników (w tym sama liczba).

Przykład

Liczba 240 ma 2, 3 i 5 jako czynniki pierwsze z 4, 1 i 1 jako odpowiednie wykładniki. Oczekiwany wynik wyniósłby wtedy 744.

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

Punktacja

Najkrótszy kod w bajtach wygrywa!

Jeśli złożoność czasu wykonania rozwiązania wynosi O (suma wykładników), a nie O (iloczyn wykładników), twój wynik można pomnożyć przez 0,8.

Było podobne pytanie zamieszczone tutaj, ale nie było to wyzwanie. Myślę, że problem jest wystarczająco interesujący, aby grać w golfa.

Zwycięzca zostanie wybrany w ten weekend

Pyth, 13 bajtów * 0,8 = 10,4

*Fms^LhdhedCQ

Demonstracja.

Ta odpowiedź działa nieco inaczej niż powyższe. Aby obliczyć sumę czynników liczb pierwszych potęg liczbowych, zamiast używać wzoru arytmetycznego, czynniki są ściśle konstruowane i sumowane.

Na przykład, na ekranie [prime, wykładnik] parą [2, 4], mamy map 2 ^ xponad 0, 1, 2, 3, 4, dając [1, 2, 4, 8, 16], który następnie sumuje się do 31.

Wyniki są następnie mnożone i drukowane.

Jeśli potęgowanie jest zaimplementowane poprawnie lub jeśli istnieje buforowanie wyników pośrednich, tak będzie O(sum of exponents).

CJam, 15 bajtów * 0,8 = 12

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

Wypróbuj online . Kolejność wprowadzania to najpierw lista wykładników, a następnie lista liczb pierwszych (-3 bajty dzięki @Dennis) .

Dla każdej pary prime-wykładnik (p, e)znalezisku

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

następnie znajdź produkt wszystkich z nich. Na przykład dla 240

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

W zależności od implementacji potęgowania może to być lepsze niż O(sum of exponents).

APL, 18 13 bajtów * 0,8 = 10,4

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

To tworzy ciąg funkcji dynamicznych, który bierze wachlarz czynników po lewej stronie i wykładniki po prawej.

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

Wypróbuj online . Zauważ, że jest to to samo podejście, co niesamowicie sprytna odpowiedź CJam Sp3000 .

Zaoszczędź 5 bajtów dzięki Dennisowi!

TI-BASIC, 17 bajtów * 0,8 = 13,6

Używa również metody Sp3000, chociaż znalazłem ją niezależnie. Pobiera jedną listę z wejścia i jedną z ekranu głównego.

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

Użycie prod (dwukrotnie jest mniejsze, ponieważ pozwala nam korzystać z otwartego nawiasu za darmo. Zauważ, że ta odpowiedź nie obsługuje pustych tablic, ponieważ w TI-BASIC nie ma pustych tablic.

Haskell, 38 * 0,8 = 30,4

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

Stosowanie:

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

Funkcja anonimowa przyjmuje (p,e)sumę dzielnika dlap^e sumy szeregów geometrycznych. Zebranie razem dwóch list w ten sposób podczas łączenia i odbierania produktu daje wynik.

Nie byłem w stanie znaleźć niczego krótszego niż wyrażenie arytmetyczne

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

Może jest sposób na pozbycie się (\p e->_) .

Definicja funkcji Infix daje tę samą długość (38):

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

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

To oblicza (p ^ (e + 1) -1) / (p-1) i rekurencyjnie mnoży wszystkie czynniki. Przekonałem się o tym rok temu.

Dziękujemy za pomoc, całkowicie zapomnieliśmy o użyciu wartości logicznej w stylu c ++.

Matlab, 53

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

Przykład:

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

Wejście

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

Wynik

744

Wyjaśnienie

Ten program otrzymuje listę 2 list: czynników i wykładników.

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

Następnie utwórz listę wszystkich możliwych kombinacji listy wykładników.

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

i spakuj go z uwzględnieniem czynników:

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

Oblicz współczynniki potęgi wykładników:

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

i pomnóż każdą listę (daje to nam wszystkie dzielniki):

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]

Na koniec zsumuj wszystkie listy i wydrukuj:

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

Dane wejściowe: dwie tablice rozdzielone przecinkami oddzielone przecinkami.

Przykład:

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

Z NumPy można zmniejszyć do 100 bajtów:

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

Galaretka, niekonkurująca

Ta odpowiedź nie jest konkurencyjna, ponieważ wyzwanie poprzedza powstanie galaretki.

5 bajtów (bez premii)

*PÆDS

Wypróbuj online!

Jak to działa

*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 bajtów (5,6 bajtu po premii)

*‘}’:’{P

Jak to działa

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

Wypróbuj online!

APL, 12 bajtów * 0,8 = 9,6

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

Odczytuje dwie listy z klawiatury, wykładniki jako pierwsze, tj .:

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

Wyjaśnienie:

• ⎕: przeczytaj listę z klawiatury (wykładniki)
• ⍳¨: dla każdego numeru na liście wygeneruj listę [1..n].
• ⎕*: przeczytaj inną listę z klawiatury (liczby pierwsze) i podnieś każdą liczbę pierwszą do każdego z wykładników na odpowiednich listach
• +/¨: zsumuj każdą listę
• 1+: dodaj po jednym do każdego wyniku, aby zrekompensować brak x^0na każdej liście
• ×/: weź iloczyn wyników

Rakieta (schemat), 65 * 0,8 = 52 bajty

Ta sama arytmetyka jak wszyscy inni

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

Wyjaśnienie:

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

Zakłada się, że dane wejściowe przychodzą jedna po drugiej. Stosuje tę samą formułę, która została opisana w odpowiedzi CJam Sp3000.

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

Jeśli nie jest to dozwolone, użyję tego jako rozwiązania, które uzyska wynik 84 bajtów * 0,8 = 67,2. Dane wejściowe należy oddzielić przecinkiem, tj [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. Hej! Jest to możliwe rozwiązanie w Symbolic, nad czym pracuję:Ƥ(П([~-(x**-~y)/~-xϝx,yϊʐ(Ί,Ί)],1))}

Mathematica, 40 bajtów

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

Bez użycia żadnego z wbudowanych rozwiązań, które dotyczą dzielników, aby odróżnić się od innych rozwiązań matematycznych w wątku.

Dane wejściowe to (na przykładzie) [{2, 3, 5}, {4, 1, 1}]

Perl 5, 96 bajtów

Oczywiście nie jest to wygrana, ale postanowiłem napisać to dla zabawy.

To podprogram:

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

Zobacz to w akcji:

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

Jak to działa:

• ($b,$e)=@_odczytuje dane wejściowe arrayrefs $b(podstawy) i$e (wykładniki).
• $s=1 inicjuje produkt.
• map$s*=$b->[$_]**$e->[$_],0..@$b-1mnoży $sprzez kolejne potęgi wykładnika podstawowego. Teraz $sjest liczba złożona.
• $_=1x$szestawy $_równe ciągowi jednych, $sdługich. $ijest inicjowany na 0.
• for$j(1..$s){$i+=$j*/^(.{$j})*$/}próbuje, dla każdej liczby $jod 1 $sdo, rozbić $_się, gdy $jznaki powtarzają się dowolną liczbę razy. Jeśli może, $jdzieli się $si /^(.{$j})*$/ma wartość 1 (w przeciwnym razie wynosi 0) i $ijest powiększany o $j. W ten sposób dodajemy do $iliczby partycji w równej wielkości partycji $_. Jak wskazuje Omar E. Pol , $ito liczba, której szukamy.
• $ina koniec wraca $i.

J, 14 bajtów * 0,8 = 11,2

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

Stosowanie

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