Diberi nilai prima Plebih besar dari itu 10, program atau fungsi Anda harus mencari tahu aturan pembagiannya x, yang didefinisikan sebagai bilangan bulat dengan nilai absolut terkecil yang menghasilkan kelipatan dari prime asli ketika dikalikan dengan digit terakhir dari prime dan ditambahkan ke sisa aslinya utama.

Contoh

Diberikan input 31, digit terakhir adalah 1dan sisanya nomor tersebut 3. Dengan demikian program Anda harus menemukan integer xdengan nilai absolut minimum sedemikian rupa sehingga 1*x + 3merupakan kelipatan 31. Dalam hal ini, x=-3berfungsi, sehingga program atau fungsi akan kembali -3.

Diberikan input 1000003, digit terakhir adalah 3dan sisanya nomor tersebut 100000. Dengan demikian program Anda akan menemukan x=300001karena 3*300001+100000 = 1000003yang merupakan kelipatan 1000003.

Latar Belakang Matematika

Nilai xdapat digunakan sebagai tes keterbagian. Jika angka Ndapat dibagi dengan P, kemudian menambahkan xkali digit terakhir dari Nsisanya Nakan menghasilkan kelipatan Pjika dan hanya jika Ndapat dibagi dengan Pdi tempat pertama.

Karena P=11, kita dapatkan x=-1, yang setara dengan aturan pembagian yang terkenal untuk 11: angka dapat dibagi dengan 11selisih selisih digitnya dapat dibagi 11.

Aturan

• Output mungkin dalam bentuk apa pun yang secara jelas mengkodekan tanda dan nilai output.
• Input prima akan berada di antara 10 dan 2 ^ 30.
• Anda tidak perlu menangani jika inputnya tidak prima atau tidak dalam jangkauan.
• Anda tidak perlu menangani jika keduanya xdan -xmerupakan output yang valid (tidak boleh terjadi).
• Brute force diizinkan, tetapi solusi yang lebih kreatif dihargai.
• Ini adalah kode-golf , sehingga kode terpendek dalam setiap bahasa menang! Jangan biarkan jawaban dalam bahasa golf menghalangi Anda untuk memposting dalam bahasa lain.

Uji Kasus

Input   Output
11  -1
13  4
17  -5
19  2
23  7
29  3
31  -3
37  -11
41  -4
43  13
47  -14
53  16
59  6
61  -6
67  -20
71  -7
73  22
79  8
83  25
89  9
97  -29
101 -10
103 31
107 -32
109 11
113 34
127 -38
131 -13
1000003 300001
2000003 600001
2999999 300000
9999991 -999999

JavaScript (ES6), 32 25 23 byte

f=
n=>(3/(n%5*2-5)*n+1)/10

<input type=number min=1 oninput=o.textContent=this.value%5*(this.value%2)?f(this.value):``><pre id=o>

3/(n%5*2-5) akan ditulis 9/n(mod -10) jika saya memiliki akses ke divisi modulo seimbang. Sunting: Disimpan 2 byte berkat @EgorSkriptunoff

Python 2 , 27 byte

lambda n:(n%5*2-5^2)*n/10+1

Cobalah online!

Operasi dilakukan kiri ke kanan: (((n%5)*2)-5)^2.

Saya menggunakan forcer brit aritmatika saya untuk menemukan ekspresi n%5*2-5^2untuk melakukan {1:-1,3:3,2:-3,4:1}[k], mengambil invers negatif residu mod 5 ke dalam jangkauan [-2..2].

Jelly ,10 8 byte

,N⁵æiAÞḢ

Cobalah online!

Penjelasan

,N       Get [Input, -Input].
⁵æi      Modular inverse of 10 mod each of [Input, -Input].
AÞ       Sort by absolute value.
Ḣ        First.

Brachylog , 14 byte

∧.ℤ≜×₁₀-₁;?%0∧

Cobalah online!

Python 2 , 69 54 53 byte

Edit: -15 byte terima kasih kepada @ Mr.Xcoder

