Sekitar setahun yang lalu Anda diminta untuk menemukan bilangan prima XOR . Ini adalah angka yang hanya faktor 1 dan diri mereka sendiri ketika melakukan perkalian XOR di basis 2 . Sekarang akan sedikit membumbui hal-hal.
Kita akan menemukan bilangan prima XOR di basis -2
Konversi ke Basis -2
Basis -2 sangat mirip dengan basis lainnya. Tempat paling kiri adalah tempat 1s (1 = (-2) 0 ), di sebelah tempat itu -2s (-2 = (-2) 1 ), di sebelahnya adalah tempat 4s (4 = (-2) ) 2 ), dan seterusnya dan seterusnya. Perbedaan besar adalah bahwa angka negatif dapat direpresentasikan dalam basis -2 tanpa tanda negatif.
Berikut beberapa contoh konversi:
Decimal | Base -2
-----------------
6 | 11010
-7 | 1001
12 | 11100
-15 | 110001
Selain XOR di Basis -2
Tambahan XOR di Basis -2 hampir sama dengan penambahan XOR dalam biner. Anda cukup mengonversi angka menjadi Basis -2 dan XOR setiap digit di tempat. (Ini sama dengan penambahan tanpa membawa)
Berikut adalah contoh langkah demi langkah:
(Kami akan menggunakan simbol +'
untuk mengindikasikan penambahan XOR -2 Base)
Mulai di basis 10:
6 +' -19
Konversikan ke basis -2:
11010 +' 10111
Tambahkan tanpa membawa:
11010
+' 10111
---------
01101
Ubah hasil Anda kembali menjadi basis 10:
-3
Perkalian XOR dalam Basis -2
Sekali lagi perkalian XOR dalam basis -2 hampir sama dengan perkalian XOR dalam biner. Jika Anda tidak terbiasa dengan perkalian XOR di basis 2 ada penjelasan yang sangat baik di sini saya sarankan Anda melihatnya dulu.
Perkalian XOR di Basis -2 sama dengan melakukan perkalian panjang di basis -2 kecuali ketika sampai pada langkah terakhir alih-alih menambahkan semua angka dengan tradisional yang +
Anda gunakan seperti yang +'
kita tentukan di atas.
Berikut adalah contoh yang dikerjakan di bawah ini:
Mulai dalam desimal:
8 *' 7
Konversikan ke Basis -2:
11000 *' 11011
Buat divisi panjang:
11000
*' 11011
---------
Lipat gandakan angka pertama dengan setiap tempat di angka kedua
11000
*' 11011
------------
11000
11000
0
11000
11000
Tambahkan semua hasil menggunakan basis -2 XOR tambahan
11000
*' 11011
-------------
11000
11000
0
11000
+' 11000
-------------
101101000
Ubah hasilnya kembali menjadi desimal:
280
Tantangan
Tantangan Anda adalah memverifikasi apakah suatu angka adalah XOR prime di basis -2. Angka adalah prima XOR dalam basis -2 jika pasangan integer yang menggandakannya dalam basis adalah 1 dan itu sendiri. (1 bukan prima)
Anda akan menerima angka dan mengeluarkan boolean, benar jika inputnya adalah XOR prime di basis -2 falsy sebaliknya.
Solusi akan diberi skor dalam byte dengan mencapai jumlah byte terendah sebagai tujuannya.
Uji kasus
Berikut ini adalah semua bilangan prima XOR di basis -2:
-395
-3
-2
3
15
83
Berikut ini bukan bilangan prima XOR pada basis -2:
-500
-4
0
1
258
280
sumber
258
tampaknya sama-2 *' -129 = 10 *' 10000011
Jawaban:
Mathematica,
156101 byteSeperti yang dinyatakan di sini , ini berfungsi karena perkalian XOR pada dasarnya adalah perkalian dalam cincin polinomial F_2.
Penjelasan
Mulai dengan
{input}
. Ganti nomor berulang kalia
(kecuali 0 dan 1) dengana
mod 2 dan prepend -floor (a
/ 2), hingga tidak berubah. Ini menghitung input pada basis -2.Buat polinomial menggunakan digit dari angka -2, menggunakan
x
sebagai variabel. misalnya{1, 1, 0}
->x^2 + x
Periksa apakah polinomial yang dihasilkan dapat direduksi, dengan modulus 2.
Versi lama (156 byte)
Daftar bilangan prima
Berikut daftar basis -2 XOR bilangan prima antara -1000 dan 1000 (pastebin)
sumber