Zadanie jest następujące. Biorąc pod uwagę liczbę całkowitą x(taką, że xmodulo 100000000003nie jest równe 0) przedstawioną w kodzie w dowolny dogodny sposób, wypisz kolejną liczbę całkowitą y < 100000000003, aby (x * y) mod 100000000003 = 1.

Kod musi trwać krócej niż 30 minut, aby uruchomić się na standardowym komputerze stacjonarnym dla każdegox takiego wejścia |x| < 2^40.

Przypadki testowe

Wejście: 400000001. Wyjście: 65991902837

Wejście: 4000000001. Wyjście: 68181818185

Wejście: 2. Wyjście: 50000000002

Wejście: 50000000002. Wyjście: 2.

Wejście: 1000000. Wyjście: 33333300001

Ograniczenia

Nie wolno używać żadnych bibliotek ani wbudowanych funkcji, które wykonują arytmetykę modulo (lub tę odwrotną operację). Oznacza to, że nie możesz się obejść a % bbez wdrożenia %się. Możesz jednak użyć wszystkich innych niemodulo modulowanych wbudowanych funkcji arytmetycznych.

Podobne pytanie

Jest to podobne do tego pytania, choć, mam nadzieję, na tyle różne, że nadal będzie interesujące.

Pyth, 24 bajty

L-b*/bJ+3^T11Jy*uy^GT11Q

Zestaw testowy

Wykorzystuje to fakt, że mod ^ (p-2) p = mod ^ ^ p.

Najpierw ręcznie reimplementuję moduł, dla konkretnego przypadku mod 100000000003. Używam wzoru a mod b = a - (a/b)*b, w którym /jest dzielenie zmiennoprzecinkowe. Generuję moduł za 10^11 + 3pomocą, używając kodu +3^T11, a następnie zapisuję go J, a następnie używam tej i powyższej formuły do ​​obliczenia b mod 100000000003 za pomocą -b*/bJ+3^T11J. Funkcja ta jest określona jako yw L.

Następnie zaczynam od wejścia, następnie doprowadzam do dziesiątej mocy i redukuję mod 100000000003, i powtarzam to 11 razy. y^GTto kod wykonywany na każdym kroku i uy^GT11Quruchamia go 11 razy, zaczynając od danych wejściowych.

Teraz mam Q^(10^11) mod 10^11 + 3i chcę Q^(10^11 + 1) mod 10^11 + 3, więc mnożę przez dane wejściowe *, redukuję to mod 100000000003 ypo raz ostatni i generuję.

Haskell , 118 113 105 101 bajtów

Inspirowane tym rozwiązaniem .

-12 od Ørjan Johansen

p=10^11+3
k b=((p-2)?b)b 1
r x=x-div x p*p
(e?b)s a|e==0=a|1<2=(div e 2?b$r$s*s)$last$a:[r$a*s|odd e]

Wypróbuj online!

Haskell , 48 bajtów

Przepisz to rozwiązanie . Chociaż jest wystarczająco szybki dla wektora testowego, to rozwiązanie jest zbyt wolne dla innych wejść.

s x=until(\t->t-t`div`x*x==0)(+(10^11+3))1`div`x

Wypróbuj online!

Brachylog , 22 bajty

∧10^₁₁+₃;İ≜N&;.×-₁~×N∧

Wypróbuj online!

Zajęło to około 10 minut w 1000000przypadku nieco innej (i dłuższej) wersji kodu, która była dokładnie dwa razy szybsza (sprawdzono tylko wartości dodatnie İzamiast zarówno dodatnich, jak i ujemnych). Dlatego wypełnienie tego wpisu powinno zająć około 20 minut.

Wyjaśnienie

Po prostu to opisujemy Input × Output - 1 = 100000000003 × an integeri pozwól Outputnam znaleźć arytmetykę ograniczeń .

∧10^₁₁+₃                   100000000003
        ;İ≜N               N = [100000000003, an integer (0, then 1, then -1, then 2, etc.)]
            &;.×           Input × Output…
                -₁         … - 1…
                  ~×N∧     … = the product of the elements of N

Technicznie nie potrzebujemy wyraźnego etykietowania ≜, jednak jeśli go nie użyjemy, ~×nie sprawdzi obudowy N = [100000000003,1](ponieważ często jest to bezużyteczne), co oznacza, że ​​będzie to bardzo powolne 2na przykład wprowadzanie danych, ponieważ będzie musiało znaleźć drugą najmniejszą liczbę całkowitą zamiast pierwszego.

Python, 53 51 49 58 53 49 bajtów

-2 bajty dzięki orlp
-2 bajty dzięki Officialaimm
-4 bajty dzięki Felipe Nardi Batist
-3 bajty dzięki isaacg
-1 bajt dzięki Ørjan Johansen
-2 bajty dzięki Federico Poloni

x=input()
t=1
while t-t/x*x:t+=3+10**11
print t/x

Wypróbuj online!

Rozpracowanie tego zajęło mi około 30 minut. Moim rozwiązaniem jest zacząć od pierwszej liczby, która zmieni się na 1. Ta liczba to 1. Jeśli jest podzielna przez x, to y jest liczbą podzieloną przez x. Jeśli nie, dodaj 10000000003 do tego numeru, aby znaleźć drugą liczbę, której mod 1000000003 będzie równy 1 i powtórz.

JavaScript (ES6), 153 143 141 bajtów

Zainspirowany tą odpowiedzią od math.stackexchange.com .

Funkcja rekurencyjna oparta na algorytmie euklidesowym.

f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)

Modulo jest realizowane przez obliczenia:

quotient = Math.floor(a / b);
remainder = a - b * quotient;

Ponieważ iloraz jest również potrzebny, robienie tego w ten sposób ma sens.

Przypadki testowe

let f =

f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)

console.log(f(2))
console.log(f(50000000002))
console.log(f(1000000))

C ++ 11 (GCC / Clang, Linux), 104 102 bajtów

using T=__int128_t;T m=1e11+3;T f(T a,T r=1,T n=m-2){return n?f(a*a-a*a/m*m,n&1?r*a-r*a/m*m:r,n/2):r;}

https://ideone.com/gp41rW

Niegolfowany, oparty na twierdzeniu Eulera i potęgowaniu binarnym.

using T=__int128_t;
T m=1e11+3;
T f(T a,T r=1,T n=m-2){
    if(n){
        if(n & 1){
            return f(a * a - a * a / m * m, r * a - r * a / m * m, n / 2);
        }
        return f(a * a - a * a / m * m, r, n / 2);
    }
    return r;
}

Mathematica, 49 bajtów

x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&

PHP, 71 bajtów

for(;($r=bcdiv(bcadd(bcmul(++$i,1e11+3),1),$argn,9))!=$o=$r^0;);echo$o;

Przypadki testowe

Rubinowy , 58 bajtów

Na razie wykorzystuje isaacgowskie małe twierdzenie Fermata, podczas gdy ja kończę mierzenie rozwiązania brutalnej siły.

->n,x=10**11+3{i=n;11.times{i**=10;i-=i/x*x};i*=n;i-i/x*x}

Aktualna wersja brute force, która wynosi 47 bajtów, lecz może być to zbyt wolno:

->n,x=10**11+3{(1..x).find{|i|i*=n;i-i/x*x==1}}

Wypróbuj online!