Hitung kebalikan dari modulo integer 100000000003

21

Tugasnya adalah sebagai berikut. Diberikan bilangan bulat x(sedemikian rupa sehingga xmodulo 100000000003tidak sama dengan 0) yang disajikan ke kode Anda dengan cara apa pun yang Anda rasa nyaman, hasilkan bilangan bulat lain y < 100000000003sehingga (x * y) mod 100000000003 = 1.

Kode Anda harus memakan waktu kurang dari 30 menit untuk berjalan pada mesin desktop standar untuk setiap input xsedemikian rupa |x| < 2^40.

Uji kasus

Input: 400000001. Output: 65991902837

Input: 4000000001. Output: 68181818185

Input: 2. Output: 50000000002

Input: 50000000002. Output: 2.

Input: 1000000. Output: 33333300001

Batasan

Anda tidak boleh menggunakan pustaka atau fungsi bawaan apa pun yang melakukan modulo aritmatika (atau operasi terbalik ini). Ini berarti Anda bahkan tidak dapat melakukannya a % btanpa menerapkan %sendiri. Anda dapat menggunakan semua fungsi built-in aritmatika non-modulo lainnya.

Pertanyaan serupa

Ini mirip dengan pertanyaan ini meskipun semoga cukup berbeda untuk tetap menarik.

isaacg
sumber
Jadi a- (a / b) * b baik-baik saja?
user253751
@immibis Itu terlihat bagus.
tag: kode terbatas?
Felipe Nardi Batista
1
Apa yang spesial 100000000003? (hanya ingin tahu)
NoOneIsHere
1
@ Lembik Dalam hal ini, dapatkah Anda menyebutkan persyaratan bahwa y <100000000003 dalam pertanyaan?
isaacg

Jawaban:

16

Pyth, 24 byte

L-b*/bJ+3^T11Jy*uy^GT11Q

Suite uji

Ini menggunakan fakta bahwa a ^ (p-2) mod p = a ^ -1 mod p.

Pertama, saya secara manual menerapkan kembali modulus, untuk kasus spesifik mod 100000000003. Saya menggunakan rumus a mod b = a - (a/b)*b, di mana /pembagian lantai. Saya menghasilkan modulus dengan 10^11 + 3, menggunakan kode +3^T11, lalu menyimpannya J, kemudian menggunakan rumus ini dan di atas untuk menghitung b mod 100000000003 dengan -b*/bJ+3^T11J. Fungsi ini didefinisikan sebagai ydengan L.

Selanjutnya, saya mulai dengan input, kemudian membawanya ke kekuatan kesepuluh dan mengurangi mod 100000000003, dan ulangi ini 11 kali. y^GTadalah kode yang dieksekusi di setiap langkah, dan uy^GT11Qmenjalankannya 11 kali dimulai dengan input.

Sekarang saya sudah Q^(10^11) mod 10^11 + 3, dan saya ingin Q^(10^11 + 1) mod 10^11 + 3, jadi saya kalikan dengan input dengan *, kurangi mod 100000000003 dengan yang yterakhir kali, dan output.

isaacg
sumber
Memang sangat bagus!
Saya
1
@Lembik aku akan melakukannya, tapi pendapat bisa berbeda. Ini tantangan Anda, buat itu bekerja seperti yang Anda inginkan.
isaacg
Cara pertanyaan ditulis, ada kemungkinan Anda bisa membatalkan pengurangan akhir, meskipun saya meminta klarifikasi apakah diperlukan hasil <100000000003.
Ørjan Johansen
9

Haskell , 118 113 105 101 byte

Terinspirasi dari solusi ini .

-12 dari Ørjan Johansen

p=10^11+3
k b=((p-2)?b)b 1
r x=x-div x p*p
(e?b)s a|e==0=a|1<2=(div e 2?b$r$s*s)$last$a:[r$a*s|odd e]

Cobalah online!

