Znajdź iloczyn skalarny produktu Rationals

31

Byłem w domu przyjaciela na obiedzie, a oni zasugerowali pomysł na „przestrzeń wektorową czynnika pierwszego”. W tej przestrzeni dodatnie liczby całkowite są wyrażane jako wektor w taki sposób, że n- ty element w wektorze jest liczbą razy, gdy n- ta liczba pierwsza dzieli liczbę. (Zauważ, że oznacza to, że nasze wektory mają nieskończoną liczbę terminów.) Na przykład 20 to

2 0 1 0 0 0 ...

Ponieważ jego pierwsza faktoryzacja wynosi 2 * 2 * 5 .

Ponieważ pierwsza faktoryzacja jest unikalna, każda liczba odpowiada jednemu wektorowi.

Możemy dodawać wektory, dodając ich pary. Jest to to samo, co pomnożenie liczb, z którymi są skojarzone. Możemy również dokonywać mnożenia skalarnego, co jest podobne do podnoszenia powiązanej liczby do potęgi.

Problem polega na tym, że ta przestrzeń nie jest w rzeczywistości przestrzenią wektorową, ponieważ nie ma odwrotności. Jeśli pójdziemy dalej i dodamy odwrotności i zamkniemy przestrzeń wektorową, możemy teraz wyrazić każdą dodatnią liczbę wymierną jako wektor. Jeśli utrzymamy fakt, że dodawanie wektora reprezentuje mnożenie. Zatem odwrotność liczby naturalnej jest odwrotnością.

Na przykład liczba 20 miała wektor

2 0 1 0 0 0 ...

Tak więc ułamek 1/20 jest odwrotny

-2 0 -1 0 0 0 ...

Gdybyśmy chcieli znaleźć wektor związany z ułamkiem takim jak 14/15 , znaleźlibyśmy 14

1 0 0 1 0 0 ...

i 1/15

0 -1 -1 0 0 0 ...

i pomnóż je przez dodanie wektora

1 -1 -1 1 0 0 ...

Teraz, gdy mamy przestrzeń wektorową, możemy ją zmodyfikować, aby utworzyć wewnętrzną przestrzeń produktu, nadając jej wewnętrzny produkt. Aby to zrobić, kradniemy wewnętrzny produkt, który klasycznie podaje przestrzenie wektorowe. Iloczyn wewnętrzny dwóch wektorów jest definiowany jako suma mnożenia parami ich terminów. Na przykład 20,14/15 można obliczyć w następujący sposób

20    =  2  0  1  0  0  0 ...
14/15 =  1 -1 -1  1  0  0 ...
         2  0 -1  0  0  0 ...  -> 1

Jako kolejny przykład produkt 2/19 · 4/19

2/19 = 1 0 0 0 0 0 0 -1 0 0 0 ...
4/19 = 2 0 0 0 0 0 0 -1 0 0 0 ...
       2 0 0 0 0 0 0  1 0 0 0 ... -> 3

Twoim zadaniem jest wdrożenie programu, który wykonuje ten produkt kropkowy. Powinien przyjmować dwie dodatnie liczby wymierne za pośrednictwem pary dodatnich liczb całkowitych (licznik i mianownik) lub typu wymiernego (liczby zmiennoprzecinkowe są niedozwolone, ponieważ powodują problemy z precyzją i podzielnością) i powinien wypisywać liczbę całkowitą reprezentującą iloczyn iloczynu dwóch wejścia.

To jest więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

