Wprowadzenie

Każda liczba wymierna od 0 do 1 może być reprezentowana jako ewentualnie okresowa sekwencja bitów. Na przykład binarna reprezentacja 11/40 to

0.010 0011 0011 0011 ...

gdzie 0011część powtarza się w nieskończoność. Jednym ze sposobów znalezienia tej reprezentacji jest: Zacznij od r = 11/40 , a następnie kilkakrotnie podwoj go i weź ułamek, rejestrując, gdy przekroczy on 1. Gdy wartość r się powtarza, wiesz, że wszedłeś w pętlę.

1. r = 11/40
2. 2*r = 11/20 < 1   ->  next bit is 0, r = 11/20
3. 2*r = 11/10 >= 1  ->  next bit is 1, r = 2*r - 1 = 1/10
4. 2*r = 1/5 < 1     ->  next bit is 0, r = 1/5
5. 2*r = 2/5 < 1     ->  next bit is 0, r = 2/5
6. 2*r = 4/5 < 1     ->  next bit is 0, r = 4/5
7. 2*r = 8/5 >= 1    ->  next bit is 1, r = 2*r - 1 = 3/5
8. 2*r = 6/5 >= 1    ->  next bit is 1, r = 2*r - 1 = 1/5, same as in 4.
   The loop 5. -> 6. -> 7. -> 8. now repeats.

Aby wrócić z ciągu binarnego z powrotem do 11/40, możesz użyć formuły

(int(prefix) + int(suffix)/(2^len(suffix) - 1)) / 2^len(prefix)

gdzie prefixjest częścią początkową 010, suffixjest częścią powtarzającą się 0011i intkonwertuje ciąg binarny na liczbę całkowitą.

Biorąc pod uwagę dwie takie reprezentacje, możemy wykonać na nich bitową operację XOR. Wynikowa sekwencja będzie również okresowa, więc reprezentuje liczbę wymierną.

Dla niektórych liczb wymiernych istnieją dwie reprezentacje binarne.

1/4 = 0.010000000...
    = 0.001111111...

Wybór między nimi może wpływać na wynik bitowego XOR. W takich przypadkach używamy poprzedniej reprezentacji, która ma nieskończenie wiele zer.

Zadanie

Twoje dane wejściowe to dwie liczby wymierne w przedziale półotwartym [0,1). Twój wynik powinien być wynikiem bitowej operacji XOR zastosowanej do danych wejściowych, wyrażonej jako liczba wymierna. Zauważ, że wyjście może wynosić 1, mimo że żadne z wejść nie jest.

Dokładne formaty wejściowe i wyjściowe są elastyczne, a każda liczba wymierna powinna być reprezentowana przez dwie liczby całkowite, licznika i mianownika (z wyjątkiem wartości 0 i 1, który może być przedstawiony jak 0i 1w razie potrzeby). Możesz założyć, że dane wejściowe są wyrażone w najniższych kategoriach. Wynik musi być wyrażony w najniższych kategoriach. Wbudowany typ liczby wymiernej jest dopuszczalnym formatem, o ile spełnia te ograniczenia. Możesz zignorować wszelkie ograniczenia liczb całkowitych narzucone przez twój język, ale twój algorytm powinien teoretycznie działać dla wszystkich liczb wymiernych.

Wygrywa najniższa liczba bajtów. Obowiązują standardowe zasady gry w golfa .

Przykład

Rozważ wejścia 11/40 i 3/7. Piszemy ich reprezentacje jedna nad drugą, ograniczając powtarzające się części za pomocą potoków |. Następnie wyodrębniamy powtarzające się części o równej długości i nakładamy bitową XOR na nich i na części przed nimi.

11/40 = 0. 0 1 0|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 ...
3/7   = 0.|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|...
     -> 0. 0 0 1|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 ...

Wynikowa liczba wymierna to 89/520.

Przypadki testowe

0 0 -> 0
1/2 1/2 -> 0
1/2 1/4 -> 3/4
1/3 2/3 -> 1
1/2 3/4 -> 1/4
5/8 1/3 -> 23/24
1/3 1/5 -> 2/5
15/16 3/19 -> 257/304
15/16 257/304 -> 3/19
3/7 11/40 -> 89/520
5/32 17/24 -> 59/96
16/29 16/39 -> 621001733121535520/696556744961512799

Python 3, 193 164 bajtów

def x(a,b,z=0):
 l=[]
 while(a,b)not in l:l+=[(a,b)];z=2*z|(a<.5)^(b<.5);a=a*2%1;b=b*2%1
 p=l.index((a,b));P=len(l)-p
 return((z>>P)+z%2**P*a**0/~-2**(P or 1))/2**p

Pobiera dane wejściowe jako fractions.Fractiontyp Pythona 3 i również je wyprowadza.

Ciekawostka (możesz to łatwo pokazać za pomocą funkcji generujących), jeśli zmienisz (a<.5)^(b<.5)na ((a>=.5)and(b>=.5))powyższy, otrzymasz wartość binarną ORAZ między dwiema wymiernymi liczbami. Nazwać nd(a, b). Więc mamy a + b - 2*nd(a, b) = x(a, b)!

JavaScript, 141 bajtów

(p,q,r,s)=>(h=(v,u)=>v%u?h(u,v%u):[a/u,b/u])(b=(g=x=>x%q||x%s?g((x|x/2)+x%2):x)(1),a=(o=b/(b-(b&~-b)),x=p*b/q,y=r*b/s,(x%o^y%o)+(x/o^y/o)*o))

Nie zadziała dla ostatniego przypadku testowego (przepełnienie liczb całkowitych). Wprowadź 4 liczby p/q xor r/s, wyślij tablicę z dwiema liczbami. W przypadku testu 0, 0powinieneś wpisać 0, 1, 0, 1.

W jaki sposób:

(Wszystkie liczby tutaj opisane są w formie binarnej.)

1. znajdź najmniejszą liczbę b, która b = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s);
2. Pozwól x = p * b / q, y = r * b / q; Konwersja p / q, r / saby x / bi y / b;
3. Niech o = 10 ^ (p - q) - 1; Podział x, ydo [x % o, x / o], [y % o, y / o]; uzyskaj xor dla każdej części [x % o xor y % o, x / o xor y / o]i dołącz ponownie (x % o xor y % o) + (x / o xor y / o) * o; Podaruj to jako a;
4. Jeśli a = 0odpowiedź brzmi 0(lub 0 / 1); W przeciwnym razie pozwól u = gcd(a, b); odpowiedź brzmi (a/u)i (b/u).

f=

(p,q,r,s)=>(h=(v,u)=>u%v?h(u%v,v):[a/v,b/v])(b=(g=x=>x%q||x%s?g((x|x/2)+x%2):x)(1),a=(o=b/(b-(b&~-b)),x=p*b/q,y=r*b/s,(x%o^y%o)+(x/o^y/o)*o))

<div oninput="[v5.value,v6.value]=['?','?'];[v5.value,v6.value]=f(+v1.value,+v2.value,+v3.value,+v4.value)">
<input id=v1 />/<input id=v2 /> xor <input id=v3 />/<input id=v4 /> = <output id=v5></output> / <output id=v6></output>
<style>input{width:40px}</style>
</div>