Sunting: -1 byte dengan menggunakan rekursi

f=lambda a,x=-1:(a%10*x+a/10)%a and f(a,-x-(x>0))or x

Cobalah online!

Python 2 , 31 29 27 byte

lambda n:3/(n%5*2-5)*n/10+1

Cobalah online!

Japt , 16 9 byte

Terlalu banyak byte yang disimpan berkat pengamatan oleh @xnor

_*AÉ vU}c

Uji secara online! Butuh beberapa detik pada input yang lebih besar.

Penjelasan

_  *AÉ  vU}c    Implicit: U = input integer
Z{Z*A-1 vU}c    Ungolfed
Z{        }c    Loop through each integer Z in [0, -1, 1, -2, ...] and yield the first where
  Z*A             Z times 10
     -1           minus 1
        vU        is divisible by the input.
                Implicit: output result of last expression

Java 8, 23 21 byte

n->3/(n%5*2-5)*++n/10

Pelabuhan @ Neil javascrip (ES6) jawaban 's , tapi -2 byte berkat @Nevay karena lantai implisit bilangan bulat.

Coba di sini.

Pyke , 12 byte

3Q5%}5-f*hTf

Coba di sini!

Pyth , 14 byte

h/*x-y%QK5K2QT

Coba di sini.

Python 2 , 44 43 byte

(Coret 44 masih 44.) Terima kasih kepada Fireflame241 karena telah menghemat satu byte!

P=input();i=P/3
while i*10%P-1:i-=1
print i

Cobalah online!

Hanya ada satu angka di antara 0dan P-1yang merupakan kebalikan dari 10. Tetapi jika kebalikan itu uterjadi lebih besar dari P/2, maka (u-P)juga kebalikannya, dan memiliki nilai absolut yang lebih kecil dari u. Jadi ternyata kami benar-benar mencari angka unik di xantara -P/2dan P/2yang merupakan kebalikannya 10.

Kode di atas melakukan hal itu, mulai dari (lantai) P/2, dan melangkah ke bawah hingga kebalikannya tercapai. Ini harus terjadi untuk beberapa nomor lebih besar dari -P/2asalkan Pprima lebih besar dari 10. Lebih tepatnya, itu akan berakhir jika dan hanya jika Pmerupakan coprime 10.

Sunting: Ini sebenarnya ternyata xdijamin antara -P/3dan P/3, jadi versi saat ini dimulai pada P/3dan turun dari sana. Lihat bagian berlabel Improved Bound untuk penjelasannya.

Penjelasan matematis

Tidak segera jelas bagi saya mengapa tes keterbelahan bekerja. Inilah penjelasan, kalau-kalau ada orang lain yang bertanya-tanya.

Membiarkan Pmenjadi prima, lebih besar dari 10, yang digit terakhirnya adalah b. Jadi

P = 10a + b

dimana a > 0, dan 0 <= b < 10. Bahkan badalah baik 1, 3, 7, atau 9, karena lebih besar perdana dari 10keharusan akhir di salah satu digit tersebut.

Sekarang misalkan bx + a = 0 (mod P). Kemudian

a = -bx (mod P)

10a + b = 10(-bx) + b (mod P)

0 = 10(-bx) + b (mod P)

0 = b(1 - 10x) (mod P)

Karena Pprima, bilangan bulat mod Padalah domain integral . Jadi b = 0 (mod P), atau 1 - 10x = 0 (mod P).

Kita tahu 0 <= b < 10 < P, jadi kalau b = 0 (mod P)begitu b = 0. Tapi kami mengatakan byang baik 1, 3, 7, atau 9, jadi ini adalah mustahil. Karena itu 1 - 10x = 0 (mod P), begitu 10x = 1 (mod P). Dengan kata lain, xadalah kebalikan dari 10, modulo P.

Sekarang anggaplah Nadalah bilangan bulat non-negatif yang digit terakhirnya d, jadi N = 10c + d. Kami memiliki rantai pernyataan yang setara:

10c + d = 0 (mod P)

<==> 10xc + dx = 0 (mod P)

<==> c + dx = 0 (mod P)

QED.

Kegunaan?

Saya juga bertanya-tanya apakah tes keterbagian (diberikan N = 10c + d, ganti Ndengan dx + c) akan benar-benar produktif dalam praktik. Atau setidaknya, apakah itu dapat diandalkan menggantikan Ndengan angka yang lebih kecil dari N(dalam nilai absolut)?

Misalkan N = 10c + d, di mana c >= 0dan 0 <= d < 10. Oleh karena itu 10c = N - d <= N. Dengan ketimpangan segitiga,

|c + dx| <= |c| + |dx| = c + d|x| <= N/10 + d|x|

< N/10 + 10|x| <= N/10 + 10P/2 = N/10 + 5P

Jadi kalau 5P <= 9N/10begitu |c + dx| < N.

Khususnya, jika N >= 6P, maka |c + dx| < N. Dengan demikian, mengingat Pkita mulai dengan menghitung 2P, 3P, ..., 6P, bersama dengan x. Kemudian diberikan N, kami menjalankan uji dibagi berulang kali sampai kita mencapai angka kurang dari atau sama dengan 6P, dan memeriksa apakah hasilnya adalah salah satu nomor 0, P, 2P, ..., 6P.

(Tentu saja, setiap kali kita mencapai angka negatif, kita menggantinya dengan nilai absolutnya, yang baik-baik saja karena qdapat dibagi dengan Pjika dan hanya jika (-q)ada.)

Peningkatan Terikat

Saya perhatikan bahwa |x|/Psepertinya tidak pernah dekat 1/2. Bahkan sepertinya itu selalu kurang dari 1/3... atau setelah diperiksa lebih dekat, selalu sangat dekat dengan salah satu 1/10atau 3/10. Yang terbesar yang pernah ada tampaknya 4/13(yang terjadi ketika P=13danx=4 ). Mengapa ini terjadi?

Membiarkan umenjadi bilangan bulat dan anggap itu 10u = kP + 1untuk bilangan bulat k, jadi uadalah kebalikan dari 10, modulo P. Kemudian kita juga tahu bahwa kitu relatif prima 10, karena k(-P)setara dengan 1modulo 10.

Sekarang, kita tahu bahwa invers dari 10modulo Psemuanya berbeda berdasarkan kelipatan P, sehingga kita dapat mengambil bilangan bulat udan menambah atau mengurangi kelipatan Psesuka hati, dan hasilnya akan selalu menjadi kebalikan dari 10modulo P. Misalkan kita memilih untuk mengurangi Pdari u: kita mendapatkan

10(u - P) = 10u - 10P = kP + 1 - 10P

10(u - P) = (k - 10)P + 1

Dengan kata lain, penurunan (masing-masing, meningkatkan) uoleh Pbersesuaian dengan penurunan (peningkatan) koleh 10. Kami ingin menambah / mengurangi kelipatan dari Pdari usampai sisi kiri diminimalkan dalam nilai absolut; tetapi sisi kiri diminimalkan tepat ketika sisi kanan diminimalkan, dan oleh karena itu kami ingin menambahkan / mengurangi 10dari ksampai sisi kanan diminimalkan dalam nilai absolut.

Tapi kita tahu bahwa ini akan terjadi ketika kadalah antara -5dan 5, dan karena itu (karena krelatif prima untuk 10) berarti ini kadalah baik -3, -1, 1, atau 3. (Ini adalah isi dari komentar @ Neil di bawah OP. Terima kasih, Neil! )

Jadi ketika |u|diminimalkan (yaitu, u=x), kita akan memiliki x/P = u/P = k/10 + 1/(10P), di mana kadalah baik -3, -1, 1, atau 3. Oleh karena itu |x|/P <= 3/10 + 1/(10P). Setara |x| <= (3P + 1)/10,.

Lebih jauh, ketidaksetaraan ini sangat ketat pada P=11, karena pada saat P=11kita miliki x=-1dan k=-1. Yang terkecil Pyang dimiliki kesetaraan adalah P=13(di mana x=4dan k=3).

Oleh karena itu yang terbesar yang |x|/Ppernah didapat adalah 3/10 + 1/(10*13), karena P=13merupakan perdana pertama yang kita miliki k=3, dan di antara mereka yang memiliki k=3, 1/(10P)istilah itu terbesar ketika Pterkecil (yaitu, pada P=13). Karena itu, untuk semua P, kami juga punya |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. Ini menjelaskan mengapa dalam kode di atas kita dapat menginisialisasi i = P/3daripada harus mulai P/2.

Selanjutnya, batas-batas di bagian Kegunaan di atas sekarang dapat ditingkatkan.

Lemma : Biarkan di N = 10c + dmana c > 0dan 0 <= d <= 9. Lalu c + d|x| < N/10 + 9(3P + 1)/10. (Perhatikan ketimpangan yang ketat.)

Bukti Lemma: berdasarkan kasus. Kasus I:, d = 0jadi N = 10c. Lalu c + d|x| = c = N/10 < N/10 + 9(3P + 1)/10.

Kasus II: 0 < d <= 9. Lalu 10c = N - d < N, begitu c < N/10. Oleh karena itu c + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10. QED.

Jadi, jika N > 3P(dan N = 10c + dseperti sebelumnya), maka

3P + 1 <= N

9(3P + 1)/10 <= 9N/10

N/10 + 9(3P + 1)/10 <= N

c + d|x| < N/10 + 9(3P + 1)/10 <= N

Jadi, kalau N > 3Pbegitu c + d|x| < N.

Karena itu, kita hanya perlu menemukan P, 2Pdan 3P, bersama dengan x. Mengingat N > 0, sementara N > 3P, kami ganti Ndengan |c + dx|, yang berkurang N. Akhirnya kita akan mendapatkannya N <= 3P; pada saat itu kami berhenti dan memeriksa apakah Nsama dengan salah satu nomor 0, P, 2P, atau 3P.

Kita tidak bisa berbuat lebih baik daripada 3Psecara umum. Misalnya, anggaplah P = 13dan N = 39begitu x = 4. Kemudian ganti Ndengan dx + c = 9(4) + 3daun Ntidak berubah.

Ruang putih , 92 byte

Perhatikan bahwa sintaksis bahasa ini hanya terdiri dari spasi putih , sehingga setiap karakter spasi putih telah diawali di sini dengan S, T, atau L (masing-masing sesuai dengan Space, Tab, dan Linefeed). Ini dapat dihapus tanpa kehilangan fungsionalitas, tetapi mereka termasuk di sini untuk menampilkannya dengan benar.

S S S L
T   L
T   T   S S S L
T   T   T   S L
S S S S T   T   L
T   S S L
S L
T   S S S T S T L
T   S T T   S L
S T S S S S S S T   S T L
T   S S T   T   S T S S S S T   L
T   S S S S S S T   S T S L
T   S T S T L
S T L
L
L
.

Cobalah online!

Japt , 14 byte

Terinspirasi oleh solusi Neil .

Ì*2%E-3 *UÄ /A

Uji secara online!

Penjelasan:

  Ì  *2%E-3 *UÄ  /A
((UgJ*2%E-3)*U+1)/A
  U                  // Implicit U = Input
   gJ                // Get the char at index -1 (last char)
     *2              // Multiply by 2
       %E            // Mod 14
         -3          // Minus 3
            *U+1     // Multiply by U+1
                 /A  // Divided by 10 

Pyke , 10 byte

~IIT*tR%)h

Coba di sini!

~I         -   Integers
  I     )  -  filter(^, not v)
   T*t     -    ^ *10 -1
      R%   -   input % ^
         h - ^[0]

Excel, 27 byte

=0.3/(MOD(A1,5)*2-5)*A1+0.1

Dapat dimasukkan ke dalam Cell sebagai

=.3/(MOD(A1,5)*2-5)*A1+.1

selama 25 byte, tetapi pembaruan otomatis Excel.