Haskell , 48 byte

Menulis ulang solusi ini . Walaupun cukup cepat untuk vektor uji, solusi ini terlalu lambat untuk input lainnya.

s x=until(\t->t-t`div`x*x==0)(+(10^11+3))1`div`x

Cobalah online!

bartavelle
sumber
Luar biasa! Saya suka eksponensial dengan pendekatan kuadrat.
isaacg
Solusi terpendek akan menjadi seperti Coba online! tapi saya rasa kinerjanya tidak bisa diterima ...
bartavelle
(1) Ini lebih pendek untuk membuat goperator (e?b)a s|...(2) Jika Anda beralih adan skemudian Anda dapat membuat !sebuah non -operator dan inline yke dalamnya. (3) Anda dapat menyingkirkan yang mahal wheredengan lasttrik, dengan biaya duplikasi z. Cobalah online!
Ørjan Johansen
Nah, itu trik yang bagus!
bartavelle
Oh, dan |e==0=asingkirkan duplikasi sial itu.
Ørjan Johansen
6

Brachylog , 22 byte

∧10^₁₁+₃;İ≜N&;.×-₁~×N∧

Cobalah online!

Ini membutuhkan waktu sekitar 10 menit untuk 1000000dengan versi kode yang sedikit berbeda (dan lebih lama) yang persis dua kali lebih cepat (hanya memeriksa nilai positif İalih-alih positif dan negatif). Karenanya ini membutuhkan waktu sekitar 20 menit untuk menyelesaikan input tersebut.

Penjelasan

Kami hanya menjelaskan itu Input × Output - 1 = 100000000003 × an integer, dan biarkan aritmatika kendala menemukan Outputbagi kita.

∧10^₁₁+₃                   100000000003
        ;İ≜N               N = [100000000003, an integer (0, then 1, then -1, then 2, etc.)]
            &;.×           Input × Output…
                -₁         … - 1…
                  ~×N∧     … = the product of the elements of N

Kami secara teknis tidak memerlukan pelabelan eksplisit , namun jika kami tidak menggunakannya, tidak akan memeriksa kasus N = [100000000003,1](karena sering tidak berguna), artinya ini akan sangat lambat untuk input 2misalnya karena akan perlu menemukan bilangan bulat terkecil kedua bukan yang pertama.

Fatalisasi
sumber
1
Wow, saya tidak akan pernah mengharapkan aritmatika kendala untuk melakukan itu. Luar biasa!
isaacg
1
@isaacg Kecepatan ini sayangnya sepenuhnya tergantung pada nilai İ, jadi ini masih sangat lambat untuk produk besar.
Fatalkan tanggal
Memperbarui pertanyaan. Apakah kode Anda selalu memakan waktu kurang dari 30 menit?
6

Python, 53 51 49 58 53 49 byte

-2 bytes berkat orlp
-2 bytes berkat officialaimm
-4 bytes berkat Felipe Nardi Batist
-3 bytes berkat isaacg
-1 byte berkat Ørjan Johansen
-2 bytes berkat Federico Poloni

x=input()
t=1
while t-t/x*x:t+=3+10**11
print t/x

Cobalah secara Online!

Butuh saya ~ 30 menit untuk menemukan yang ini. Solusi saya adalah mulai dengan angka pertama yang akan mod ke 1. Angka ini adalah 1. Jika dapat dibagi dengan x, maka y adalah angka yang dibagi dengan x. Jika tidak, tambahkan 10000000003 ke nomor ini untuk menemukan angka kedua yang mod 1000000003 akan sama dengan 1 dan ulangi.

Zachary Cotton
sumber
Angka pertama yang akan
diubah
@ atau lol terima kasih. Itu menyelamatkan saya 2 byte :)
Zachary Cotton
Menarik, pada TIO ini cepat untuk semua kasus uji tetapi sedikit membenturkan keyboard acak memberi saya 421385994waktu yang keluar.
Ørjan Johansen
@ ØrjanJohansen Pekerjaan sulap yang bagus.
1
Jika Anda bhanya perlu sekali, mengapa tidak melakukan hardcoding?
Federico Poloni
5