4 · 4 = 4
8 · 8 = 9
10 · 10 = 2
12 · 12 = 5
4 · 1/4 = -4
20 · 14/15 = 1
2/19 · 4/19 = 3
Kreator pszenicy
źródło
Wektor nie ma wymiaru, podobnie jak przestrzeń wektora.
Jonathan Frech
5
@JathanathanFrech Myślę, że to trochę pedantyczne, ale dokonałem zmiany.
Kreator pszenicy
„Liczby naturalne” są ogólnie rozumiane jako zawierające 0, które nie są reprezentowane w twoim systemie. I to nie są wektory. Przestrzeń wektorowa znajduje się nad polem, a to ponad pierścieniem, co uczyniłoby z niego moduł. I nie jest to oddzielna spacja od liczb całkowitych, to ta sama przestrzeń z inną reprezentacją.
Kumulacja
6
@Kumulacja „Liczby naturalne” nie są dobrze zdefiniowanym terminem, w zależności od tego, o kogo zapytasz, może, ale nie musi, zawierać zero. Masz rację, że „mnożenie skalarne” w moim pytaniu tworzy zestaw G z monoidą, a nie grupą, ale zostało to uproszczone w celu uczynienia pytania przyjemnym. Nie jestem pewien, co sądzić o twoim ostatnim komentarzu, na pewno ma on taką samą liczność jak liczby całkowite, ale tak naprawdę akcja definiuje przestrzeń, a nie jej rozmiar. Być może masz na myśli coś bardziej szczegółowego, czego mi brakuje. Jeśli tak, chętnie będę kontynuować tę dyskusję (najlepiej na czacie).
Kreator pszenicy
2
Inna terminologia nit-pick: przestrzenie wektorowe są na ogół wymagane, aby mnożyć skalarnie z pola, więc samo użycie liczb całkowitych nie wystarczy. To dlatego, że chcemy, aby wektory równoległe były wielokrotnościami, a nie tylko wspólną wspólną. Na przykład 4 $ i 8 $ są równoległymi „wektorami” w tej przestrzeni (oba mają postać (a, 0, 0, ...)), ale żaden z nich nie jest wielokrotnością skalarną (tj. Potęgą całkowitą) inny. Jednak nie ma tak naprawdę wielu innych terminów, których można by użyć, które byłyby ogólnie znane ludziom. „Darmowy moduł ponad liczbami całkowitymi” jest najlepszym, co mogę zrobić.
Arthur

Odpowiedzi:

4

MATL , 12 bajtów

YF2:&Y)dwd*s

Dane wejściowe to tablica [num1 den1 num2 den2].

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Rozważ przykładowe dane wejściowe [20 1 14 15].

YF      % Implicit input: array of 4 numbers. Exponents of prime factorization.
        % Gives a matrix, where each row corresponds to one of the numbers in
        % the input array. Each row may contain zeros for non-present factors
        % STACK: [2 0 1 0
                  0 0 0 0
                  1 0 0 1
                  0 1 1 0]
2:&Y)   % Push a submatrix with the first two rows, then a submatrix with the
        % other two rows
        % STACK: [2 0 1 0
                  0 0 0 0],
                 [1 0 0 1
                  0 1 1 0]
d       % Consecutive difference(s) along each column
        % STACK: [2 0 1 0
                  0 0 0 0],
                 [-1 1 -1 1]
wd      % Swap, and do the same for the other submatrix
        % STACK: [-1 1 -1 1]
                 [-2 0 -1 0]
*       % Element-wise product
        % STACK: [2 0 -1 0]
s       % Sum. Implicit display
        % STACK: 1
Luis Mendo
źródło
4

C (gcc) , 99 + 32 = 131 bajtów

  • Korzystanie z flagi kompilatora wymaga 32 bajtów -D=F(v,V,e)for(;v%p<1;V+=e)v/=p;.
T,p,A,C;f(a,b,c,d){T=0;for(p=2;a+b+c+d>4;p++){A=C=0;F(a,A,1)F(b,A,~0)F(c,C,1)F(d,C,~0)T+=A*C;}a=T;}

Wypróbuj online!

Jonathan Frech
źródło
Myślę, że lepiej jest wyraźnie określić, że -D=F(v,V,e)for(;v%p<1;V+=e)v/=p;używana jest dodatkowa flaga (32 bajty) (więc 99 + 32 = 131); w przeciwnym razie sam kod nie ma większego sensu.
Bubbler
3

Python 2 , 110 bajtów

l=input()
p=t=2
while~-max(l):r=i=0;exec"while l[i]%p<1:l[i]/=p;r+=1j**i\ni+=1\n"*4;t+=r*r;p+=1
print t.imag/2

Wypróbuj online!

Przyjmuje dane wejściowe jak [num1, num2, den1, den2]. Używa liczby zespolonej rdo przechowywania wpisów liczb pierwszych pdla dwóch uzasadnień i (r*r).imag/2do wyodrębnienia ich produktu r.real*r.imagw ramach sumy t. Dodanie 1j**idla i=0,1,2,3powoduje wykonanie każdej kombinacji zwiększania lub zmniejszania części rzeczywistej lub urojonej dla czterech liczb wejściowych.

