Wprowadzenie

W tym wyzwaniu będziemy mieli do czynienia z pewnym nieskończonym niekierowanym wykresem, który nazywam wykresem wysokiego dzielnika . Węzłami są liczbami całkowitymi, począwszy od 2. Nie jest krawędź między dwoma węzłami <b jeśli dzieli b i a ² ≥ b . Podgraf utworzony przez zakres od 2 do 18 wygląda następująco:

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

Można pokazać, że wykres nieskończonego wysokiego dzielnika jest połączony, więc możemy zapytać o najkrótszą ścieżkę między dwoma węzłami.

Wejście i wyjście

Twoje dane wejściowe to dwie liczby całkowite a i b . Możesz założyć, że 2 ≤ a ≤ b <1000 . Jego wynik jest długością najkrótszej trasy między i b w nieskończonym wykresie wysokiej dzielnik. Oznacza to liczbę krawędzi na ścieżce.

Przydatny może być następujący fakt: zawsze istnieje optymalna ścieżka od a do b, która najpierw rośnie, a następnie maleje i odwiedza tylko węzły, które są mniejsze niż 2b ² . W szczególności, ponieważ b <1000 , należy wziąć pod uwagę tylko węzły mniejsze niż 2 000 000.

Przykłady

Rozważ dane wejściowe 3i 32. Jedną z możliwych ścieżek między węzłami 3 i 32 jest

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

Ta ścieżka ma cztery krawędzie i okazuje się, że nie ma krótszych ścieżek, więc prawidłowy wynik to 4.

Kolejnym przykładem jest optymalna ścieżka dla 2i 25jest

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

więc poprawne wyjście to 5. W takim przypadku żadna optymalna ścieżka nie zawiera węzła 50 = lcm(2, 25).

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Nie ma ograniczeń czasu ani pamięci, więc dozwolone jest brutalne wymuszanie.

Przypadki testowe

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 bajtów

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

Dzięki @beaker za skrót w kroku wydłużania listy!

Jest to stosunkowo prosta implementacja dijkstra:

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

_{^{dzisiaj nie ma splotu}}

JavaScript (ES6), 186 bajtów

(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)))

Wykorzystuje funkcję pomocnika gobliczyć wszystkie ścieżki rosnacy od mi nkolejno do podanego limitu, a następnie sumuje ścieżek razem i powroty najniższej wartości.

Mathematica 98 bajtów

Zakładam, że wbudowana funkcja FindShortestPathnie narusza ograniczenia dotyczącego standardowych luk. Jeśli tak, daj mi znać, a ja usunę to zgłoszenie.

Brutalna siła, a więc powolna z dużymi wartościami b. Nadal zastanawiam się, jak to przyspieszyć.

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

Spowoduje to utworzenie wykresu z odpowiednimi krawędziami między węzłami od ado b^2. FindShortestPathznajduje najkrótszą ścieżkę na wykresie. Lengthzlicza węzły; Length -1to liczba krawędzi.

