(Przekreślone 44 to wciąż 44.) Dzięki Fireflame241 za uratowanie bajtu!
P=input();i=P/3
while i*10%P-1:i-=1
print i
Wypróbuj online!
Jest dokładnie jedna liczba pomiędzy 0i P-1która jest odwrotnością 10. Ale jeśli ta odwrotność ujest większa niż P/2, to (u-P)jest również odwrotnością i ma mniejszą wartość bezwzględną niż u. Okazuje się więc, że naprawdę szukamy unikalnej liczby xpomiędzy -P/2i P/2która jest odwrotnością 10.
Powyższy kod robi dokładnie to, zaczynając od (najniższy poziom) P/2i schodząc w dół, aż do osiągnięcia odwrotności. To musi się zdarzyć dla pewnej liczby większej niż -P/2tak długo, jak liczba Ppierwsza jest większa niż 10. Mówiąc dokładniej, zakończy się wtedy i tylko wtedy, gdy Pjest chroniony prawem autorskim 10.
Edycja: Okazuje się, że xna pewno jest pomiędzy -P/3i P/3, więc bieżąca wersja zaczyna się od P/3i schodzi z tego miejsca. Wyjaśnienie tego znajduje się w sekcji „ Poprawiona granica” .
Wyjaśnienie matematyczne
Nie od razu zrozumiałem, dlaczego zadziałał test podzielności. Oto wyjaśnienie, na wypadek gdyby ktoś się zastanawiał.
Niech Pbędzie liczbą pierwszą, większą niż 10, której ostatnią cyfrą jest b. A zatem
P = 10a + b
gdzie a > 0i 0 <= b < 10. W rzeczywistości bjest albo 1, 3, 7, lub 9, z powodu doskonałej większy niż 10końcowy musi w jednej z tych cyfr.
Załóżmy teraz bx + a = 0 (mod P). Następnie
a = -bx (mod P)
10a + b = 10(-bx) + b (mod P)
0 = 10(-bx) + b (mod P)
0 = b(1 - 10x) (mod P)
Ponieważ Pjest liczbą pierwszą, liczby całkowite mod Psą domeną integralną . Więc albo b = 0 (mod P), albo 1 - 10x = 0 (mod P).
Wiemy 0 <= b < 10 < P, więc jeśli b = 0 (mod P)potem b = 0. Ale my powiedzieliśmy balbo jest 1, 3, 7, lub 9, więc jest to niemożliwe. Dlatego 1 - 10x = 0 (mod P)tak 10x = 1 (mod P). Innymi słowy, xjest odwrotnością 10modulo P.
Załóżmy teraz, że Njest nieujemną liczbą całkowitą, której ostatnia cyfra to d, więc N = 10c + d. mamy łańcuch równoważnych instrukcji:
10c + d = 0 (mod P)
<==> 10xc + dx = 0 (mod P)
<==> c + dx = 0 (mod P)
CO BYŁO DO OKAZANIA.
Przydatność?
Zastanawiałem się również, czy test podzielności (podany N = 10c + d, zastąpiony Nprzez dx + c) rzeczywiście byłby produktywny w praktyce. Czy przynajmniej rzetelnie zastępuje Ngo liczbą mniejszą niż N(w wartości bezwzględnej)?
Załóżmy N = 10c + d, gdzie c >= 0i 0 <= d < 10. W związku z tym 10c = N - d <= N. Przez nierówność trójkąta
|c + dx| <= |c| + |dx| = c + d|x| <= N/10 + d|x|
< N/10 + 10|x| <= N/10 + 10P/2 = N/10 + 5P
Jeśli więc 5P <= 9N/10to |c + dx| < N.
W szczególności, jeśli N >= 6P, to |c + dx| < N. Tak więc, biorąc pod uwagę Pzaczynamy od obliczenia 2P, 3P, ..., 6Pwraz z x. Następnie podano N, prowadzimy wielokrotnie test podzielności aż osiągniemy liczbę mniejszą niż lub równy 6P, i sprawdzić, czy wynik jest każda z liczb 0, P, 2P, ..., 6P.
(Oczywiście, ilekroć osiągniemy liczbę ujemną, zastępujemy ją wartością bezwzględną, co jest w porządku, ponieważ qmożna ją podzielić przez „ Ptylko i tylko jeśli” (-q)).
Ulepszona granica
Zauważyłem, że |x|/Pnigdy nie było tak blisko 1/2. W rzeczywistości wydawało się, że zawsze było mniej niż 1/3... lub po bliższym zbadaniu, był zawsze bardzo blisko albo 1/10albo 3/10. Wydawało się, że jest ono największe 4/13(co dzieje się, kiedy P=13i x=4). Dlaczego miałoby to być?
Niech ubędzie liczbą całkowitą i załóżmy, że 10u = kP + 1dla jakiejś liczby całkowitej k, tak ujest odwrotnie 10, modulo P. Wiemy również, że kjest to względnie pierwszy 10, ponieważ k(-P)jest równoważne 1modulo 10.
Teraz wiemy, że wszystkie odwrotności 10modulo Próżnią się wielokrotnościami P, więc możemy wziąć liczbę całkowitą ui dodawać lub odejmować wielokrotności według Pwoli, a wynik zawsze będzie odwrotnością 10modulo P. Załóżmy, że zdecydujemy się odjąć Pod u: otrzymujemy
10(u - P) = 10u - 10P = kP + 1 - 10P
10(u - P) = (k - 10)P + 1
Innymi słowy, zmniejszenie (odpowiednio zwiększenie) uo Podpowiada zmniejszeniu (wzrost) ko 10. Chcemy dodawać / odejmować wielokrotności Pod, uaż lewa strona zostanie zminimalizowana w wartości bezwzględnej; ale po lewej stronie jest dokładnie zminimalizowane, gdy po prawej stronie jest zminimalizowane, a więc chcemy dodać / odjąć 10od kdopóki po prawej stronie jest minimalizowane w wartości bezwzględnej.
Ale wiemy, że to się stanie, gdy kjest między -5i 5, a więc (ponieważ kjest stosunkowo prime do 10) to oznacza kto albo -3, -1, 1, lub 3. (To jest treść komentarza @ Neil w OP. Dzięki, Neil! )
Tak więc, gdy |u|jest zminimalizowany (tj u=x), będziemy mieć x/P = u/P = k/10 + 1/(10P), gdzie kjest albo -3, -1, 1, lub 3. W związku z tym |x|/P <= 3/10 + 1/(10P). Odpowiednio |x| <= (3P + 1)/10.
Co więcej, nierówność ta jest surowa w P=11, ponieważ w P=11mamy x=-1i k=-1. Najmniejsze, Pdla którego obowiązuje równość, to P=13(gdzie x=4i k=3).
Dlatego największa, |x|/Pjaka kiedykolwiek dostaje, jest 3/10 + 1/(10*13), ponieważ P=13jest to pierwsza liczba pierwsza, dla której mamy k=3, a wśród tych z k=3, 1/(10P)termin jest największy, gdy Pjest najmniejszy (tj. At P=13). Dlatego też wszyscy Pmamy |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. To wyjaśnia, dlaczego w powyższym kodzie możemy zainicjować o, i = P/3zamiast zaczynać od P/2.
Ponadto można teraz poprawić granice w powyższej sekcji Przydatność .
Lemma : Niech N = 10c + dgdzie c > 0i 0 <= d <= 9. Potem c + d|x| < N/10 + 9(3P + 1)/10. (Zwróć uwagę na ścisłą nierówność.)
Dowód lematu: według przypadków. Przypadek I: d = 0tak N = 10c. Potem c + d|x| = c = N/10 < N/10 + 9(3P + 1)/10.
Przypadek II: 0 < d <= 9. Więc 10c = N - d < Ntak c < N/10. W związku z tym c + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10. CO BYŁO DO OKAZANIA.
Zatem jeśli N > 3P (i N = 10c + djak poprzednio), to
3P + 1 <= N
9(3P + 1)/10 <= 9N/10
N/10 + 9(3P + 1)/10 <= N
c + d|x| < N/10 + 9(3P + 1)/10 <= N
Więc jeśli N > 3Ptak c + d|x| < N.
Dlatego też, musimy tylko znaleźć P, 2Pa 3Pwraz z x. Biorąc pod uwagę N > 0, natomiast N > 3P, możemy zastąpićN przez |c + dx|, co zmniejsza N. W końcu dostaniemy N <= 3P; W tym momencie możemy zatrzymać się i sprawdzić, czy Njest równa żadnej z liczb 0, P, 2P, lub 3P.
Nie możemy zrobić nic lepszego niż 3Pogólnie. Załóżmy na przykład P = 13i N = 39takx = 4 . Następnie zastąpione Nprzez dx + c = 9(4) + 3liście Nbez zmian.
xwartości bezwzględnej, która10*x-1jest podzielna przez dane wejściowe.