GolfScript (23 znaki)
{:^((1${\.**2^?%}+*}:f;
Wynik wartownika dla nieistniejącej odwrotności to 0
.
Jest to proste zastosowanie twierdzenia Eulera . , więc x - 1 ≡ x 2 n - 1 - 1xφ(2n)≡1(mod2n)x−1≡x2n−1−1(mod2n)
Niestety jest to zbyt duża wykładnicza wartość, aby obliczyć bezpośrednio, więc musimy użyć pętli i dokonać modularnej redukcji w pętli. Krok iteracyjny to i mamy do wyboru wariant podstawowy: albo zx2k−1=(x2k−1−1)2×xk=1
{1\:^(@{\.**2^?%}+*}:f;
lub k=2
z
{:^((1${\.**2^?%}+*}:f;
Pracuję nad innym podejściem, ale wartownik jest trudniejszy.
Kluczową obserwacją jest to, że możemy budować odwrotność w górę krok po kroku: jeśli a następnie x y ∈ { 1 , 1 + 2 k - 1 }xy≡1(mod2k−1) , a jeśli x jest nieparzyste, mamy x ( y + x y - 1 ) ≡ 1xy∈{1,1+2k−1}(mod2k)x . (Jeśli nie jesteś przekonany, sprawdź oba przypadki osobno). Możemy więc zacząć od dowolnego odpowiedniego przypadku podstawowego i zastosować transformację y ′ = ( x + 1 ) y - 1x(y+xy−1)≡1(mod2k)y′=(x+1)y−1 odpowiednią liczbę razy.
Ponieważ otrzymujemy przez indukcję0x≡1(mod20)
x(1−(x+1)nx)≡1(mod2n)
gdzie odwrotność jest sumą sekwencji geometrycznej. Pokazałem wyprowadzenie, aby uniknąć efektu królika poza kapeluszem: biorąc pod uwagę to wyrażenie, łatwo to zauważyć (biorąc pod uwagę, że wartość w nawiasach kwadratowych jest liczbą całkowitą, która wynika z jego wyprowadzenia jako sumy liczby całkowitej sekwencja) produkt po lewej musi być w odpowiedniej klasie równoważności, jeśli jest parzyste.x+1
To daje funkcję 19-znakową
{1$)1$?@/~)2@?%}:f;
która daje poprawne odpowiedzi dla danych wejściowych, które mają odwrotność. Jednak nie jest to takie proste, gdy jest parzyste. Jedną potencjalnie interesującą opcją, którą znalazłem, jest dodanie zamiast .xx&1
1
{1$.1&+1$?@/~)2@?%}:f;
02n−1 , ale jeszcze tego nie udowodniłem.
01−(x+1)n1−1n
{1$.1&*)1$?@/~)2@?%}:f;
nn x f
{..1&*)2$?\/~)2@?%}:f;