Bubbler zapisał 2 bajty łączące wartości początkowe p=t=2.

xnor
źródło
1
p=t=2zamiast p=2;t=0ponieważ t.realjest ignorowane mimo to ( TIO ).
Bubbler
@Bubbler Nicea, dodawanie!
xnor
1

JavaScript (Node.js) , 104 ... 100 94 bajtów

F=(A,i=2)=>A.some(x=>x>1)&&([a,b,c,d]=A.map(G=(x,j)=>x%i?0:1+G(A[j]/=i,j)),a-b)*(c-d)+F(A,i+1)

Wypróbuj online!

Przekaż liczby jako tablicę [Num1, Den1, Num2, Den2].

Dzięki za Arnauld za naprawienie brakujących F=bez dodatkowych bajtów i 2 kolejnych bajtów mniej.

Wyjaśnienie i nie golfista

function F(A, i = 2) {                 // Main function, recursing from i = 2
 if (A.some(function(x) {              // If not all numbers became 1:
  return x > 1;
 })) {
  var B = A.map(G = function(x, j) {   // A recursion to calculate the multiplicity
   if (x % i)
    return 0;
   else
    return 1 + G(A[j] /= i, j);        // ...and strip off all powers of i
  });
  return (B[0] - B[1]) * (B[2] - B[3]) // Product at i
   + F(A, i + 1);                      // Proceed to next factor. All composite factors 
 }                                     // will be skipped effectively
 else 
  return 0;                            // Implied in the short-circuit &&
}
Shieru Asakoto
źródło
1

J , 19 bajtów

1#.*/@,:&([:-/_&q:)

Wypróbuj online!

Wyjaśnienie:

Czasownik dynamiczny, argumenty znajdują się zarówno po lewej, jak i po prawej stronie

         &(        ) - for both arguments (which are lists of 2 integers)
               _&q:  - decompose each number to a list of prime exponents
           [:-/      - and find the difference of these lists
       ,:            - laminate the resulting lists for both args (to have the same length)
   */@               - multiply them
1#.                  - add up 
Galen Iwanow
źródło
1

Stax , 11 bajtów

ä÷ß½♂←√:=Ü]

Uruchom i debuguj

Odpowiada to reprezentacji ascii tego samego programu.

{|nmMFE-~-,*+

Zasadniczo pobiera wykładniki pierwszej faktoryzacji dla każdej części. Pobiera różnicę dla każdej pary, następnie produktu, i na koniec sumuje wszystkie wyniki.

rekurencyjny
źródło
1

Python 2 , 133 127 bajtów

a=input();s=0;p=2;P=lambda n,i=0:n%p and(n,i)or P(n/p,i+1)
while~-max(a):a,(w,x,y,z)=zip(*map(P,a));s+=(w-x)*(y-z);p+=1
print s

Wypróbuj online!

Ukradnij warunek pętli od złożenia xnora .

Dzięki za radę @mathmandan, aby zmienić funkcję w program (tak, rzeczywiście zaoszczędził kilka bajtów).

Przestarzałe, nieprawidłowe rozwiązanie (124 bajty):

lambda w,x,y,z:sum((P(w,p)-P(x,p))*(P(y,p)-P(z,p))for p in[2]+range(3,w+x+y+z,2))
P=lambda n,p,i=1:n%p and i or P(n/p,p,i+1)
Bubbler
źródło
Czy nie pzamierza testować wartości innych niż pierwotne, takich jak 9?
xnor
Ups, naprawię to wkrótce.
Bubbler
3
Można wymienić returnz print, można również zapisać spacje wcięć jeśli piszesz jako program zamiast funkcji.
matmandan
@mathmandan Dzięki za informację. Wygląda na użyteczne w przypadku moich innych zgłoszeń Py2, ale nie jestem pewien co do Py3 (zajmuje to więcej, eval()chyba że dane wejściowe funkcji są ciągiem).
Bubbler
1

Haskell , 153 bajty

(2%)
n%m|all(<2)m=0|(k,[a,b,c,d])<-unzip[(,)=<<div x.max 1.(n*)$until((>0).mod x.(n^))(+1)1-1|x<-m]=(a-b)*(c-d)+[i|i<-[n..],all((>0).rem i)[2..i-1]]!!1%k

Wypróbuj online! Przykładowe zastosowania dla 20 · 14/15: (2%) [20,1,14,15].

Laikoni
źródło