Hitung modulus terbalik

18

Tugas:

Keluarkan nilai untuk x, di mana a mod x = buntuk dua nilai yang diberikan a,b.

Anggapan

  • adan bakan selalu menjadi bilangan bulat positif
  • Tidak akan selalu ada solusi untuk itu x
  • Jika ada beberapa solusi, hasilkan setidaknya satu di antaranya.
  • Jika tidak ada solusi, tidak ada output atau indikasi yang tidak ada solusi.
  • Built-in diizinkan (tidak menyenangkan seperti pendekatan matematika lainnya)
  • Output selalu bilangan bulat

Contohnya

A, B >> POSSIBLE OUTPUTS

5, 2 >> 3
9, 4 >> 5
8, 2 >> 3, 6
6, 6 >> 7, (ANY NUMBER > 6)
8, 7 >> NO SOLUTION
2, 4 >> NO SOLUTION
8, 5 >> NO SOLUTION
10,1 >> 3, 9

Ini adalah , sehingga byte terendah menang.

Graviton
sumber
Bisakah itu kesalahan jika tidak ada solusi yang ditemukan?
bertepuk tangan
@ConfusedMr_C Secara teknis itu tidak menunjukkan solusi, jadi ya.
Graviton

Jawaban:

11

JavaScript , 28 27 26 24 23 byte

a=>b=>(a-=b)?a>b&&a:b+1

Cobalah online!

false menunjukkan tidak ada solusi.

-1 terima kasih @Arnauld

eush77
sumber
Dilakukan dengan baik dan golf dengan baik.
Shaggy
Jadi, untuk menyebutnya, Anda perlu memberi nama fungsi luar, katakan f=..., lalu panggil f(8)(3)? Itu sepertinya sedikit curang? Cara normal untuk memanggil suatu fungsi adalah f(8,3), mana yang akan membuat definisi fungsi Anda lebih lama?
Steve Bennett
3
@SteveBennett Benar, definisinya adalah curried , yang artinya harus dipanggil seperti (8)(3), tetapi ada konsensus tentang PPCG yang diizinkan . Anda tidak harus memberinya nama.
eush77
1
@SteveBennett Sangat lucu bagaimana Anda berpikir 26 vs -15 sama sekali bukan konsensus yang jelas. Semoga berhasil mencoba perselisihan.
eush77
1
@SteveBennett bagaimana konsensus lemah 55 banding 1?
Cyoce
6

MATL , 6 byte

tQ:\=f

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

Pertimbangkan input 8, 2sebagai contoh.

t    % Implicit input. Duplicate                STACK: 8, 8
Q    % Add 1                                    STACK: 8, 9
:    % Range                                    STACK: 8, [1 2 3 4 5 6 7 8 9]
\    % Modulo                                   STACK: [0 0 2 0 3 2 1 0 8]
=    % Implicit input. Equality comparison      STACK: [0 0 1 0 0 1 0 0 0]
f    % Indices of nonzeros. Implicit display    STACK: [3 6]
Luis Mendo
sumber
4

Jelly , 5 byte

‘R⁸%i

Mengembalikan minimal x atau 0 yang valid jika tidak ada.

Cobalah online!

Dennis
sumber
3

Groovy, 48 byte (menggunakan bawaan):

{a,b->Eval.me(a+"g").modInverse(Eval.me(b+"g"))}

Eval.me(...+"g") - Membubuhkan "g" ke input, menjadikannya BigInteger.

modInverse(...) - Melakukan operasi modulo terbalik.


Java 8, 70 byte

{a,b->return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(b));}
Guci Gurita Ajaib
sumber
3

R , 33 28 byte

pryr::f(match(b,a%%1:(a+1)))

Cobalah online!

-4 byte berkat Jarko Dubbeldam.

-1 byte terima kasih kepada Giuseppe.

Kembali NAjika tidak ada solusi. TIO tidak memiliki pryr library yang diinstal, jadi kode pada tautan itu yang digunakan function(a,b).

Nitrodon
sumber
pryr::f(which(a%%1:(a+1)==b)) lebih pendek 4 byte.
JAD
Anda juga dapat menjatuhkan byte lain dengan menggunakan match(b,a%%1:(a+1)), yang mengembalikan NAnilai yang hilang.
Giuseppe
1

Jelly , 11 10 byte

³%_⁴
r‘ÇÐḟ

Program lengkap mengambil dua bilangan bulat positif, adan b, dan mencetak daftar solusi bilangan bulat di antara min(a,b)+1dan max(a,b)+1inklusif.

Cobalah online!

Jonathan Allan
sumber
1

Mathematica 36 Bytes

