Biorąc pod uwagę listę wyrażeń matematycznych, które są prawdziwe i składają się z obliczeń reszty modulo z dwiema liczbami i wynikiem, Twoim zadaniem jest uzyskanie pierwszych nliczb, które są prawdziwe dla wszystkich instrukcji na liście.

Na przykład:

[m % 3 = 0, m % 4 = 1, m % 5 = 3], gdzie% jest operatorem modulo.

Dla n= 3 pierwsze 3 liczby (licząc od 0), które pasują do sekwencji, są 33, 93, 153więc wynikiem (format do ciebie).

Zasady / IO

1. Bierzesz liczbę dodatnią ni listę prawd. Oczywiście, potrzebne są tylko RHS operacji modulo i wynik.
2. na liczby na liście prawd zawsze będą w zakresie 1 -> 2 ^ 31-1 , podobnie jak wyniki.
3. Bierzesz dane w dowolnej dogodnej formie i dane wyjściowe w dowolnej dogodnej formie. Na przykład, wejście: 3 [3 0, 4 1, 5 3]i wyjście: 33 93 153.
4. Gwarantuje to, że rozwiązanie jest matematycznie możliwe.
5. Źródło danych wejściowych może pochodzić z pliku, parametrów funkcji, standardowego wejścia itd. To samo dotyczy danych wyjściowych.
6. Bez luk.
7. To jest golf golfowy, więc wygrywa najmniejsza liczba bajtów.

Przypadki testowe

# Input in the form <n>, <(d r), (d2 r2), ...>
# where <d> = RHS of the modulo expression and <r> the result of the expression. Output in the next line.

5, (3 2), (4 1), (5 3)
53 113 173 233 293

3, (8, 0), (13, 3), (14, 8)
120 848 1576

Implementacja referencji w pseudokodzie

n = (an integer from stdin)
truths = (value pairs from stdin)
counter = 0

while n != 0 {
    if matches_criterias(counter, truths) {
        print counter
        n -= 1
    }

    counter += 1
}

Galaretka , 7 bajtów

%⁼⁴
0ç#

To jest pełny program. Argumentami są dzielniki, moduły docelowe i liczba rozwiązań w tej kolejności.

Wypróbuj online!

Jak to działa

0ç#  Main link.
     Left argument: D (array of divisors)
     Right argument: M (array of target moduli)
     Third argument: n (number of solutions)

0ç#  Execute the helper link with k = 0, 1, 2, ... as left argument and D as the
     right one until n of them return 1. Yield the array of matches.


%⁼⁴  Helper link. Left argument: k. Right argument: D

%    Compute k % d for each d in D.
 ⁼⁴  Compare the result with M.

Perl 6 , 33 bajtów

{grep((*X%@^b)eqv@^c,0..*)[^$^a]}

Spróbuj

Dane wejściowe to ( number-of-values, list-of-divisors, list-of-remainders )

Rozszerzony:

{   # bare block lambda with placeholder parameters ｢$a｣ ｢@b｣ ｢@c｣

  grep(

    # WhateverCode lambda:
    (

      *        # the value being tested

      X%       # cross modulus

      @^b      # with the divisors ( second parameter )

    )

    eqv        # is that list equivalent with

    @^c        # the expected remainders ( third parameter )

    # end of WhateverCode lambda

    ,

    0 .. *     # Range of all Integers starting with 0

  )[ ^$^a ]    # grab up-to ｢$a｣ values ( first parameter )
               # ( ｢^$a｣ is the same as ｢0 ..^ $a｣ )
}

JavaScript (ES6), 71 68 bajtów

a=>f=(n,m=0)=>n?a.some(x=>m%x[0]-x[1],++m)?f(n,m):[m,...f(n-1,m)]:[]

Prosta funkcja rekurencyjna. Użyj, curry w tablicy pierwszy i ndrugi, tak:

g=a=>f=(n,m=0)=>n?a.some(x=>m%x[0]-x[1],++m)?f(n,m):[m,...f(n-1,m)]:[]
g([[3, 2], [4, 1], [5, 3]])(5)

JavaScript (ES6), 74 70 69 bajtów

Staje wejście liczbą całkowitą noraz szereg az [modulo, remainder]tablic z currying składni (n)(a).

n=>a=>eval('for(i=r=[];a.some(([b,c])=>i%b-c)||--n*r.push(i);i++);r')

Przypadki testowe

let f =

n=>a=>eval('for(i=r=[];a.some(([b,c])=>i%b-c)||--n*r.push(i);i++);r')

console.log(f(5)([[3, 2], [4, 1], [5, 3]]))
console.log(f(3)([[8, 0], [13, 3], [14, 8]]))

Haskell, 47 bajtów