Thread[# <-> Range[2, #] #] &tworzy krawędzie pełnego wykresu. Na przykład Thread[# <-> Range[2, #] #]&[5]utworzy krawędzie {5 <-> 2*5, 5 <-> 3*5, 5 <-> 4*5, 5 <-> 5*5}, to znaczy {5 <-> 10, 5 <-> 15, 5 <-> 20, 5 <-> 25}.

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

Uwaga: Ja, użytkownik Agawa001, osobiście zaświadczam, że wygrałem z użytkownikiem @flawr, korzystając z jego pomocy

 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

• Ta funkcja różni się od innych, jest zgodna z szeregiem czystych obliczeń matematycznych i faktoryzacji, ale nie ma nic wspólnego ze ścieżkami lub wykresami.

• Przykład wywołania funkcji:

   t(2,3,0)
  
   p =
  
   4
  

  Wszystkie przypadki testowe są spełnione

• Wyjaśnienie:

Zanim zaczniemy od wyjaśnień, dowiedzmy się, że niektóre lematy są „zielone”:

Lemat (1): Optymalna ścieżka między dowolnymi dwoma liczbami (a,b)istnieje w taki sposób, że węzły najpierw rosną, a maleją.

Dlaczego ? Jest to po prostu udowodnione, ponieważ maksymalna liczba całkowita, która dzieli dowolną liczbę, ajest odpowiednio duża jak asama liczba , więc jako sprytne podejście musimy wybrać ajak najwięcej pomnożenia, aby było wystarczająco większe, a następnie podzielenie przez większe wartości. Jeśli kiedykolwiek zrobimy to na odwrót, liczba się azmniejszy, więc potrzebujemy niepotrzebnie więcej iteracji, aby pomnożyć ją stopniowo, bez potrzeby.

Lemat (2): Od liczby ado b, jeśli gcd(a,b)=1 ajest pomnożony przez b, jeśli bjest większy niż abędzie pomnożony przez znaną liczbę c, jeśli gcd>1 amusi być pomnożony przez największy dzielnik o b/gcdnazwie, dktóry sprawdza warunek a >= drównież wtedy, gdy wszystko djest mianem minimum jest większe niż a, aotrzymuje a*cponownie.

To założenie jest proste do udowodnienia każdy węzeł rozpoczęciem anależy pomnożyć aż osiągnie najmniejszą wielokrotność aa bwięc albo mnożymy przez proporcjach b*gcdzaczynając od maksimum która weryfikuje główny warunek, który gwarantuje zawsze najkrótsza droga do smp zanim rozpocznie proces podziału, lub gdy dnie jest dostępny, liczba cjest mnożona przez, aaby spełnić warunek a>=ddla pierwszego etapu.

Lemat (3): Od wielokrotności wykresu ado bgcd tej liczby i bjest bsam

Cóż, jest to tylko konsekwencja poprzednich manipulacji, a ostatnie pozostałe kroki są również wykonywane stopniowo dzieląc przez największy dzielnik, który nie przekracza pierwiastka kwadratowego.

Dylemat: Jaka jest optymalna liczba, którą cnależy pomnożyć iteracyjnie a, która prowadziłaby prosto do warunków otwarcia dla etapu 1, a następnie najwyższego?

Dobre pytanie, dla każdej prostej sytuacji istnieje prosta parowanie, więc zakładając przykład dwóch zakończeń (a,b)=(4,26)tak podzielonych na czynniki:

  2 | 2
  2 | 13

Oprócz gcd=2najmniejszej liczby całkowitej, którą należy pomnożyć, 2aby osiągnąć, 13jest 7, ale oczywiście jest wykluczone, ponieważ jest większa niż 2, więc a jest kwadratem.

  2 | 2 
  5 | 13

Appearenlty w drugim przykładzie (a,b)=(10,26)powyżej cmierzy się jako najmniejszą liczbę całkowitą od 1do 5przekraczającej 13/5stąd spełnia warunek wykresu zgorzeliny, która jest 3, aby następny krok jest pomnożony przez3

  2 | 2 
  5 | 13
  3 |

Dlaczego ? Dzieje się tak, ponieważ gdy musimy pomnożyć, 2*13/gcd=13aby dopasować do drugiej strony tabeli, ilość śmieci dodanych wcześniej jest optymalnie najmniejsza, a poruszanie się po wykresie jest zminimalizowane, jeśli kiedykolwiek pomnożymy przez większą wartość, taką jak 10szansa na podzielenie przez najmniej razy zmniejsza się, a zostałby zwiększony o 1 kolejny krok dzielący, aby osiągnąć nasz cel 2*13. które są wyliczone do: 13*2*5*10/2*5wtedy 13*2*5/5. Chociaż oczywiście tutaj liczba, którą należy podzielić, to5*3<13*2

i jeszcze jedno ... MATY WŁOSÓW ...

To są moje wyniki porównawcze z wynikami @flawr. Zwróć tylko uwagę, że wyznaczyłem górną granicę czasu wykonania zachowując algorytm flawr, to zajmuje zbyt dużo czasu!

Możesz wstawiać początkowe i końcowe zakresy skanowania jako zmienne a i b w nagłówku kompilowanego kodu online.