a_±b_:=Select[Range[9a],a~Mod~#==b&]

Memasukkan:

5 ± 2
9 ± 4
8 ± 2
6 ± 6
8 ± 7
2 ± 4
8 ± 5
10 ± 1

Keluaran:

{3}
{5}
{3, 6}
{7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, \
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, \
42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54}
{}
{}
{}
{3, 9}
Kelly Lowder
sumber
Saat menggunakan operator ASCII yang diperluas ini dalam bentuk biner, mereka membutuhkan ruang di depan saat didefinisikan, jika tidak, parser melempar kesalahan. Jadi harus begitu a_ ±b_. Tapi ini lebih pendek untuk digunakan Casesdaripada Selectfungsi yang tidak disebutkan namanya:Cases[Range[9#],x_/;#~Mod~x==#2]&
Martin Ender
1

Haskell , 33 byte

Gangguan dengan code.hs: out of memory (requested ??? bytes)jika tidak ada solusi (batas waktu di TIO sebelum itu):

a!b=[x|x<-[b+1..],mod(a-b)x<1]!!0

Cobalah online!

Terima kasih di Ørjan Johansen karena menemukan kesalahan!

ბიმო
sumber
Ini memberikan jawaban yang salah untuk kasus uji di mana bmembagi a.
Ørjan Johansen
1

C # (Mono C # compiler) , 57 56 26 byte

Port of Rod's Python menjawab. Terima kasih kepada WW untuk -1 byte.

BESAR terima kasih kepada Kevin Cruijssen untuk -30 byte.

a=>b=>a-b>b?a-b:a==b?a+1:0

Cobalah online!

Epicness
sumber
1
Selamat datang di situs ini! Sepertinya Anda dapat menghapus ruang setelah return.
Wheat Wizard
Selamat datang di PPCG! Untuk jawaban C # non-rekursif itu selalu yang terbaik dan terpendek untuk menggunakan fungsi lambda ( i=>{/*code here*/}). Namun dalam hal ini, karena Anda memiliki 2 input, ini bisa menjadi fungsi lambda yang sedang dikerjakan untuk menyimpan byte tambahan ( a=>b=>{/*code here*/}bukan (a,b)=>{/*code here*/}). Anda juga dapat menghapus tanda kurung di sekitar tanda-if Anda. Secara total, tanpa mengubah fungsionalitas Anda, itu menjadi a=>b=>a-b>b?a-b:a==b?a+1:0 26 byte
Kevin Cruijssen
Juga, jika Anda belum melihatnya, Tips untuk bermain golf di <semua bahasa> dan Tips untuk bermain golf di C # mungkin menarik untuk dibaca. Selamat menikmati! :)
Kevin Cruijssen
Terima kasih semua untuk tipsnya, saya akan mengingatnya saat bermain golf di masa depan
Epicness
0

Pyth, 16 byte

hhx!0mqeQ%hQdShh

Cobalah online!

Semua uji kasus

Mengambil input sebagai [a, b], kesalahan jika tidak ada solusi yang ditemukan. Akan merevisi jika kesalahan tidak diizinkan.

tepuk
sumber
0

Mathematica, 28 byte

Which[#>2#2,#-#2,#==#2,#+1]&
alephalpha
sumber
0

PHP> = 7.1, 51 Bytes

for([,$a,$b]=$argv;++$x<2*$a;)$a%$x!=$b?:print$x._;

Versi Online

Jörg Hülsermann
sumber
0

Aksioma, 147 128 byte

g(a:PI,c:PI):Union(List PI,Stream INT)==(a<c=>[];r:=a-c;r=0=>expand((a+1..)::UniversalSegment INT);[b for b in divisors(r)|b>c])

ungolf itu dan uji

--a%b=c return all possible b
f(a:PI,c:PI):Union(List PI, Stream INT)==
    a<c=>[]
    r:=a-c
    r=0=>expand((a+1..)::UniversalSegment INT)
    [b  for b in divisors(r)|b>c]

(3) -> [[i,j,g(i,j)] for i in [5,9,8,6,8,2,8,10] for j in [2,4,2,6,7,4,5,1]]
   (3)
   [[5,2,[3]], [9,4,[5]], [8,2,[3,6]], [6,6,[7,8,9,10,11,12,13,14,15,16,...]],
    [8,7,[]], [2,4,[]], [8,5,[]], [10,1,[3,9]]]
                                                      Type: List List Any

Ini akan menemukan semua solusi bahkan solusi set yang tak terbatas ...

RosLuP
sumber
0

Pip , 9 byte

a%,a+2@?b

Mengambil dua angka sebagai argumen baris perintah. Menghasilkan solusi terkecil, atau nol jika tidak ada solusi. Cobalah online!

Penjelasan

           a, b are cmdline args (implicit)
  ,a+2     Range from 0 up to but not including a+2
a%         Take a mod each of those numbers
           (Note that a%0 returns nil; it emits a warning, but only if warnings are turned on)
      @?b  Find the index of the first occurrence of b in this list, or nil if it doesn't occur
           Autoprint (implicit)

Misalnya, dengan input dari 8dan 2:

   a+2   10
  ,      [0 1 2 3 4 5 6 7 8 9]
a%       [() 0 0 2 0 3 2 1 0 8]

Indeks berbasis 0 dari kemunculan pertama 2dalam daftar ini adalah 3, yang merupakan solusi kami.

DLosc
sumber
0

J , 14 byte

(->]){-,~=*1+]

Cobalah online!

Terjemahan dari solusi Rod's Python 2 .

Bagaimana itu bekerja

Kasus yang jarang terjadi di mana kode J dapat langsung diterjemahkan ke dalam Python.

(->]){-,~=*1+]  <=>  [(a==b)*(1+b),a-b][a-b>b]
         =*1+]        (a==b)*(1+b)
      -,~            [            ,a-b]
     {                                 [     ]
(->])                                   a-b>b
Bubbler
sumber
0

Japt , 13 byte

UµV ?U>V©U:ÒV

Cobalah online!

Terjemahan dari solusi JS eush77 .

Kode hanya (U-=V)?U>V&&U:-~Vketika ditransmisikan ke JS, di mana Udan Vmerupakan dua nilai input.

Bubbler
sumber
0

Japt , 7 byte

(Akhirnya) Keluaran undefinedjika tidak ada solusi.

@%X¥V}a