JavaScript (ES6), 153 143 141 byte

Terinspirasi oleh jawaban ini dari math.stackexchange.com .

Fungsi rekursif berdasarkan algoritma Euclidean.

f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)

Modulo diimplementasikan dengan komputasi:

quotient = Math.floor(a / b);
remainder = a - b * quotient;

Karena hasil bagi juga diperlukan, melakukannya dengan cara yang sebenarnya masuk akal.

Uji kasus

Arnauld
sumber
Anda hanya perlu lantai 64 bit pada kejadian terakhir sehingga Anda dapat mengganti yang lain dengan 0 | x / y dan menghapus deklarasi
Oki
5

C ++ 11 (GCC / Dentang, Linux), 104 102 byte

using T=__int128_t;T m=1e11+3;T f(T a,T r=1,T n=m-2){return n?f(a*a-a*a/m*m,n&1?r*a-r*a/m*m:r,n/2):r;}

https://ideone.com/gp41rW

Tidak digubah, berdasarkan teorema Euler dan eksponen biner.

using T=__int128_t;
T m=1e11+3;
T f(T a,T r=1,T n=m-2){
    if(n){
        if(n & 1){
            return f(a * a - a * a / m * m, r * a - r * a / m * m, n / 2);
        }
        return f(a * a - a * a / m * m, r, n / 2);
    }
    return r;
}
SteelRaven
sumber
ISO C ++ hanya membutuhkan longpaling tidak 32-bit, jadi tidak harus selalu berlaku 1e11 + 3. Ini 32-bit pada Windows x86-64. longadalah tipe 64-bit pada x86-64 Linux (dan OS lain yang menggunakan SystemV ABI). Jadi untuk sepenuhnya portabel, Anda harus menggunakan long long, yang dijamin setidaknya 64-bit sejak C ++ 11 .
Peter Cordes
__int128_ttampaknya tidak menjadi standar C ++, tampaknya merupakan ekstensi gcc, akan lebih keren jika Anda menyatakan ini sebagai bahasa (C ++ 11 + gcc).
Felix Dombek
3
Ini seharusnya bukan situs pakar C ++, saya berharap tidak ada yang memperhatikan.
SteelRaven
@PeterCordes Code golf tidak perlu portabel atau bahkan dibentuk dengan baik, hanya perlu bekerja pada satu implementasi.
aschepler
1
@aschepler: Aku tahu, itulah sebabnya saya mengatakan "Anda akan membutuhkan". Saya pikir itu berguna untuk menunjukkan platform mana yang akan / tidak akan bekerja, kalau-kalau ada yang mencobanya dan mengalami masalah.
Peter Cordes
4

Mathematica, 49 byte

x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&
J42161217
sumber
Berapa lama untuk menjalankan ini?
Kurang dari 0,001 di komputer saya (untuk kasus 2 ^ 40-1)
Keyu Gan
2

PHP, 71 byte

for(;($r=bcdiv(bcadd(bcmul(++$i,1e11+3),1),$argn,9))!=$o=$r^0;);echo$o;

Testcases

Jörg Hülsermann
sumber
1

Ruby , 58 byte

Menggunakan aplikasi isaacg tentang teorema kecil Fermat untuk saat ini sementara saya menyelesaikan pengaturan waktu solusi brute-force.

->n,x=10**11+3{i=n;11.times{i**=10;i-=i/x*x};i*=n;i-i/x*x}

Versi kekerasan saat ini, yang 47 byte tapi mungkin adalah terlalu lambat:

->n,x=10**11+3{(1..x).find{|i|i*=n;i-i/x*x==1}}

Cobalah online!

Nilai Tinta
sumber