pengantar

Dalam tantangan ini, kita akan berhadapan dengan grafik tak terarah tak terbatas tertentu, yang saya sebut grafik pembagi tinggi . Node-nya adalah bilangan bulat mulai dari 2. Ada tepi antara dua node a <b jika a membagi b dan a ² ≥ b . Subgraf yang dibentuk oleh rentang 2 hingga 18 terlihat seperti ini:

16-8 12 18
  \|/ |/|
   4  6 9 10 15 14
   |  |/   |/   |
   2  3    5    7  11 13 17

Dapat ditunjukkan bahwa grafik pembagi tinggi tak terbatas terhubung, sehingga kita dapat bertanya tentang jalur terpendek antara dua node.

Masukan dan keluaran

Input Anda adalah dua bilangan bulat a dan b . Anda dapat mengasumsikan bahwa 2 ≤ a ≤ b <1000 . Output Anda adalah panjang jalur terpendek antara a dan b dalam grafik pembagi tinggi tak terbatas. Ini berarti jumlah tepi di jalan.

Anda mungkin menemukan fakta berikut ini berguna: selalu ada jalur optimal dari a ke b yang pertama kali meningkat lalu menurun, dan hanya mengunjungi node yang benar-benar kurang dari 2b ² . Khususnya, karena b <1000 Anda hanya perlu mempertimbangkan node yang kurang dari 2 000 000.

Contohnya

Pertimbangkan input 3dan 32. Satu jalur yang mungkin antara node 3 dan 32 adalah

3 -- 6 -- 12 -- 96 -- 32

Jalur ini memiliki empat tepi, dan ternyata tidak ada jalur yang lebih pendek, jadi output yang benar adalah 4 .

Sebagai contoh lain, jalur optimal untuk 2dan 25adalah

2 -- 4 -- 8 -- 40 -- 200 -- 25

jadi output yang benar adalah 5. Dalam hal ini, tidak ada jalur optimal yang berisi node 50 = lcm(2, 25).

Aturan dan penilaian

Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Tidak ada batasan waktu atau memori, jadi pemaksaan kasar diperbolehkan.

Uji kasus

2 2 -> 0
2 3 -> 4
2 4 -> 1
2 5 -> 5
3 5 -> 4
6 8 -> 2
8 16 -> 1
12 16 -> 2
16 16 -> 0
2 25 -> 5
3 32 -> 4
2 256 -> 3
60 77 -> 3
56 155 -> 3
339 540 -> 2
6 966 -> 4
7 966 -> 2
11 966 -> 4
2 997 -> 7
991 997 -> 4

Matlab, 218 190 175 byte

function f(a,b);q=a;l(b)=0;l(a)=1;while~l(b);x=q(1);q=q(2:end);l(end+1:x^2)=0;g=x+1:x^2;s=2:x-1;u=[g(~mod(g,x)),s(~mod(x,s)&s.^2>=x)];u=u(~l(u));q=[q,u];l(u)=l(x)+1;end;l(b)-1

Terima kasih @beaker untuk pintasan di dalam langkah pemanjangan daftar!

Ini adalah implementasi dijkstra yang relatif mudah:

q=a;                  %queue
l(b)=0;       %list of path lengths
l(a)=1;
while~l(b);         %if there is no predecessor to b
    x=q(1);         %get first queue element
    q=q(2:end);
    %add edges 
    l(end+1:x^2)=0;% lengthen predecessor list if too short
    g=x+1:x^2;      % g=greater neighbours
    s=2:x-1;        % s=smaller neighbours %keep only valid/unvisited neighbours 
    u=[g(~mod(g,x)),s(~mod(x,s)&s.^2>=x)]; %-1byte
    u=u(~l(u));
    q=[q,u];      %add only hte valid nodes edges to queue
    l(u)=l(x)+1;       %mark x as predecessor  
end;
l(b)-1 %output length to the end of the path

_{^{tidak ada belitan hari ini}}

JavaScript (ES6), 186 byte

(m,n)=>(g=i=>{for(q=[i],r=[],r[i]=j=0;i=q[j++];)for(k=i+i;k<=i*i&(k<m*m*2|k<n*n*2);k+=i)r[k]-r[i]<2?0:r[q.push(k),k]=r[i]+1},g(m),s=r,g(n),Math.min(...r.map((i,j)=>i+s[j]).filter(i=>i)))

Menggunakan fungsi penolong guntuk menghitung semua jalur naik dari mdan npada gilirannya ke batas yang disediakan, lalu menjumlahkan jalur bersama dan mengembalikan nilai terendah.

Mathematica 98 byte

Saya mengasumsikan bahwa fungsi bawaan, FindShortestPathtidak melanggar batasan tentang celah standar. Jika ya, beri tahu saya dan saya akan menghapus kiriman ini.

Brute force, karenanya lambat dengan nilai besar b. Saya masih memikirkan cara untuk mempercepatnya.

