Chińskie twierdzenie o resztach może być bardzo przydatna w arytmetyce modularnej.

Rozważmy na przykład następujący zestaw relacji zgodności:

W przypadku zestawów warunków kongruencji jak ten, w którym wszystkie zasady ( 3, 5, 7w tym przykładzie) są wspólnie pierwsza z siebie, że będzie jeden i tylko jeden całkowitą nod 1i produkt z zasady ( 3*5*7 = 105w tym przykładzie) włącznie, który spełnia stosunki .

W tym przykładzie liczba byłaby 14wygenerowana według tej formuły:

gdzie 2, 4, and 0podano z powyższego przykładu.

70, 21, 15są współczynniki o wzorze i są one zależne od podstawach 3, 5, 7.

Aby obliczyć współczynniki wzoru ( 70, 21, 15w naszym przykładzie) dla zestawu zasad, stosujemy następującą procedurę.

Dla każdej liczby aw zestawie zasad:

1. Znajdź produkt wszystkich innych baz, oznaczonych jako P.
2. Znajdź pierwszą wielokrotność, Pktóra pozostawia resztę 1po podzieleniu przez a. Jest to współczynnik a.

Na przykład, aby obliczyć współczynnik odpowiadający podstawie 3, znajdujemy iloczyn wszystkich pozostałych zasad (tj. 5*7 = 35), A następnie znajdujemy pierwszą wielokrotność tego produktu, która pozostawia resztę 1po podzieleniu przez zasadę.

W tym przypadku 35pozostawia resztę 2po podzieleniu przez 3, ale 35*2 = 70pozostawia resztę 1po podzieleniu przez 3, więc 70jest to odpowiedni współczynnik dla 3. Podobnie 3*7 = 21pozostawia resztę 1po podzieleniu przez 5i 3*5 = 15pozostawia resztę 1po podzieleniu przez 7.

W skrócie

Dla każdej liczby aw zestawie liczb:

1. Znajdź iloczyn wszystkich pozostałych liczb oznaczonych jako P.
2. Znajdź pierwszą wielokrotność, Pktóra pozostawia resztę 1po podzieleniu przez a. Jest to współczynnik a.

Wyzwanie

• Wyzwaniem dla zestawu dwóch lub więcej zasad jest znalezienie zestawu odpowiednich współczynników.
• Zestaw podstaw jest gwarantowany jako para-podstawowa, a każda podstawa jest większa niż 1.
• Twoje dane wejściowe to lista liczb całkowitych jako [3,4,5]ciąg wejściowy lub ciąg znaków oddzielonych spacjami "3 4 5"lub dane wejściowe działają.
• Wynik powinien być albo listą liczb całkowitych, albo ciągiem znaków oddzielonych spacją, który oznacza zbiór współczynników.

Przypadki testowe

input             output
[3,5,7]           [70,21,15]
[2,3,5]           [15,10,6]
[3,4,5]           [40,45,36]
[3,4]             [4,9]
[2,3,5,7]         [105,70,126,120]
[40,27,11]        [9801,7480,6480]
[100,27,31]       [61101,49600,56700]
[16,27,25,49,11]  [363825,2371600,2794176,5583600,529200]

Wielkie dzięki dla Dziurawej Zakonnicy za pomoc w napisaniu tego wyzwania. Jak zawsze, jeśli problem jest niejasny, daj mi znać. Powodzenia i dobrej gry w golfa!

Haskell, 61 55 53 bajtów

f x=[[p|p<-[0,product x`div`n..],p`mod`n==1]!!0|n<-x]

Definiuje funkcję, fktóra pobiera dane wejściowe i podaje dane wyjściowe jako listę liczb całkowitych.

f x=[                                          |n<-x]  (1)
              product x                                (2)
                       `div`n                          (3)

Najpierw zapętlamy wszystkie liczby całkowite na wejściu (1). Następnie bierzemy iloczyn wszystkich liczb całkowitych (2) i dzielimy przez n, aby otrzymać tylko iloczyn nliczb całkowitych, czyli P(3).

           [0,               ..]                       (4)
     [p|p<-                     ,p`mod`n==1]           (5)
                                            !!0        (6)

Następnie wykorzystujemy wynik ( P) jako wartość kroku dla zakresu rozpoczynającego się od zera (4). Bierzemy wynik [0, P, 2P, 3P, ...]i filtrujemy go według wartości, dla których wynikiem operacji mod-n jest jeden (5). Na koniec bierzemy pierwszy element, który działa dzięki leniwej ocenie (6).

Dzięki @xnor za 2 bajty!

Galaretka , 11 7 bajtów

P:*ÆṪ%P

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Niech P i być ściśle dodatnich, względnie pierwsze liczby całkowite.

Dwuetapowy proces w pytaniu - znalezienie wielokrotności P, która pozostawia resztę 1, gdy dzieli się przez a - można opisać następującym równaniem zgodności.

Według twierdzenia Eulera-Fermata mamy

gdzie φ oznacza funkcję całkowitą Eulera . Na podstawie tego wyniku wnioskujemy, co następuje.

Wreszcie, ponieważ wyzwanie wymaga od nas obliczenia Px , obserwujemy to

gdzie Pa można obliczyć jako iloczyn wszystkich modułów.

Jak to działa

P:*ÆṪ%P  Main link. Argument: A (list of moduli)

P        Yield the product of all moduli.
 :       Divide the product by each modulus in A.
   ÆṪ    Apply Euler's totient function to each modulus.
  *      Raise each quotient to the totient of its denominator.
     %P  Compute the remainder of the powers and the product of all moduli.

J, 13 bajtów

*/|5&p:^~*/%]

Na podstawie niesamowitej odpowiedzi @Dennis .

