Oblicz normę p-adyczną liczby wymiernej
Napisz funkcję lub program, który pobiera 3 liczby całkowite m,n,p
(gdzie liczba p
dodatnia jest liczbą pierwszą) jako dane wyjściowe, które generują normę p-adyczną (oznaczoną |m/n|_p
jako) jako ułamek (całkowicie zredukowany). Fermat jest znany z bardzo małych marginesów, ale raczej nie wiadomo, że miał tylko bardzo mały ekran komputera. Dlatego staraj się, aby kod był jak najkrótszy, aby zmieścił się na ekranie Fermata!
Definicja
Biorąc pod uwagę p
liczbę pierwszą , każdą część m/n
można jednoznacznie zapisać (ignorując znaki) jako (a/b)* p^e
taką, która e
jest liczbą całkowitą i p
nie dzieli ani a
ani b
. Normą p adyczne na m/n
to p^-e
. Jest to szczególny przypadek, gdy frakcja jest 0: |0|_p = 0
.
Format wyjściowy musi być x/y
(np. 1/3
Dla liczb całkowitych dozwolone są oba 10
lub równoważnie 10/1
, dla liczb ujemnych musi być wiodący minus np. -1/3
)
Detale
Program musi używać stdin / stdout lub po prostu składać się z funkcji, która zwraca liczbę wymierną lub łańcuch. Musisz założyć, że dane wejściowe m/n
nie są w pełni zmniejszone. Możesz założyć, że p
jest to liczba pierwsza. Program musi być zdolny do przetwarzania liczb całkowitych od -2^28
do 2^28
, i nie powinien zająć więcej niż 10 sekund.
Wbudowane funkcje faktoryzacji i sprawdzania liczb pierwszych nie są dozwolone, podobnie jak wbudowane konwersacje bazowe i wbudowane funkcje, które obliczają wartość p-adyczną lub normę.
Przykłady (skradzione z wikipedii ):
x = m/n = 63/550 = 2^-1 * 3^2 * 5^-2 * 7 * 11^-1
|x|_2 = 2
|x|_3 = 1/9
|x|_5 = 25
|x|_7 = 1/7
|x|_11 = 11
|x|_13 = 1
Ciekawe ciekawostki
(Nie trzeba znać / czytać tego wyzwania, ale być może warto je czytać jako motywację).
(Proszę poprawić mnie, jeśli użyję niewłaściwych słów lub coś innego jest nie tak, nie jestem przyzwyczajony do mówienia o tym po angielsku.)
Jeśli weźmiesz pod uwagę liczby wymierne jako pole, wówczas norma p-adyczna indukuje metrykę p-adyczną d_p(a,b) = |a-b|_p
. Następnie możesz wypełnić to pole w odniesieniu do tej metryki, co oznacza, że możesz zbudować nowe pole, w którym zbiegają się wszystkie sekwencje cauchy, co jest przyjemną właściwością topologiczną. (Które np. Liczby wymierne nie mają, ale liczby rzeczywiste tak.) Te liczby p-adyczne są, jak można się domyślać, używane w teorii liczb.
Innym interesującym wynikiem jest twierdzenie Ostrowskiego, które w zasadzie mówi, że dowolna wartość bezwzględna (jak zdefiniowano poniżej) liczb wymiernych jest jedną z następujących trzech:
- Trywialne:
|x|=0 iff x=0, |x|=1 otherwise
- Standard (rzeczywisty):
|x| = x if x>=0, |x| = -x if x<0
- P-adic (jak to zdefiniowaliśmy).
Wartość bezwzględna / metryka jest po prostu uogólnieniem tego, co uważamy za odległość . Wartość bezwzględna |.|
spełnia następujące warunki:
|x| >= 0 and |x|=0 if x=0
|xy| = |x| |y|
|x+y| <= |x|+|y|
Zauważ, że możesz łatwo konstruować metryki z wartości bezwzględnych i odwrotnie: |x| := d(0,x)
lub d(x,y) := |x-y|
, więc są one prawie takie same, jeśli możesz dodać / odjąć / pomnożyć (to jest w domenach integralnych). Możesz oczywiście zdefiniować metrykę na bardziej ogólnych zestawach, bez tej struktury.
PadicNorm
funkcja Mathematiki również jest wyłączona? : P|x|_11 = 11
, prawda? Czy jest w11
porządku? I czy to musi obsłużyćx=0
sprawę?x=0
sprawę i na tym przykładzie można wyjściowy11
, a także11/1
, ale nie trzeba drukować|x|_11
.Odpowiedzi:
Julia,
948075 bajtówUwaga: użycie linii odniesienia zamiast średników dla zwiększenia czytelności - będzie działać tak samo.
Jest to dość proste -
g(m,n)
funkcja korzysta z rekurencji i reszty (%
) w celu wyodrębnieniap^n
współczynnika z danych wejściowychm
, przyn=1
czym domyślnie, a następnie pomnożona przezp
na każdym etapie rekurencji, tak aby wynik byłp^n
. Kod stosuje to don/gcd(m,n)
, a następniem/gcd(m,n)
do uzyskania odpowiedniego wyrażenia.k=gcd(m,n)
służy do unikaniagcd(m,n)
podwójnego obliczania , do zapisywania znaków.m!=0
jest testem do obsługi przypadku, w którymx=0
.Dane wyjściowe mają postać
N/1
lub,1/N
w stosownych przypadkach, gdzieN
jestp^e
.źródło
J,
3534 bajtówJest to czasownik binarny, który przyjmuje
p
liczbę pierwszą za swój lewy argument, a tablicęm n
za swój prawy argument. Zawsze drukuje ukośnik/
i zwraca0/1
ifm = 0
. Użyj tego w ten sposób:Wyjaśnienie
W
x:
zakręty na rozszerzonej precyzji, ponieważ mamy do przenoszenia bardzo dużych ilościach. Reszta kodu działa w następujący sposób:źródło
CJam, 42 bajty
To kończy się błędem (po wydrukowaniu 0) dla wejścia 0. Wypróbuj go online w interprecie CJam .
źródło
Stax , 32 bajty
Uruchom i debuguj
Powinien być w stanie skrócić. Natywne wsparcie dla frakcji przez Staxa jest całkiem fajne.
Odpowiednik ASCII:
źródło