Coba di sini

Shaggy
sumber
0

Perl 6 , 23 byte

{grep $^a%*==$^b,^$a+2}

Cobalah online!

Blok kode anonim yang mengembalikan daftar nilai yang mungkin dari 2hinggaa+1

Jo King
sumber
0

ORK , 566 byte

When this program starts:
I have a inputter called I
I have a number called a
I have a number called b
I is to read a
I is to read b
I have a mathematician called M
M's first operand is a
M's second operand is b
M is to subtract
I have a number called n
n is M's result
M's first operand is b
M's second operand is n
M is to compare
I have a scribe called W
If M says it's less then W is to write n
If M says it's less then W is to write "\n"
M's second operand is a
M is to compare
If M says it's equal then W is to write a
If M says it's equal then W is to write a

Cobalah online!

O bjects R K ool. Untungnya, bagaimanapun, saya tidak perlu menggunakan (selain yang built-in) untuk tugas ini.

JosiahRyanW
sumber
0

F #, 40 byte

let m a b=Seq.find(fun x->a%x=b){1..a+1}

Cobalah online!

Cukup mudah. Melempar System.Collections.Generic.KeyNotFoundExceptionjika tidak ada solusi yang dapat ditemukan.

Anda juga dapat memodifikasinya Seq.tryFind, yang akan mengembalikan int option, dengan Nonejika tidak ada solusi yang ditemukan.

Ciaran_McCarthy
sumber
0

> <> , 21 byte

Trik yang sama dengan kebanyakan solusi yang diposting. Pertama, kami menyiapkan semua nilai yang diperlukan pada tumpukan dan kemudian memeriksa perbandingannya.