Stosowanie

Niektóre przypadki testowe będą wymagały danych wejściowych jako rozszerzonych liczb całkowitych z sufiksem x.

   f =: */|5&p:^~*/%]
   f 3 5 7
70 21 15
   f 40x 27 11
9801 7480 6480
   f 16x 27 25 49 11
363825 2371600 2794176 5583600 529200

Wyjaśnienie

*/|5&p:^~*/%]  Input: list B
         */    Reduce B using multiplication to get the product of the values
            ]  Identity function, get B
           %   Divide the product by each value in B, call the result M
   5&p:        Apply the totient function to each value in B, call the result P
       ^~      Raise each value in M to the power of its corresponding value in P
*/             The product of the values in B
  |            Compute each power modulo the product and return

Wypróbuj tutaj.

Mathematica, 27 bajtów

PowerMod[a=LCM@@#/#,-1,#]a&

Pyth , 14 bajtów

mhfq1%Td*R/*FQ

Zestaw testowy.

Naiwna implementacja algorytmu.

Galaretka, 14 13 bajtów

P:×"Ḷð%"’¬æ.ḷ

Zapisano bajt dzięki @ Dennis !

Wykorzystuje proces opisany w specyfikacji wyzwania. Dane wejściowe to lista zasad, a dane wyjściowe to lista współczynników.

Wypróbuj online lub Zweryfikuj wszystkie przypadki testowe .

Wyjaśnienie

P:×"Ḷð%"’¬æ.ḷ  Input: a list B
P              Get the product of the list
 :             Divide it by each value in the B, call it M
    Ḷ          Get a range from 0 to k for k in B
  ×"           Vectorized multiply, find the multiples of each M
     ð         Start a new dyadic chain. Input: multiples of M and B
      %"       Vectorized modulo, find the remainders of each multiple by B
        ’      Decrement every value
               If the remainder was 1, decrementing would make it 0
         ¬     Logical NOT, zeros become one and everything else becomes 0
            ḷ  Get the multiples of M
          æ.   Find the dot product between the modified remainders and the multiples
               Return

JavaScript (ES6), 80 bajtów

a.map(e=>[...Array(e).keys()].find(i=>p*i/e%e==1)*p/e,p=a.reduce((i,j)=>i*j))

Wypróbowałem rozszerzony algorytm euklidesowy, ale zajmuje on 98 bajtów:

a=>a.map(e=>(r(e,p/e)+e)%e*p/e,p=a.reduce((i,j)=>i*j),r=(a,b,o=0,l=1)=>b?r(b,a%b,t,o-l*(a/b|0)):o)

Jeśli wszystkie wartości są liczbą pierwszą, ES7 może to zrobić w 56 bajtach:

a=>a.map(e=>(p/e%e)**(e-2)%e*p/e,p=a.reduce((i,j)=>i*j))

Python + SymPy, 71 bajtów

from sympy import*
lambda x:[(prod(x)/n)**totient(n)%prod(x)for n in x]

Wykorzystuje algorytm z mojej odpowiedzi Jelly . I / O ma postać list numerów SymPy.

Python 2, 87 84 bajtów

Prosta implementacja algorytmu. Sugestie dotyczące gry w golfa mile widziane.

a=input();p=1
for i in a:p*=i
print[p/i*j for i in a for j in range(i)if p/i*j%i==1]

Cheddar , 64 bajty

n->n.map(i->(|>i).map(j->(k->k%i>1?0:k)(n.reduce((*))/i*j)).sum)

GAP , 51 bajtów

GAP ma funkcję, która może obliczyć motywujący przykład ChineseRem([2,5,7],[2,4,0]), ale wciąż nie ułatwia to uzyskania współczynników. Możemy uzyskać n-ty współczynnik, używając listy z jednym w n-tej pozycji i zerami w innych pozycjach jako drugim argumentem. Musimy więc utworzyć te listy i zastosować funkcję do wszystkich:

l->List(Basis(Integers^Size(l)),b->ChineseRem(l,b))

Partia, 148 bajtów

@set p=%*
@set/ap=%p: =*%
@for %%e in (%*)do @for /l %%i in (1,1,%%e)do @call:l %%e %%i
@exit/b
:l
@set/an=p/%1*%2,r=n%%%1
@if %r%==1 echo %n%

Właściwie 14 bajtów

Wykorzystuje to algorytm w odpowiedzi Dennisa Jelly . Nadchodzi kolejna odpowiedź oparta na mojej odpowiedzi w języku Python. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

;π;)♀\;♂▒@♀ⁿ♀%

Jak to działa

                 Implicit input a.
;                Duplicate a.
 π;)             Take product() of a, duplicate and rotate to bottom.
    ♀\           Integer divide the product by each element of a. Call this list b.
      ;♂▒        Take that list, duplicate, and get the totient of each element.
         @♀ⁿ     Swap and take pow(<item in b>, <corresponding totient>)
            ♀%   Modulo each item by the remaining duplicate product on the stack.
                 Implicit return.

Kolejna odpowiedź oparta na mojej odpowiedzi w języku Python na 22 bajty. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

;π╖`╝╛╜\╛r*"╛@%1="£░`M

Jak to działa

            Implicit input a.
;π╖         Duplicate, take product of a, and save to register 0.
`...`M      Map over a.
  ╝           Save the item, b, in register 1.
  ╛╜\         product(a) // b. Call it P.
  ╛r          Take the range [0...b].
  *           Multiply even item in the range by P. Call this list x.
  "..."£░     Turn a string into a function f.
              Push values of [b] where f returns a truthy value.
    ╛@%         Push b, swap, and push <item in x> % b.
    1=          Does <item> % b == 1?
            Implicit return.