Chiński pozostająca Twierdzenie mówi nam, że zawsze możemy znaleźć numer, który produkuje wszelkie wymagane pozostałości pod różnymi głównych modułów. Twoim celem jest napisanie kodu, który wyświetli taką liczbę w czasie wielomianowym. Najkrótszy kod wygrywa.

Na przykład powiedzmy, że mamy te ograniczenia ( %reprezentuje mod):

n % 7  == 2
n % 5  == 4
n % 11 == 0

Jednym z rozwiązań jest n=44. Pierwsze ograniczenie jest spełnione, ponieważ 44 = 6*7 + 2i tak 44pozostało, 2gdy zostanie podzielone przez 7, i w ten sposób 44 % 7 == 2. Pozostałe dwa ograniczenia są również spełnione. Istnieją inne rozwiązania, takie jak n=814i n=-341.

Wkład

Niepusta lista par (p_i,a_i), w której każdy moduł p_ijest odrębną liczbą pierwszą, a każdy cel a_ijest liczbą naturalną w zakresie 0 <= a_i < p_i. Możesz przyjmować dane wejściowe w dowolnej dogodnej formie; to wcale nie musi być lista par. Nie możesz zakładać, że dane wejściowe są posortowane.

Wydajność

Liczba całkowita ntaka jak n % p_i == a_idla każdego indeksu i. Nie musi to być najmniejsza taka wartość i może być ujemna.

Wielomianowe ograniczenie czasu

Aby zapobiec tanie rozwiązania, które po prostu spróbować n=0, n=1, n=2, i tak dalej, kod musi działać w czasie wielomianowym na długości wejścia . Zauważ, że liczba mna wejściu ma długość Θ(log m), więc msama nie jest wielomianowa w swojej długości. Oznacza to, że nie można liczyć mani wykonywać operacji m, ale można obliczać operacje arytmetyczne na wartościach.

Nie można użyć nieefektywnego formatu wejściowego, takiego jak unary, aby obejść ten problem.

Inne zakazy

Wbudowane funkcje do wykonywania następujących czynności są niedozwolone: ​​Implementuj twierdzenie Chinese Remainder, rozwiązuj równania lub liczby czynników.

Możesz używać wbudowanych funkcji do znajdowania modów i dodawania, odejmowania, mnożenia i potęgowania modularnego (z wykładnikiem liczby naturalnej). Nie możesz używać innych wbudowanych operacji modułowych, w tym odwrotności modułowej, dzielenia i ustalania kolejności.

Przypadki testowe

Dają one najmniejsze nieujemne rozwiązanie. Twoja odpowiedź może być inna. Prawdopodobnie lepiej będzie, jeśli sprawdzisz bezpośrednio, czy dane wyjście spełnia każde ograniczenie.

[(5, 3)] 
3

[(7, 2), (5, 4), (11, 0)]
44

[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
1770977011

[(982451653, 778102454), (452930477, 133039003)]
68121500720666070

Mathematica, 55 51 45

Modułowe odwrotne jest zabronione, ale dozwolone jest potęgowanie modułowe. Przez małego twierdzenia Fermata, n^(-1) % p == n^(p-2) % p.

(PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&

Przykład:

In[1]:= f = (PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&;

In[2]:= f[{{5, 3}}]

Out[2]= 3

In[3]:= f[{{7, 2}, {5, 4}, {11, 0}}]

Out[3]= 1584

In[4]:= f[{{5, 1}, {73, 4}, {59, 30}, {701, 53}, {139, 112}}]

Out[4]= 142360350966

Dla żartu:

ChineseRemainder@@Reverse@Thread@#&

Python 2, 165 101 99 98 85 bajtów

Używając małego twierdzenia Fermata, podobnie jak innych odpowiedzi. Nie przejmuje się utrzymywaniem końcowej sumy w zakresie modułowym, ponieważ nie interesuje nas najmniejsze rozwiązanie. Dzięki Zmienność za zaoszczędzenie 13 bajtów.

l=input();x=reduce(lambda a,b:a*b[0],l,1)
print sum(x/a*b*pow(x/a,a-2,a)for a,b in l)

[(5, 3)]
3
[(7, 2), (5, 4), (11, 0)]
1584
[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
142360350966

Pyth, 40 37 36 29

M*G.^G-H2Hsm*edg/u*GhHQ1hdhdQ

Wykorzystuje małe twierdzenie Fermata, dzięki alephalpha. Oblicza przy użyciu tej formuły .

Ruby, 129

Cóż, towarzysze, wydaje się, że rozwiązania Rubiego muszą być dłuższe, ponieważ modułowe potęgowanie nie jest dostępne bez ładowania biblioteki openssl i wykonywania konwersji do OpenSSL :: BN. Mimo to dobrze się bawiłem pisząc to:

require("openssl")
z=eval(gets)
x=1
z.map{|a,b|x*=a}
s=0
z.map{|a,b|e=a.to_bn;s+=(x/a).to_bn.mod_exp(e-2,e).to_i*b*x/a}
puts(s)

Python 2, 61

n=P=1
for p,a in input():n+=P*(a-n)*pow(P,p-2,p);P*=p
print n

Wykorzystuje to odmianę konstrukcji produktu, z której korzystają inne odpowiedzi.

Chodzi o to, aby ominąć ograniczenia i zaktualizować rozwiązanie tak, naby spełniało obecne ograniczenie bez zepsucia poprzednich. Aby to zrobić, śledzimy iloczyn Pliczb pierwszych widzianych do tej pory i obserwujemy, że dodanie wielokrotności Pnie ma wpływu modulo na żadną już widzianą liczbę pierwszą.

Tak więc musimy tylko zmienić, naby spełnić n%p == a, dodając odpowiednią wielokrotność P. Rozwiązujemy dla współczynnika c:

(n + P*c) % p == a

Wymaga to c = (a-n) * P^(-1), że tam gdzie odwrotność jest brana modulo p. Jak zauważają inni, odwrotność można obliczyć według Małego Twierdzenia Fermata jako P^(-1) = pow(P,p-2,p). Tak więc c = (a-n) * pow(P,p-2,p)aktualizujemy nprzez n+= P * (a-n) * pow(P,p-2,p).

Haskell, 68 100 bajtów

f l=sum[p#(m-2)*n*p|(m,n)<-l,let a#0=1;a#n=(a#div n 2)^2*a^mod n 2`mod`m;p=product(map fst l)`div`m]

Zastosowanie: f [(5,1), (73,4), (59,30), (701,53), (139,112)]->142360350966 .

Edycja: teraz z szybką funkcją „power / mod”. Stara wersja (68 bajtów) z wbudowaną funkcją zasilania:

f l=sum[l#m^(m-2)`mod`m*n*l#m|(m,n)<-l]
l#m=product(map fst l)`div`m