n#l=take n[i|i<-[0..],all(\(d,r)->mod i d==r)l]

Przykład użycia: 3 # [(8,0),(13,3),(14,8)]-> [120,848,1576].

Python, 67 bajtów

lambda n,r:[k for k in range(2**32)if all(k%d==m for d,m in r)][:n]

JavaScript (ES6), 72 70 bajtów

a=>g=(n,i,r=[],m=a.some(e=>i%e[0]^e[1]))=>n?g(n-!m,-~i,m?r:[...r,i]):r

Zwinięte w pierwszej kolejności tablica warunków i druga liczba wyników. Edycja: Zapisano 2 bajty, nie obsługując wielkości zerowej.

Mathematica, 42 bajty

#2~ChineseRemainder~#+Range[0,#3-1]LCM@@#&

Funkcja bez nazwy, zwracająca listę dodatnich liczb całkowitych i przyjmująca trzy dane wejściowe: listę modułów, listę reszt i liczbę nliczb całkowitych do zwrócenia. Na przykład drugi przypadek testowy jest wywoływany przez

#2~ChineseRemainder~#+Range[0,#3-1]LCM@@#&[{8,13,14},{0,3,8},3]

i wraca {120, 848, 1576}.

Wbudowane #2~ChineseRemainder~#daje najmniejsze nieujemne rozwiązanie; aby uzyskać wszystkie pożądane rozwiązania, dodajemy tę liczbę Range[0,#3-1]LCM@@#, która jest pierwszą nnieujemną wielokrotnością najmniejszej wspólnej wielokrotności wszystkich modułów.

O ile mi wiadomo, Mathematica nie ma leniwie ocenianych nieskończonych list, więc ta implementacja była krótsza niż cokolwiek, co znalazłem, które testowało nieujemne liczby całkowite jeden po drugim - nawet przy długości nazwy funkcji ChineseRemainder, i mimo że test taki Mod[k,{8,13,14}]=={0,3,8}działa idealnie dobrze.

PHP, 97 bajtów

najdłuższa jak dotąd odpowiedź. Ale cieszę się, że udało mi się uzyskać go poniżej 100.

for($a=$argv;++$k;)for($i=$v=2;$m=$a[$i++];$v>$argc/2&&$a[1]-->0?print$k._:0)$v+=$k%$m==$a[$i++];

pobiera dane wejściowe z oddzielnych argumentów wiersza poleceń,
drukuje dopasowania oddzielone i poprzedzone znakami podkreślenia.
Pętla nigdy nie pęka; ledwo odpowiedni dla testerów online.

Biegnij jak php -r 'code' <n> <modulo1> <result1> <modulo2> <result2> ....

awaria

for($a=$argv;++$k;)         // loop $k up from 1
    for($i=$v=2;                // $i = argument index, $v=2+ number of satisfied equations
        $m=$a[$i++];            // loop through modulo/result pairs
        $v>$argc/2                  // 2. if $v>argument-count/2
        &&$a[1]-->0                 // and match count not exhausted
            ?print$k._                  // print match
            :0                          // else do nothing
        )
            $v+=$k%$m==$a[$i++];    // 1. if $k%modulo==result, increment $v

notatki

$argc==count($argv). Dla trzech par istnieje 8 argumentów: nazwa pliku $argv[0], n= $argv[1]i pary modulo/ resultpowyżej. $v=2inkrementowane 3 razy daje 5> $argc/2.

Dodaj jeden bajt na czystą wyjścia: Wymień &&$a[1]-->0?print$k._się ?$a[1]--?print$k._:die.

Pyth - 14 13 bajtów

.f!fneT%ZhTQE

Wypróbuj online tutaj .

SmileBASIC, 102 bajty

DEF V N,M
FOR K=1TO N@L
T=T+1F=0FOR J=1TO LEN(M)F=F||T MOD M[J-1]-M[J]J=J+1NEXT
ON!F GOTO @L?T
NEXT
END

To pierwszy raz, kiedy używałem ONw SB. Powodem, dla którego użyłem go tutaj, IF F GOTO@Lbyło umieszczenie ?Tgo w tym samym wierszu, oszczędzając 1 bajt.

Python, 59 bajtów

lambda n,m:[i for i in range(2**31)if all(map(eval,m))][:n]

m jest listą wyrażeń w postaci łańcucha, takich jak ["i % 4 == 1", ...]

Wypróbuj online (z mniejszym zasięgiem, więc faktycznie się skończy)

PHP, 91 bajtów

Weź listę jako tablicę asocjacyjną

<?for($t=1;$r<$_GET[1];$i+=$t=!$t?:print+$i._.!++$r)foreach($_GET[0]as$k=>$v)$t*=$i%$k==$v;

Wypróbuj online!