::r::{-:{)?nr=?!;1+n;

Cobalah online!

PidgeyDigunakanGust
sumber
0

Bisikan v2 , 128 byte

> Input
> Input
>> 1²
>> (3]
>> 1%L
>> L=2
>> Each 5 4
>> Each 6 7
>> L⋅R
>> Each 9 4 8
> {0}
>> {10}
>> 12∖11
>> Output 13

Cobalah online!

Mengembalikan set semua solusi yang mungkin, dan set kosong (mis ) ketika tidak ada solusi.

Bagaimana itu bekerja

Tidak mengherankan, ia bekerja hampir identik dengan sebagian besar jawaban lain: ia menghasilkan daftar angka dan memeriksa masing-masing untuk modulus terbalik dengan argumen.

Jika Anda terbiasa dengan bagaimana struktur program Whispers bekerja, jangan ragu untuk beralih ke garis horizontal. Jika tidak: pada dasarnya, Whispers bekerja pada sistem referensi baris demi baris, mulai dari baris terakhir. Setiap baris digolongkan sebagai salah satu dari dua opsi. Entah itu adalah garis nilad , atau itu adalah garis operator .

Garis Nilad dimulai dengan >, seperti > Inputatau > {0}dan mengembalikan nilai tepat yang diwakili pada garis itu yaitu > {0}mengembalikan set{0}. > Inputmengembalikan baris STDIN berikutnya, dievaluasi jika mungkin.

Jalur operator dimulai dengan >>, seperti >> 1²atau >> (3]dan menunjukkan menjalankan operator pada satu atau beberapa nilai. Di sini, angka-angka yang digunakan tidak mereferensikan angka-angka eksplisit itu, melainkan mereka merujuk nilai pada baris itu. Sebagai contoh, ²adalah perintah kuadrat (nn2), jadi >> 1²tidak mengembalikan nilai12, alih-alih mengembalikan kuadrat dari baris 1 , yang, dalam hal ini, adalah input pertama.

Biasanya, garis operator hanya berfungsi menggunakan angka sebagai referensi, namun Anda mungkin telah memperhatikan garis >> L=2dan >> L⋅R. Kedua nilai ini, Ldan R, digunakan bersama dengan Eachpernyataan. Eachpernyataan bekerja dengan mengambil dua atau tiga argumen, lagi sebagai referensi numerik. Argumen pertama (misalnya 5) adalah referensi ke garis operator yang digunakan fungsi, dan sisanya dari argumen adalah array. Kami kemudian mengulangi fungsi di atas array, di mana Ldan Rdi fungsi mewakili elemen saat ini (s) dalam array yang diulangi. Sebagai contoh:

Membiarkan SEBUAH=[1,2,3,4], B=[4,3,2,1] dan f(x,y)=x+y. Dengan asumsi kita menjalankan kode berikut:

> [1, 2, 3, 4]
> [4, 3, 2, 1]
>> L+R
>> Each 3 1 2

Kami kemudian mendapatkan demonstrasi tentang bagaimana Eachpernyataan bekerja. Pertama, ketika bekerja dengan dua array, kita ritsleting mereka untuk membentukC=[(1,4),(2,3),(3,2),(4,1)] lalu petakan f(x,y) atas setiap pasangan, membentuk susunan terakhir kami D=[f(1,4),f(2,3),f(3,2),f(4,1)]=[5,5,5,5]

Cobalah online!


Cara kerja kode ini

Bekerja berlawanan secara intuitif dengan cara Whispers bekerja, kita mulai dari dua baris pertama:

> Input
> Input

Ini mengumpulkan dua input kami, katakanlah x dan y, dan menyimpannya masing-masing di jalur 1 dan 2 . Kami kemudian menyimpanx2pada baris 3 dan buat rentangSEBUAH: =[1...x2]pada saluran 4 . Selanjutnya, kita lompat ke bagian

>> 1%L
>> L=2
>> Each 5 4
>> Each 6 7

Hal pertama dilaksanakan di sini adalah garis 7 , >> Each 5 4yang iterates baris 5 melewati garis 4 . Ini menghasilkan arrayB: =[saya%x|sayaSEBUAH]dimana Sebuah%bdidefinisikan sebagai modulus dariSebuah dan b.

Kami kemudian mengeksekusi baris 8 , >> Each 6 7yang iterates baris 6 lebihB, menghasilkan sebuah array C: =[(saya%x)=y|sayaSEBUAH].

Untuk input x=5,y=2, kita punya SEBUAH=[1,2,3,...,23,24,25], B=[0,1,2,1,0,5,5,...,5,5] dan C=[0,0,1,0,0,...,0,0]

Kami kemudian melompat ke bawah

>> L⋅R
>> Each 9 4 8

yang merupakan contoh kita dari Eachpernyataan diad . Di sini, fungsi kami adalah garis 9 yaitu >> L⋅Rdan dua array kami adalahSEBUAH dan C. Kami mengalikan setiap elemen dalamSEBUAH dengan elemen yang sesuai di C, yang menghasilkan array, E, di mana setiap elemen bekerja dari hubungan berikut:

Esaya={0Csaya=0SEBUAHsayaCsaya=1

Kami kemudian berakhir dengan array yang terdiri dari 0dan moduli kebalikan dari x dan y. Untuk menghapus0s, kami mengonversi array ini ke set ( >> {10}), lalu mengambil perbedaan set antara set ini dan{0}, menghasilkan, lalu mengeluarkan, hasil akhir kami.

caird coinheringaahing
sumber
-1

C #, 53 byte (83 dengan judul fungsi)

static int F(int a, int b){
    for(int i=1;i<=a+1;i++){if(a%i==b)return i;}return 0;
}

Cobalah secara Online

Pertama coba di codegolf. Mungkin bukan bahasa terbaik untuk digunakan, atau pengkodean yang paling efisien.

Alex
sumber
5
Hapus spasi putih yang tidak perlu untuk menghemat sekitar 10 byte atau lebih
Tn. Xcoder