Tugas Anda adalah memberikan dua angka bilangan bulat, a
dan b
menghitung inversi multiplikatif modular dari modulo b, jika ada.
Kebalikan modular dari a
modulo b
adalah angka c
sedemikian rupa sehingga ac ≡ 1 (mod b)
. Angka ini adalah modulo unik b
untuk setiap pasangan a
dan b
. Ini ada hanya jika pembagi umum terbesar dari a
dan b
adalah 1
.
The halaman Wikipedia untuk invers perkalian modular dapat dikonsultasikan jika Anda memerlukan informasi lebih lanjut tentang topik.
Masukan dan keluaran
Input diberikan sebagai dua bilangan bulat atau daftar dua bilangan bulat. Program Anda harus menampilkan angka tunggal, invers multiplikatif modular yang ada dalam interval 0 < c < b
, atau nilai yang menunjukkan tidak ada invers. Nilai dapat berupa apa saja, kecuali angka dalam kisaran (0,b)
, dan mungkin juga merupakan pengecualian. Namun nilai harus sama untuk kasus-kasus di mana tidak ada invers.
0 < a < b
dapat diasumsikan
Aturan
- Program harus selesai pada titik tertentu, dan akan menyelesaikan setiap kasus uji dalam waktu kurang dari 60 detik
- Celah standar berlaku
Uji kasus
Test case di bawah ini diberikan dalam format, a, b -> output
1, 2 -> 1
3, 6 -> Does not exist
7, 87 -> 25
25, 87 -> 7
2, 91 -> 46
13, 91 -> Does not exist
19, 1212393831 -> 701912218
31, 73714876143 -> 45180085378
3, 73714876143 -> Does not exist
Mencetak gol
Ini adalah kode golf, jadi kode terpendek untuk setiap bahasa menang.
Ini dan ini adalah pertanyaan yang serupa, tetapi keduanya menanyakan situasi tertentu.
sumber
Jawaban:
Mathematica, 14 byte
Wajib Matematika dibangun :
Ini adalah fungsi yang mengambil dua argumen (
a
danb
), dan mengembalikan kebalikan dari mod b jika ada. Jika tidak, itu mengembalikan kesalahanModularInverse: a is not invertible modulo b.
.sumber
JavaScript (ES6),
79736261 byteMengembalikan
false
jika invers tidak ada.Ia menggunakan algoritma Euclidean yang diperluas dan menyelesaikan semua kasus uji hampir secara instan.
Uji kasus
Tampilkan cuplikan kode
sumber
f(x,y)
selalu diuraikan sebagai panggilan fungsi, kecuali jika secara eksplisit didahului olehfunction
kata kunci. Fungsi panah anonim, di sisi lain, dinyatakan sebagai(x,y)=>something
danf=(x,y)=>something
menetapkan fungsi kef
variabel.Jelly , 2 byte
Cobalah online!
Ini menggunakan builtin untuk invers modular, dan mengembalikan 0 tanpa invers modular.
Jelly , 7 byte
Cobalah online!
Keluaran set kosong (direpresentasikan sebagai string kosong) tanpa pembalikan modular. Kehabisan memori pada TIO untuk kasus uji terbesar, tetapi harus bekerja mengingat memori yang cukup.
Bagaimana itu bekerja
Jika Anda ingin bekerja untuk kasing yang lebih besar, coba versi ini (yang relatif tidak dipisahkan), yang membutuhkan lebih banyak waktu daripada memori:
Jelly, 9 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Python 2 , 34 byte
Cobalah online!
Fungsi rekursif yang memberikan
True
untukprint f(1,2)
, yang saya percaya dapat diterima, dan kesalahan untuk input tidak valid.Kami berusaha untuk menemukanx dalam a ⋅ x ≡ 1( modb ) .
PengambilanmodSebuah - 1 ≡ k ⋅ b( moda ) - k ⋅ b ≡ 1( moda ) k
sumber
Angka R + , 15 byte
pengembalian
NA
untuk yanga
tanpa mod inversb
.R-Fiddle untuk mencobanya!
R , 33 byte (tidak bersaing)
Ini akan gagal pada ukuran yang sangat besar
b
karena ia sebenarnya membuat vektor32*b
bit ukuran .Cobalah online!
Pengembalian
integer(0)
(daftar kosong) untuk yanga
tanpa mod terbalikb
.sumber
Mathematica, 18 byte
memasukkan
sumber
Python 2 ,
514954535149 byteTerima kasih -1 byte ke officialaimm
-1 byte terima kasih kepada Shaggy
Cobalah online!
Mencetak
0
saat tidak ada solusi.sumber
0
untuka=1
danb=2
; dari kasus uji, seharusnya keluar1
.2, 1
31,73714876143
.Japt ,
98 byteMengambil input dalam urutan terbalik. Output
-1
tanpa kecocokan. Craps keluar saat bilangan bulat lebih besar semakin besar.Menguji
sumber
73714876143,31
tampaknya menghasilkan kesalahan kehabisan memori pada Firefox (dan menabrak Chromium). Saya rasa ini bukan jawaban yang valid.Python 3 + gmpy , 23 byte
Saya tidak berpikir itu bisa lebih pendek dengan Python.
Cobalah online! (tidak akan berfungsi jika gmpy Anda belum diinstal)
sumber
Python 3 , 49 byte
Cobalah online!
Python 3 , 50 byte
Cobalah online!
Ini melempar
IndexError: list index out of range
kalau-kalau tidak ada invers multiplikatif modular, karena diizinkan oleh aturan.sumber
31,73714876143
dalam 60 detik (pada TIO).8 , 6 byte
Kode
Penjelasan
invmod
adalah kata ke 8 yang menghitung nilai kebalikan daria
, modulob
. Ia mengembalikannull
pada overflow atau kesalahan lainnya.Penggunaan dan uji kasus
sumber
Pari / GP , 22 byte
Melempar kesalahan saat tidak ada terbalik.
Cobalah online!
sumber
J , 28 byte
Cobalah online!
Penggunaan teorema Euler . Mengembalikan 0 jika kebalikannya tidak ada.
Penjelasan
sumber
Pyth , 10 byte
3 byte disimpan berkat @Jakube .
Coba di sini!
Kembali
-1
tanpa pembalikan multiplikasi.Rincian Kode
Pyth ,
1513 byteMelempar pengecualian jika tidak ada inversi multiplikasi.
Coba di sini!
Pyth , 15 byte
Ini menambahkan banyak byte untuk menangani kasus di mana tidak ada nomor tersebut. Program ini dapat dipersingkat secara signifikan jika kasus itu tidak perlu ditangani:
Coba di sini!
sumber
KExm%*QdKK1
xm%*szdQQ1
C (gcc) , 115 byte
Cobalah online!
Algoritma Euclidean yang diperluas, versi rekursif
C (gcc) , 119 byte
Cobalah online!
Algoritma Euclidean yang diperluas, versi iteratif
sumber
C (gcc) ,
48 110104 byteCobalah online!
Ini harus bekerja dengan semua input (yang cocok dalam waktu lama) dalam 60 detik.
Edit. Saya sudah menyalahgunakan
n
variabel jadi saya mungkin juga berasumsi bahwa gcc menempatkan tugas pertama di%rax
.sumber
f(3,1000001)
mengembalikan 717, yang jelas-jelas tidak masuk akal (jawaban yang benar adalah 333334). Juga, bahkan jika bug ini diperbaiki dengan menggunakan tipe integer yang lebih luas, pendekatan brute-force ini pasti akan habis untuk beberapa kasus uji yang lebih besar yang diberikan dalam tantangan.Python 2 + sympy, 74 byte
Cobalah online!
Diambil dari kode sumber Jelly.
sumber
Aksioma, 45 byte
0 untuk kesalahan lain kembalikan z dengan x * z Mod y = 1
sumber
Python 2 , 52 byte
-3 byte terima kasih kepada Tn. Xcoder.
Cobalah online!
Output
False
tanpa solusi dan kesalahan keluar karenab
semakin besar.TIO tertanam
Saya hanya menguji iframe di Stack Snippets dan mereka bekerja sangat fantastis.
Tampilkan cuplikan kode
sumber
i*a%b
bisa0
?(31,73714876143)
.JavaScript (ES6),
42413938 byteOutput
false
tanpa kecocokan. Akan menimbulkan kesalahan overflow karena angka kedua terlalu besar.sumber
Jelly , 27 byte
Cobalah online!
Menggunakan teorema Euler dengan eksponensial modular. Karena Jelly tidak memiliki builtin untuk melakukan eksponensial modular, itu harus diimplementasikan, dan butuh sebagian besar byte.
sumber
Aksioma, 99 byte
menggunakan fungsi h (); h (a, b) mengembalikan 0 jika kesalahan [tidak ada kebalikan] jika tidak mengembalikan z sedemikian sehingga * z mod b = 1 Ini akan baik-baik saja walaupun argumen negatif ...
ini akan menjadi fungsi egcd () umum yang mengembalikan daftar int (sehingga mereka juga bisa negatif)
beginilah cara menggunakannya
saya menemukan basis algo di internet dari https://pastebin.com/A13ybryc
sumber