h@{a_,b_}:=Length@FindShortestPath[Graph[Apply[Join,Thread[#<->Range[2,#] #]&/@Range[b^2]]],a,b]-1

Ini mengatur grafik dengan tepi yang sesuai antara node dari ake b^2. FindShortestPathmenemukan jalur terpendek dalam grafik. Lengthmenghitung node; Length -1adalah jumlah tepi.

Thread[# <-> Range[2, #] #] &menghasilkan tepi grafik penuh. Sebagai contoh, Thread[# <-> Range[2, #] #]&[5]akan menghasilkan tepi {5 <-> 2*5, 5 <-> 3*5, 5 <-> 4*5, 5 <-> 5*5}, yaitu {5 <-> 10, 5 <-> 15, 5 <-> 20, 5 <-> 25},.

Matlab (195) (185) (181) (179)(173)

Catatan: Saya pengguna Agawa001 secara pribadi saya membuktikan bahwa saya menang atas pengguna @ flawr memanfaatkan bantuannya

 function t(a,b,p),for r=0:1,d=(b*~r+r*a)/gcd(a,b);while(d>1)p=p+1;e=find(~rem(d,1:d));f=max(e(a^(1-r/2)>=e));a=a*min([find(1:a*a>=b) a])^~(f-1);d=d/f;a=a*f^(1-2*r);end,end,p

• Fungsi ini berbeda dari yang lain, ia memang mengikuti banyak perhitungan matematis murni dan factorisations tetapi tidak ada hubungannya dengan jalur atau grafik.

• Contoh panggilan fungsi:

   t(2,3,0)
  
   p =
  
   4
  

  Semua test case puas

• Penjelasan:

Sebelum memulai dengan penjelasan, mari kita buktikan beberapa lemmas "bukan yang hijau":

Lemma (1): Jalur optimal antara dua angka (a,b)ada dengan cara node pertama meningkat kemudian menurun.

Mengapa Ini hanya dibuktikan karena jumlah bilangan bulat maksimal yang membagi angka berapa apun masing-masing sebesar angka aitu sendiri, sehingga sebagai pendekatan yang cerdas kita harus memilih untuk mengalikan asebanyak mungkin untuk membuatnya cukup besar, kemudian membaginya dengan nilai yang lebih besar. Jika kita melakukan jalan memutar, jumlahnya amenyusut, jadi kita perlu lebih banyak iterasi untuk memperbanyaknya secara bertahap sehingga kita tidak perlu.

Lemma (2): Dari angka ake b, jika gcd(a,b)=1 adikalikan dengan b, jika blebih besar dari aitu akan dikalikan dengan angka yang diketahui c, jika gcd>1 aharus dikalikan secara bertahap dengan pembagi b/gcdnama terbesar dyang memverifikasi kondisi a >= djuga ketika semua dadalah minimum lebih besar dari a, aterima a*clagi.

Asumsi ini sederhana untuk membuktikan setiap simpul awal aharus dikalikan hingga mencapai kelipatan terkecil adan bkarenanya kita kalikan dengan proporsi b*gcdawal dengan maksimum yang memverifikasi kondisi utama, yang menjamin selalu jalur terpendek untuk smp sebelum proses pembagian dimulai, atau ketika dtidak tersedia angka cdikalikan dengan auntuk membuat kondisi yang valid a>=duntuk tahap pertama ini.

Lemma (3): Dari kelipatan grafik-ultimum ake b, gcd dari angka ini dan bitu bsendiri

Nah ini hanya konsekuensi dari manipulasi sebelumnya, dan langkah terakhir yang tersisa juga dilakukan secara bertahap dengan pembagi terbesar yang tidak melebihi akar kuadratnya.

Dilema: Berapakah angka optimal cuntuk dikalikan secara iteratif dengan angka ayang mengarah langsung ke kondisi pembukaan untuk tahap 1 kemudian ultimum?

Pertanyaan bagus, untuk situasi sederhana apa pun ada pesta sederhana, jadi anggaplah contoh dua sisi (a,b)=(4,26)difaktorkan seperti ini:

  2 | 2
  2 | 13

Terlepas dari gcd=2bilangan bulat terkecil yang harus dikalikan dengan 2untuk mencapai 13adalah 7, tetapi jelas dikesampingkan, karena lebih besar dari 2, jadi a kuadrat.

  2 | 2 
  5 | 13

Appearenlty pada contoh kedua (a,b)=(10,26)di atas cdiukur sebagai integer terendah dari 1ke 5yang melebihi 13/5karena itu memenuhi kondisi grafik-scaling, yang 3, maka langkah selanjutnya di sini adalah mengalikan dengan3

  2 | 2 
  5 | 13
  3 |

Mengapa ini karena, begitu kita harus mengalikan dengan 2*13/gcd=13untuk mencocokkan dengan sisi kedua tabel, jumlah sampah yang kita tambahkan sebelumnya secara optimal terkecil, dan bergerak sepanjang grafik diminimalkan, jika kita dikalikan dengan nilai yang lebih besar seperti 10peluang untuk membagi dengan paling sedikit waktu berkurang, dan itu akan meningkat 1 langkah membagi lain untuk mencapai tujuan kami 2*13. yang disebutkan untuk: 13*2*5*10/2*5lalu 13*2*5/5. Sementara, jelas di sini jumlah yang akan dibagi adalah5*3<13*2

dan satu hal lagi ........ MATI MATI ...

Ini adalah hasil komparatif saya dengan @ flawr 's hanya memperhatikan bahwa saya membuat batas atas untuk eksekusi berdasarkan algoritma flawr, butuh terlalu banyak waktu!

Anda dapat memasukkan rentang pemindaian mulai dan berakhir sebagai variabel a dan b di header kode yang dapat dikompilasi online.