For a fixed positive integer \(n\), consider the subtractive Euclidean algorithm on a coprime pair \((n,m)\): at each step, replace the larger number by the difference of the two numbers until one entry becomes 0. The quantity minimized in Problem 958 is this Euclidean labour, and among all residues with minimal labour we want the smallest positive representative of the symmetry orbit
$$\{m,\ n-m,\ m^{-1},\ n-m^{-1}\}\pmod n,$$
where \(m^{-1}\) is the modular inverse of \(m\) modulo \(n\).
The small checks built into the implementations are
$$f(7)=2,\qquad f(89)=34,\qquad f(8191)=1856.$$
For the final input \(n=1{,}000{,}000{,}000{,}039\), a direct scan over all \(1\le m<n\) is impossible. The successful solution rewrites the search in terms of primitive Euclid-tree states, splits a shortest path near its midpoint, and turns the second half into a reduced lattice problem followed by a short finishing Euclidean descent.
If
$$\frac{n}{m}=[q_0,q_1,\dots,q_r]$$
is the regular continued fraction of \(n/m\), then the subtractive Euclidean algorithm performs exactly
$$\ell(n,m)=q_0+q_1+\cdots+q_r$$
subtractions. So the problem is not asking for the smallest \(m\), but for the smallest \(m\) among those whose continued-fraction digit sum is minimal.
The search is organized with the two unimodular moves
$$L=\begin{pmatrix}0&1\\1&1\end{pmatrix},\qquad R=\begin{pmatrix}1&0\\1&1\end{pmatrix},$$
which act on a primitive ordered pair \((a,b)\) as
$$L:(a,b)\mapsto (b,a+b),\qquad R:(a,b)\mapsto (a,a+b).$$
Starting from \((0,1)\), these moves generate the Stern-Brocot style tree of primitive nonnegative pairs. Every move contributes one unit of Euclidean labour, so a path of length \(s\) represents a coprime residue whose subtractive Euclidean cost is \(s\).
Fix a trial budget \(s\), and set
$$d=\left\lfloor\frac{s+1}{2}\right\rfloor.$$
The forward half of the path is explored explicitly to depth \(d\). To describe the backward half, the implementations carry a second vector \((c_a,c_b)\) satisfying the invariant
$$a\,c_a+b\,c_b=n.$$
This is preserved because the coefficient vector is updated by the inverse transpose of the same matrix used on \((a,b)\):
$$L^{-T}:(c_a,c_b)\mapsto (c_b-c_a,c_a),\qquad R^{-T}:(c_a,c_b)\mapsto (c_a-c_b,c_b).$$
So every midpoint of a valid shortest path lies on the integer line \(a\,c_a+b\,c_b=n\).
All integer solutions of \(a\,c_a+b\,c_b=n\) differ by multiples of \((b,-a)\). Define
$$N=a^2+b^2,\qquad X=c_a b-c_b a.$$
Replacing \((c_a,c_b)\) by \((c_a+k b,c_b-k a)\) keeps the dot product \(a\,c_a+b\,c_b\) unchanged, but changes the cross term by
$$X\mapsto X+kN.$$
Therefore the midpoint can be shifted into a canonical strip \(0\le X<N\). The additional condition
$$c_a^2+c_b^2\le N$$
means that the coefficient vector is no longer than the forward vector. Once the strip reduction is done, at most two neighboring lattice points can satisfy this norm bound, which is why the implementation only needs to test two candidates at the terminal stage.
When \(s\) is odd, the midpoint lies inside one Euclidean move rather than between two full levels. The code converts that case to the same geometry by replacing
$$ (a,b,c_a,c_b)\longmapsto (2a,\ 2b-a,\ 2c_a+c_b,\ 2c_b). $$
After this change, the preserved dot product becomes \(4n\), but the same norm reduction and the same finishing logic apply. That is why the odd and even cases share one core terminal check.
From a valid midpoint, the remaining Euclidean labour is completed by a subtractive descent on a coefficient pair \((x,y)\), together with the dual updates on a primitive pair \((v_x,v_y)\): after ordering \(x\le y\), one step is
$$ (x,y,v_x,v_y)\mapsto (x,\ y-x,\ v_x+v_y,\ v_y). $$
The invariant
$$x\,v_x+y\,v_y=n$$
is preserved throughout. If one coefficient reaches 0 within the remaining budget, the associated residue is
$$o\equiv v_x+v_y-n \pmod n.$$
The code then checks that \(o\) is invertible modulo \(n\), and scores the orbit representative
$$\min\{o,\ n-o,\ o^{-1},\ n-o^{-1}\}.$$
The first budget \(s\) for which such a terminal state exists is the minimal Euclidean labour.
For \(n=7\), take \(m=2\). Then
$$\frac{7}{2}=[3,2],$$
so the labour is \(3+2=5\). The same labour appears on the whole symmetry orbit
$$\{2,5,4,3\}=\{m,\ 7-m,\ m^{-1},\ 7-m^{-1}\},$$
because \(2^{-1}\equiv 4\pmod 7\). The smallest positive member of that orbit is \(2\), matching the validation value \(f(7)=2\). The larger checks \(f(89)=34\) and \(f(8191)=1856\) are produced by exactly the same mechanism, only with much deeper shortest paths.
The C++, Python, and Java implementations increase the candidate labour \(s\) from 0 upward. For each \(s\), they set \(d=\lfloor(s+1)/2\rfloor\) and run a depth-first search over midpoint states \((a,b,c_a,c_b)\). Each recursive call normalizes the order to \(a\le b\), pushes \(c_a\) upward by whole copies of \((b,-a)\) when necessary, and immediately rejects states with \(c_b<0\) or with a broken invariant \(a\,c_a+b\,c_b\ne n\).
Before expanding deeper, the implementation computes an optimistic continuation obtained by always following the smallest-growth forward branch. If even that continuation cannot make the terminal norm large enough, the whole branch is impossible and is pruned early. The resulting tests are
$$x^2+y^2\ge n$$
for even budgets, and
$$x^2+xy+\frac{5}{4}y^2\ge n$$
for the odd-midpoint geometry. These inequalities are the main reason the search stays small in practice.
At depth \(d\), the code applies the odd-budget conversion when needed, computes the norm \(N\) and cross term \(X\), and shifts the coefficient vector into the canonical strip \(0\le X<N\). Because only two neighboring lattice points can remain compatible with the norm bound \(c_a^2+c_b^2\le N\), the implementation performs exactly two terminal checks: the reduced point itself and the next neighbor obtained by subtracting one more copy of \((b,-a)\).
Each surviving terminal candidate is finished by a bounded subtractive Euclidean run on the second-half coefficients. The same code handles even and odd budgets; the odd case first undoes the midpoint conversion with parity checks so that the final descent always lives in the original integer state space. When the descent ends within the remaining budget, the residue \(o\) is extracted, its modular inverse is tested, and the best answer is updated using the pair "smallest labour first, smallest orbit representative second".
If the minimal Euclidean labour is \(s^\ast\), a naive full search would branch over all words of length \(s^\ast\), which is exponential. The midpoint split reduces the explicit tree depth to roughly \(s^\ast/2\), so the raw search shape is closer to \(O(2^{s^\ast/2})\) midpoint states than to \(O(2^{s^\ast})\) full paths.
Each surviving midpoint requires only constant-size arithmetic on a few integers, plus at most \(s^\ast-d\) subtractive finishing steps. Memory usage is \(O(s^\ast)\) because the recursion stack and the terminal work both store only a bounded amount of state. In practice, the decisive factor is pruning: the sign normalization, norm bounds, lattice-strip reduction, and modular-inverse test remove the overwhelming majority of theoretical branches.
Für ein festes positives \(n\) betrachtet man den subtraktiven euklidischen Algorithmus für ein teilerfremdes Paar \((n,m)\): In jedem Schritt wird die größere Zahl durch die Differenz der beiden Zahlen ersetzt, bis ein Eintrag 0 wird. In Problem 958 wird diese euklidische Arbeit minimiert; unter allen Restklassen mit minimaler Arbeit ist dann der kleinste positive Vertreter der Symmetrieklasse
$$\{m,\ n-m,\ m^{-1},\ n-m^{-1}\}\pmod n$$
gesucht, wobei \(m^{-1}\) das multiplikative Inverse modulo \(n\) bezeichnet.
Die eingebauten Prüfwerte lauten
$$f(7)=2,\qquad f(89)=34,\qquad f(8191)=1856.$$
Für \(n=1{,}000{,}000{,}000{,}039\) ist ein direktes Durchprobieren aller \(m\) unmöglich. Die Lösung beschreibt die Suche daher als Baum primitiver Euclid-Zustände, teilt einen kürzesten Pfad nahe seiner Mitte und verwandelt die zweite Hälfte in ein Gitterproblem mit anschließender kurzer euklidischer Restreduktion.
Ist
$$\frac{n}{m}=[q_0,q_1,\dots,q_r]$$
der reguläre Kettenbruch von \(n/m\), dann benötigt der subtraktive euklidische Algorithmus genau
$$\ell(n,m)=q_0+q_1+\cdots+q_r$$
Subtraktionen. Gesucht ist also nicht einfach das kleinste \(m\), sondern das kleinste \(m\) unter den Restklassen mit minimaler Kettenbruch-Ziffernsumme.
Die Suche benutzt die beiden unimodularen Übergänge
$$L=\begin{pmatrix}0&1\\1&1\end{pmatrix},\qquad R=\begin{pmatrix}1&0\\1&1\end{pmatrix},$$
die auf ein primitives geordnetes Paar \((a,b)\) wirken als
$$L:(a,b)\mapsto (b,a+b),\qquad R:(a,b)\mapsto (a,a+b).$$
Ausgehend von \((0,1)\) entsteht so der Stern-Brocot-artige Baum aller primitiven nichtnegativen Paare. Jeder Schritt erhöht die euklidische Arbeit um 1; ein Pfad der Länge \(s\) entspricht also einer Restklasse mit Arbeit \(s\).
Für ein vorgegebenes Arbeitsbudget \(s\) setzt der Algorithmus
$$d=\left\lfloor\frac{s+1}{2}\right\rfloor.$$
Die erste Pfadhälfte wird bis Tiefe \(d\) explizit durchsucht. Für die zweite Hälfte wird ein zweiter Vektor \((c_a,c_b)\) mitgeführt, der die lineare Invariante
$$a\,c_a+b\,c_b=n$$
erfüllt. Diese Bedingung bleibt erhalten, weil der Koeffizientenvektor mit der invers transponierten Matrix aktualisiert wird:
$$L^{-T}:(c_a,c_b)\mapsto (c_b-c_a,c_a),\qquad R^{-T}:(c_a,c_b)\mapsto (c_a-c_b,c_b).$$
Jeder zulässige Mittelpunkt eines kürzesten Pfades liegt damit auf der diophantischen Geraden \(a\,c_a+b\,c_b=n\).
Alle ganzzahligen Lösungen von \(a\,c_a+b\,c_b=n\) unterscheiden sich um Vielfache von \((b,-a)\). Definiere
$$N=a^2+b^2,\qquad X=c_a b-c_b a.$$
Verschiebt man \((c_a,c_b)\) zu \((c_a+k b,c_b-k a)\), so bleibt das Skalarprodukt erhalten, aber
$$X\mapsto X+kN.$$
Deshalb kann der Mittelpunkt in den kanonischen Streifen \(0\le X<N\) verschoben werden. Die zusätzliche Normbedingung
$$c_a^2+c_b^2\le N$$
sagt, dass der Koeffizientenvektor nicht länger als der Vorwärtsvektor sein darf. Nach der Streifenreduktion kommen daher höchstens zwei benachbarte Gitterpunkte als Kandidaten infrage.
Ist \(s\) ungerade, liegt der Mittelpunkt inmitten eines euklidischen Schritts. Dieser Fall wird durch die Ersetzung
$$ (a,b,c_a,c_b)\longmapsto (2a,\ 2b-a,\ 2c_a+c_b,\ 2c_b) $$
auf dieselbe Geometrie zurückgeführt. Danach lautet das erhaltene Skalarprodukt \(4n\), doch Normreduktion und Endprüfung bleiben unverändert.
Von einem gültigen Mittelpunkt aus wird die restliche Arbeit durch einen subtraktiven Abstieg auf \((x,y)\) mitgeführt, parallel zu einem primitiven Paar \((v_x,v_y)\). Nach Anordnung \(x\le y\) ist ein Schritt
$$ (x,y,v_x,v_y)\mapsto (x,\ y-x,\ v_x+v_y,\ v_y). $$
Dabei bleibt
$$x\,v_x+y\,v_y=n$$
erhalten. Sobald innerhalb des Restbudgets ein Koeffizient 0 wird, erhält man die Restklasse
$$o\equiv v_x+v_y-n \pmod n,$$
prüft ihre Invertierbarkeit modulo \(n\) und bewertet den Vertreter
$$\min\{o,\ n-o,\ o^{-1},\ n-o^{-1}\}.$$
Das erste Budget \(s\), für das das gelingt, ist genau die minimale euklidische Arbeit.
Für \(n=7\) und \(m=2\) gilt
$$\frac{7}{2}=[3,2],$$
also beträgt die Arbeit \(3+2=5\). Zur selben Symmetrieklasse gehören
$$\{2,5,4,3\}=\{m,\ 7-m,\ m^{-1},\ 7-m^{-1}\},$$
denn \(2^{-1}\equiv 4\pmod 7\). Alle vier Werte haben dieselbe Arbeit, und der kleinste positive Vertreter ist \(2\). Genau deshalb liefert der Testwert \(f(7)=2\).
Die C++-, Python- und Java-Implementierungen erhöhen das Arbeitsbudget \(s\) von 0 an schrittweise. Für jedes \(s\) wird \(d=\lfloor(s+1)/2\rfloor\) gesetzt und eine Tiefensuche über Mittelpunktzustände \((a,b,c_a,c_b)\) ausgeführt. Dabei werden stets \(a\le b\) normalisiert, negative \(c_a\) durch Verschiebungen entlang \((b,-a)\) angehoben und alle Zustände mit \(c_b<0\) oder verletzter Invariante sofort verworfen.
Vor dem Abstieg berechnet der Code eine optimistische Fortsetzung, die den Normzuwachs minimal hält. Wenn selbst diese kleinste mögliche Fortsetzung den nötigen terminalen Normwert nicht erreicht, wird der ganze Ast abgeschnitten. Die resultierenden Schranken sind
$$x^2+y^2\ge n$$
für gerade Budgets und
$$x^2+xy+\frac{5}{4}y^2\ge n$$
für die ungerade Mittelpunktgeometrie.
In Tiefe \(d\) wird gegebenenfalls die ungerade Umformung angewandt, anschließend werden Norm \(N\) und Kreuzterm \(X\) berechnet und der Koeffizientenvektor in den Streifen \(0\le X<N\) verschoben. Da danach höchstens zwei benachbarte Gitterpunkte noch die Normbedingung \(c_a^2+c_b^2\le N\) erfüllen können, testet die Implementierung genau zwei Endkandidaten.
Jeder dieser Endkandidaten wird durch einen beschränkten subtraktiven euklidischen Lauf vervollständigt. Für ungerade Budgets wird zuvor mit Paritätsprüfungen aus der umgeformten Geometrie in den ursprünglichen ganzzahligen Zustandsraum zurückgekehrt. Erreicht der Abstieg das Ende innerhalb des Restbudgets, wird \(o\) berechnet, das modulare Inverse geprüft und dann lexikographisch zuerst nach Arbeit, danach nach kleinstem Orbitvertreter aktualisiert.
Ist \(s^\ast\) die minimale euklidische Arbeit, dann wäre eine naive vollständige Suche über alle Wörter der Länge \(s^\ast\) exponentiell. Durch die Aufspaltung in der Mitte sinkt die explizit durchsuchte Tiefe auf ungefähr \(s^\ast/2\), sodass die Rohform eher \(O(2^{s^\ast/2})\) Mittelpunktzuständen als \(O(2^{s^\ast})\) ganzen Pfaden entspricht.
Jeder überlebende Mittelpunkt braucht nur Arithmetik auf wenigen ganzen Zahlen und höchstens \(s^\ast-d\) weitere Subtraktionsschritte. Der Speicherbedarf ist \(O(s^\ast)\), weil im Wesentlichen nur der Rekursionsstapel und ein kleiner fester Terminalzustand gehalten werden. Praktisch dominiert die starke Beschneidung durch Vorzeichenprüfungen, Normschranken, Streifenreduktion und Invertierbarkeitstest.
Sabit bir pozitif \(n\) için, aralarında asal \((n,m)\) çifti üzerinde çıkarma tabanlı Oklid algoritmasını düşünelim: her adımda büyük sayı iki sayının farkıyla değiştirilir ve bir bileşen 0 olana kadar devam edilir. Problem 958'de minimize edilen nicelik bu Oklid emeğidir; en küçük emeği veren artık sınıfları arasından da
$$\{m,\ n-m,\ m^{-1},\ n-m^{-1}\}\pmod n$$
yörüngesinin en küçük pozitif temsilcisi istenir. Burada \(m^{-1}\), \(n\) modundaki çarpımsal tersi ifade eder.
Uygulamalardaki doğrulama değerleri şunlardır:
$$f(7)=2,\qquad f(89)=34,\qquad f(8191)=1856.$$
Son giriş \(n=1{,}000{,}000{,}000{,}039\) için tüm \(m\) değerlerini doğrudan denemek imkansızdır. Başarılı yöntem, aramayı asal Oklid-ağacı durumlarıyla ifade eder, en kısa yolu orta noktasına yakın bir yerde ikiye böler ve ikinci yarıyı indirgenmiş bir kafes problemi ile kısa bir son Oklid inişine çevirir.
Eğer
$$\frac{n}{m}=[q_0,q_1,\dots,q_r]$$
\(n/m\) oranının düzenli sürekli kesir açılımıysa, çıkarma tabanlı Oklid algoritması tam olarak
$$\ell(n,m)=q_0+q_1+\cdots+q_r$$
adet çıkarma yapar. Dolayısıyla aranan şey yalnızca en küçük \(m\) değil, sürekli kesir basamak toplamı en küçük olan sınıflar içindeki en küçük \(m\)'dir.
Arama şu iki unimodüler dönüşümle düzenlenir:
$$L=\begin{pmatrix}0&1\\1&1\end{pmatrix},\qquad R=\begin{pmatrix}1&0\\1&1\end{pmatrix}.$$
Bunlar asal bir sıralı \((a,b)\) çifti üzerinde
$$L:(a,b)\mapsto (b,a+b),\qquad R:(a,b)\mapsto (a,a+b)$$
şeklinde etki eder. \((0,1)\)'den başlanınca Stern-Brocot benzeri ağaçtaki bütün asal, negatif olmayan çiftler üretilir. Her hamle Oklid emeğine 1 ekler; dolayısıyla uzunluğu \(s\) olan bir yol, emeği \(s\) olan bir artık sınıfı temsil eder.
Deneme bütçesi \(s\) için
$$d=\left\lfloor\frac{s+1}{2}\right\rfloor$$
alınır. Yolun ilk yarısı derinlik \(d\)'ye kadar açıkça gezilir. İkinci yarıyı temsil etmek için,
$$a\,c_a+b\,c_b=n$$
değişmezini sağlayan ikinci bir \((c_a,c_b)\) vektörü taşınır. Bunun korunma sebebi, katsayı vektörünün aynı matrisin ters-transpozu ile güncellenmesidir:
$$L^{-T}:(c_a,c_b)\mapsto (c_b-c_a,c_a),\qquad R^{-T}:(c_a,c_b)\mapsto (c_a-c_b,c_b).$$
Böylece geçerli bir en kısa yolun her orta noktası, \(a\,c_a+b\,c_b=n\) doğrusu üzerindeki bir tam sayı noktasına karşılık gelir.
\(a\,c_a+b\,c_b=n\) denkleminin bütün tam sayı çözümleri \((b,-a)\) vektörünün katları kadar farklıdır. Şimdi
$$N=a^2+b^2,\qquad X=c_a b-c_b a$$
tanımlarını yapalım. \((c_a,c_b)\) yerine \((c_a+k b,c_b-k a)\) yazmak skaler çarpımı değiştirmez ama çapraz terimi
$$X\mapsto X+kN$$
şeklinde kaydırır. Bu yüzden orta nokta \(0\le X<N\) olan kanonik şeride taşınabilir. Ek olarak
$$c_a^2+c_b^2\le N$$
koşulu, katsayı vektörünün ileri yöndeki vektörden daha uzun olmamasını söyler. Şerit indirgeme yapıldıktan sonra bu norm koşulunu en fazla iki komşu kafes noktası sağlayabilir; kodun iki aday denemesinin sebebi budur.
\(s\) tek olduğunda orta nokta iki tam seviye arasına değil, tek bir Oklid hamlesinin içine düşer. Kod bu durumu
$$ (a,b,c_a,c_b)\longmapsto (2a,\ 2b-a,\ 2c_a+c_b,\ 2c_b) $$
dönüşümüyle aynı geometriye çevirir. Bu durumda korunan skaler çarpım \(4n\) olur; fakat norm indirgeme ve son kontrol mantığı değişmez.
Geçerli bir orta noktadan sonra kalan emek, \((x,y)\) katsayı çifti üzerinde çıkarma tabanlı bir inişle tamamlanır; buna eş zamanlı olarak asal \((v_x,v_y)\) çifti güncellenir. \(x\le y\) sıralamasından sonra bir adım
$$ (x,y,v_x,v_y)\mapsto (x,\ y-x,\ v_x+v_y,\ v_y) $$
şeklindedir. Bu sırada
$$x\,v_x+y\,v_y=n$$
değişmezi korunur. Kalan bütçe içinde katsayılardan biri 0 olursa, elde edilen artık
$$o\equiv v_x+v_y-n \pmod n$$
olur. Daha sonra \(o\)'nun modüler tersi sınanır ve yörünge temsilcisi
$$\min\{o,\ n-o,\ o^{-1},\ n-o^{-1}\}$$
değerlendirilir. Böyle bir son durumun ilk kez ortaya çıktığı bütçe, minimal Oklid emeğidir.
\(n=7\) ve \(m=2\) için
$$\frac{7}{2}=[3,2]$$
olduğundan emek \(3+2=5\) çıkar. Aynı emek
$$\{2,5,4,3\}=\{m,\ 7-m,\ m^{-1},\ 7-m^{-1}\}$$
yörüngesinin tamamında görülür; çünkü \(2^{-1}\equiv 4\pmod 7\). Bu yörüngedeki en küçük pozitif eleman \(2\)'dir ve doğrulama değeri \(f(7)=2\) tam olarak bunu verir.
C++, Python ve Java uygulamaları aday emek değeri \(s\)'yi 0'dan başlayarak artırır. Her \(s\) için \(d=\lfloor(s+1)/2\rfloor\) alınır ve \((a,b,c_a,c_b)\) orta nokta durumları üzerinde derinlik öncelikli arama yapılır. Her çağrı önce \(a\le b\) normalizasyonu yapar, gerekirse \(c_a\)'yı \((b,-a)\) doğrultusunda yükseltir ve \(c_b<0\) olan ya da \(a\,c_a+b\,c_b=n\) değişmezini bozan durumları anında eler.
Özyineleme öncesinde, kalan seviyelerde en yavaş büyüyen ileri uzatma hesaplanır. Bu en iyimser uzatma bile terminal normu yeterince büyütemiyorsa, tüm dal imkansızdır. Böylece
$$x^2+y^2\ge n$$
eşitsizliği çift bütçeler için,
$$x^2+xy+\frac{5}{4}y^2\ge n$$
eşitsizliği ise tek orta nokta geometrisi için budama testi olarak kullanılır.
Derinlik \(d\)'de gerekirse tek-bütçe dönüşümü uygulanır, sonra \(N\) ve \(X\) hesaplanır ve katsayı vektörü \(0\le X<N\) şeridine kaydırılır. Bundan sonra norm koşulu \(c_a^2+c_b^2\le N\) ile uyumlu olabilecek en fazla iki komşu kafes noktası kaldığından, uygulama tam olarak iki terminal adayını sınar.
Ayakta kalan her aday, sınırlı uzunlukta bir çıkarma tabanlı Oklid koşusuyla tamamlanır. Tek bütçe durumunda önce parite kontrolleriyle dönüştürülmüş geometri geri alınır; böylece son iniş her zaman özgün tam sayı durum uzayında çalışır. İniş kalan bütçe içinde biterse \(o\) hesaplanır, modüler ters var mı diye bakılır ve sonuç önce emek, sonra en küçük yörünge temsilcisi olacak şekilde güncellenir.
Minimal Oklid emeği \(s^\ast\) ise, bütün uzunluk-\(s^\ast\) kelimeleri doğrudan gezmek üstel maliyetlidir. Orta nokta bölmesi, açıkça gezilen derinliği yaklaşık \(s^\ast/2\)'ye düşürür; bu nedenle kaba yapı tüm yollar için \(O(2^{s^\ast})\) yerine orta nokta durumları için yaklaşık \(O(2^{s^\ast/2})\) davranışındadır.
Her yaşayan orta nokta yalnızca birkaç tam sayı üzerinde sabit boyutlu aritmetik ve en çok \(s^\ast-d\) ek çıkarma adımı gerektirir. Bellek kullanımı \(O(s^\ast)\)'dir; esas olarak özyineleme yığını ve küçük bir terminal durum tutulur. Pratikte belirleyici olan şey budamadır: işaret normalizasyonu, norm sınırları, şerit indirgeme ve modüler ters testi teorik dalların büyük kısmını ortadan kaldırır.
Para un entero positivo fijo \(n\), consideramos el algoritmo de Euclides sustractivo sobre un par coprimo \((n,m)\): en cada paso se sustituye el mayor por la diferencia de ambos hasta que una componente llega a 0. En el Problema 958 se minimiza ese trabajo euclídeo, y entre todas las clases residuales con trabajo mínimo se pide el menor representante positivo de la órbita
$$\{m,\ n-m,\ m^{-1},\ n-m^{-1}\}\pmod n,$$
donde \(m^{-1}\) es el inverso modular de \(m\) módulo \(n\).
Las comprobaciones incluidas en las implementaciones son
$$f(7)=2,\qquad f(89)=34,\qquad f(8191)=1856.$$
Para la entrada final \(n=1{,}000{,}000{,}000{,}039\), recorrer todos los \(m\) posibles es inviable. La solución eficaz reescribe el problema como una búsqueda en el árbol de pares primitivos asociado al algoritmo de Euclides, parte un camino óptimo cerca de su punto medio y transforma la segunda mitad en un problema de red entera reducido, seguido de una corta bajada euclídea final.
Si
$$\frac{n}{m}=[q_0,q_1,\dots,q_r]$$
es la fracción continua regular de \(n/m\), entonces el algoritmo sustractivo realiza exactamente
$$\ell(n,m)=q_0+q_1+\cdots+q_r$$
restas. Por tanto, no buscamos simplemente el menor \(m\), sino el menor \(m\) entre aquellos cuya suma de dígitos en la fracción continua es mínima.
La búsqueda se organiza mediante las dos transformaciones unimodulares
$$L=\begin{pmatrix}0&1\\1&1\end{pmatrix},\qquad R=\begin{pmatrix}1&0\\1&1\end{pmatrix},$$
que actúan sobre un par primitivo ordenado \((a,b)\) como
$$L:(a,b)\mapsto (b,a+b),\qquad R:(a,b)\mapsto (a,a+b).$$
Partiendo de \((0,1)\), estas reglas generan el árbol tipo Stern-Brocot de todos los pares primitivos no negativos. Cada movimiento añade una unidad de trabajo; así, un camino de longitud \(s\) representa una clase residual cuyo trabajo euclídeo es \(s\).
Fijado un presupuesto de trabajo \(s\), se toma
$$d=\left\lfloor\frac{s+1}{2}\right\rfloor.$$
La mitad inicial del camino se explora explícitamente hasta profundidad \(d\). Para describir la mitad restante, se mantiene un segundo vector \((c_a,c_b)\) que satisface
$$a\,c_a+b\,c_b=n.$$
La razón es que el vector de coeficientes se actualiza con la inversa transpuesta de la misma matriz aplicada a \((a,b)\):
$$L^{-T}:(c_a,c_b)\mapsto (c_b-c_a,c_a),\qquad R^{-T}:(c_a,c_b)\mapsto (c_a-c_b,c_b).$$
De este modo, cualquier punto medio de un camino mínimo válido queda sobre la recta diofántica \(a\,c_a+b\,c_b=n\).
Todas las soluciones enteras de \(a\,c_a+b\,c_b=n\) difieren en múltiplos de \((b,-a)\). Definimos
$$N=a^2+b^2,\qquad X=c_a b-c_b a.$$
Al sustituir \((c_a,c_b)\) por \((c_a+k b,c_b-k a)\), el producto escalar no cambia, pero el término cruzado pasa a
$$X\mapsto X+kN.$$
Por eso el punto medio puede trasladarse a la banda canónica \(0\le X<N\). Además, la condición
$$c_a^2+c_b^2\le N$$
impone que el vector de coeficientes no sea más largo que el vector adelantado. Tras la reducción, como mucho dos puntos de red vecinos pueden satisfacer esta cota, lo que explica por qué el código solo prueba dos candidatos terminales.
Si \(s\) es impar, el punto medio cae dentro de un paso euclídeo y no entre dos niveles completos. El programa convierte ese caso a la misma geometría mediante
$$ (a,b,c_a,c_b)\longmapsto (2a,\ 2b-a,\ 2c_a+c_b,\ 2c_b). $$
Después de esta transformación, el producto escalar conservado pasa a ser \(4n\), pero el mismo esquema de reducción y comprobación final sigue siendo válido.
Desde un punto medio válido, el trabajo restante se completa con una bajada sustractiva sobre un par \((x,y)\), acompañada por las actualizaciones duales de un par primitivo \((v_x,v_y)\). Tras ordenar \(x\le y\), un paso es
$$ (x,y,v_x,v_y)\mapsto (x,\ y-x,\ v_x+v_y,\ v_y). $$
Durante todo el proceso se conserva
$$x\,v_x+y\,v_y=n.$$
Si uno de los coeficientes llega a 0 dentro del presupuesto restante, el residuo asociado es
$$o\equiv v_x+v_y-n \pmod n.$$
Entonces se comprueba la invertibilidad de \(o\) módulo \(n\) y se puntúa el representante
$$\min\{o,\ n-o,\ o^{-1},\ n-o^{-1}\}.$$
El primer presupuesto \(s\) para el que existe un estado terminal así es precisamente el trabajo euclídeo mínimo.
Para \(n=7\) y \(m=2\), tenemos
$$\frac{7}{2}=[3,2],$$
de modo que el trabajo es \(3+2=5\). La misma cantidad aparece en toda la órbita
$$\{2,5,4,3\}=\{m,\ 7-m,\ m^{-1},\ 7-m^{-1}\},$$
porque \(2^{-1}\equiv 4\pmod 7\). El menor elemento positivo de esa órbita es \(2\), en acuerdo con el valor de validación \(f(7)=2\).
Las implementaciones en C++, Python y Java incrementan el trabajo candidato \(s\) desde 0. Para cada valor, fijan \(d=\lfloor(s+1)/2\rfloor\) y ejecutan una búsqueda en profundidad sobre estados intermedios \((a,b,c_a,c_b)\). En cada llamada se normaliza \(a\le b\), se corrige \(c_a\) sumando copias enteras de \((b,-a)\) cuando hace falta, y se descartan enseguida los estados con \(c_b<0\) o con la invariante \(a\,c_a+b\,c_b=n\) rota.
Antes de expandir un estado, el programa calcula la continuación optimista de menor crecimiento. Si ni siquiera esa continuación puede alcanzar una norma terminal suficiente, toda la rama se elimina. Las desigualdades resultantes son
$$x^2+y^2\ge n$$
en el caso par, y
$$x^2+xy+\frac{5}{4}y^2\ge n$$
en la geometría de punto medio impar.
En profundidad \(d\), el código aplica la conversión impar cuando procede, calcula \(N\) y \(X\), y desplaza el vector de coeficientes a la banda \(0\le X<N\). Como después de eso solo dos puntos vecinos pueden seguir cumpliendo \(c_a^2+c_b^2\le N\), la implementación realiza exactamente dos comprobaciones terminales.
Cada candidato terminal superviviente se completa con una cadena euclídea sustractiva acotada. En el caso impar, primero se deshace la conversión del punto medio mediante comprobaciones de paridad para volver al espacio entero original. Si el descenso termina dentro del presupuesto disponible, se calcula \(o\), se verifica su inverso modular y se actualiza la mejor respuesta usando el criterio "menor trabajo primero, menor representante de la órbita después".
Si el trabajo euclídeo mínimo es \(s^\ast\), una búsqueda ingenua sobre todas las palabras de longitud \(s^\ast\) sería exponencial. La división en el punto medio reduce la profundidad explorada explícitamente a aproximadamente \(s^\ast/2\), de modo que la forma bruta de la búsqueda se parece más a \(O(2^{s^\ast/2})\) estados intermedios que a \(O(2^{s^\ast})\) caminos completos.
Cada estado superviviente solo necesita aritmética de tamaño constante sobre unos pocos enteros y, como mucho, \(s^\ast-d\) restas adicionales. El uso de memoria es \(O(s^\ast)\), esencialmente por la pila recursiva y un pequeño conjunto de datos terminales. En la práctica manda la poda: la normalización de signos, las cotas de norma, la reducción a banda y la prueba de inversibilidad eliminan casi todas las ramas teóricas.
固定一个正整数 \(n\)，考虑互素整数对 \((n,m)\) 上的减法版欧几里得算法：每一步都把较大的数替换为两数之差，直到其中一个数变成 0。Problem 958 要最小化的就是这种“欧几里得劳动量”；在所有达到最小劳动量的剩余类中，再取下面这个对称轨道里的最小正代表：
$$\{m,\ n-m,\ m^{-1},\ n-m^{-1}\}\pmod n,$$
其中 \(m^{-1}\) 表示 \(m\) 在模 \(n\) 意义下的乘法逆元。
实现中内置的校验值是
$$f(7)=2,\qquad f(89)=34,\qquad f(8191)=1856.$$
对于最终输入 \(n=1{,}000{,}000{,}000{,}039\)，不可能把所有 \(1\le m<n\) 的候选都逐个检查。真正可行的做法，是把问题改写成欧几里得原始状态树上的搜索，在最短路径附近做一次中点切分，再把后半段转化为一个经过约化的整数格问题，最后接上一小段受限的欧几里得下降。
如果
$$\frac{n}{m}=[q_0,q_1,\dots,q_r]$$
是 \(n/m\) 的正规连分数展开，那么减法版欧几里得算法恰好执行
$$\ell(n,m)=q_0+q_1+\cdots+q_r$$
次减法。也就是说，题目并不是单纯寻找最小的 \(m\)，而是先找出连分数数字和最小的那些剩余类，再在其中取最小代表。
搜索使用两个 unimodular 变换
$$L=\begin{pmatrix}0&1\\1&1\end{pmatrix},\qquad R=\begin{pmatrix}1&0\\1&1\end{pmatrix},$$
它们对有序原始对 \((a,b)\) 的作用分别是
$$L:(a,b)\mapsto (b,a+b),\qquad R:(a,b)\mapsto (a,a+b).$$
从 \((0,1)\) 出发，这两个操作会生成 Stern-Brocot 风格的全部非负原始整数对。每走一步，劳动量增加 1，因此长度为 \(s\) 的路径就对应一个欧几里得劳动量为 \(s\) 的候选剩余类。
对一个试探预算 \(s\)，代码令
$$d=\left\lfloor\frac{s+1}{2}\right\rfloor.$$
前半段路径显式搜索到深度 \(d\)。为了表示后半段，程序同时维护一个系数向量 \((c_a,c_b)\)，满足线性不变量
$$a\,c_a+b\,c_b=n.$$
之所以能保持这个不变量，是因为当 \((a,b)\) 被某个矩阵更新时，系数向量使用同一矩阵的逆转置更新：
$$L^{-T}:(c_a,c_b)\mapsto (c_b-c_a,c_a),\qquad R^{-T}:(c_a,c_b)\mapsto (c_a-c_b,c_b).$$
因此，任何有效最短路径的中点都必须落在那条丢番图直线 \(a\,c_a+b\,c_b=n\) 上。
方程 \(a\,c_a+b\,c_b=n\) 的所有整数解彼此相差 \((b,-a)\) 的整数倍。定义
$$N=a^2+b^2,\qquad X=c_a b-c_b a.$$
如果把 \((c_a,c_b)\) 改成 \((c_a+k b,c_b-k a)\)，那么点积不变，但交叉项会变成
$$X\mapsto X+kN.$$
所以可以把中点平移到标准条带 \(0\le X<N\) 中。再加上长度约束
$$c_a^2+c_b^2\le N,$$
就表示系数向量的长度不能超过前向向量。经过这种条带约化之后，最多只有两个相邻的格点还能满足范数条件，这正是终端阶段只需要检查两个候选点的原因。
当 \(s\) 为奇数时，中点不是落在两层完整状态之间，而是落在某一步欧几里得操作的内部。代码通过
$$ (a,b,c_a,c_b)\longmapsto (2a,\ 2b-a,\ 2c_a+c_b,\ 2c_b) $$
把这个情况改写到同一套几何框架中。变换之后保持的不再是 \(n\)，而是 \(4n\)，但后面的范数约化、交叉项归约与终端检查全部仍然适用。
从一个合法中点出发，剩余的劳动量通过系数对 \((x,y)\) 上的减法欧几里得下降来完成，同时伴随一个原始对 \((v_x,v_y)\) 的对偶更新。整理成 \(x\le y\) 之后，一步更新是
$$ (x,y,v_x,v_y)\mapsto (x,\ y-x,\ v_x+v_y,\ v_y). $$
在整个过程中始终保持
$$x\,v_x+y\,v_y=n.$$
如果在剩余预算内有一个系数降为 0，那么对应的剩余类就是
$$o\equiv v_x+v_y-n \pmod n.$$
接下来检查 \(o\) 是否在模 \(n\) 下可逆，并对对称轨道代表值
$$\min\{o,\ n-o,\ o^{-1},\ n-o^{-1}\}$$
打分。第一次出现这种终态的预算 \(s\)，就是最小欧几里得劳动量。
以 \(n=7\)、\(m=2\) 为例，有
$$\frac{7}{2}=[3,2],$$
因此劳动量是 \(3+2=5\)。整个对称轨道
$$\{2,5,4,3\}=\{m,\ 7-m,\ m^{-1},\ 7-m^{-1}\}$$
都具有同样的劳动量，因为 \(2^{-1}\equiv 4\pmod 7\)。这个轨道中的最小正整数是 \(2\)，所以校验值 \(f(7)=2\) 正好成立。更大的 \(f(89)=34\) 与 \(f(8191)=1856\) 只是同一机制在更深最短路径上的体现。
C++、Python 和 Java 实现都从 \(s=0\) 开始逐步增加候选劳动量。对每个 \(s\)，先设 \(d=\lfloor(s+1)/2\rfloor\)，然后对中点状态 \((a,b,c_a,c_b)\) 做深度优先搜索。每次递归都会先把顺序规范化为 \(a\le b\)，必要时沿 \((b,-a)\) 方向整体平移以修正 \(c_a\)，并立刻丢弃那些 \(c_b<0\) 或破坏不变量 \(a\,c_a+b\,c_b=n\) 的状态。
在继续向下搜索之前，程序会计算一种“最慢增长”的乐观延拓。如果连这种最有利的延拓都无法让终端范数达到要求，那么整棵子树都不可能成功。对应的不等式是
$$x^2+y^2\ge n$$
用于偶数预算，而
$$x^2+xy+\frac{5}{4}y^2\ge n$$
用于奇数中点几何。这些剪枝对实际运行时间非常关键。
到达深度 \(d\) 后，如果预算是奇数，就先执行中点变换；然后计算 \(N\) 和 \(X\)，把系数向量移动到 \(0\le X<N\) 的标准条带里。由于此时满足 \(c_a^2+c_b^2\le N\) 的候选最多只剩下两个相邻格点，代码只做两次终端检查：当前约化点，以及再减去一份 \((b,-a)\) 得到的那个相邻点。
每个幸存的终端候选都会接上一段受限长度的减法欧几里得过程。若预算为奇数，先通过奇偶性检查把中点变换逆回原始整数状态空间，然后再执行同一套下降逻辑。只要能在剩余预算内结束，就计算 \(o\)，测试模逆是否存在，并按“劳动量更小优先，轨道代表更小次之”的规则更新当前最优答案。
设最小欧几里得劳动量为 \(s^\ast\)。如果直接枚举所有长度为 \(s^\ast\) 的路径，复杂度会是指数级。中点切分把显式搜索深度降到了大约 \(s^\ast/2\)，因此整体搜索形状更接近 \(O(2^{s^\ast/2})\) 个中点状态，而不是 \(O(2^{s^\ast})\) 条完整路径。
每个存活的中点只需要在少数几个整数上做常数规模运算，再加上最多 \(s^\ast-d\) 步减法下降。内存使用是 \(O(s^\ast)\)，因为主要只保留递归栈和一个很小的终端状态。实际表现远好于理论上界，原因就在于符号规范化、范数界、条带约化和模逆测试会提前淘汰绝大多数分支。
Для фиксированного положительного числа \(n\) рассматривается вычитательная версия алгоритма Евклида для взаимно простых \((n,m)\): на каждом шаге большее число заменяется разностью двух чисел, пока один из элементов не станет равен 0. В Problem 958 минимизируется именно такой «труд Евклида», а затем среди всех классов вычетов с минимальным трудом выбирается наименьший положительный представитель орбиты
$$\{m,\ n-m,\ m^{-1},\ n-m^{-1}\}\pmod n,$$
где \(m^{-1}\) означает мультипликативную обратную величину по модулю \(n\).
Встроенные контрольные значения таковы:
$$f(7)=2,\qquad f(89)=34,\qquad f(8191)=1856.$$
Для итогового входа \(n=1{,}000{,}000{,}000{,}039\) прямой перебор всех \(m\) невозможен. Рабочее решение переписывает задачу как поиск в дереве примитивных евклидовых состояний, разрезает кратчайший путь около середины и превращает вторую половину в задачу о редуцированной решетке, после чего остается короткий финальный евклидов спуск.
Если
$$\frac{n}{m}=[q_0,q_1,\dots,q_r]$$
есть обычная непрерывная дробь для \(n/m\), то вычитательный алгоритм Евклида выполнит ровно
$$\ell(n,m)=q_0+q_1+\cdots+q_r$$
вычитаний. Значит, задача состоит не в том, чтобы найти просто наименьшее \(m\), а в том, чтобы найти наименьшее \(m\) среди классов с минимальной суммой коэффициентов непрерывной дроби.
Поиск организован двумя unimodular-преобразованиями
$$L=\begin{pmatrix}0&1\\1&1\end{pmatrix},\qquad R=\begin{pmatrix}1&0\\1&1\end{pmatrix},$$
которые действуют на упорядоченную примитивную пару \((a,b)\) так:
$$L:(a,b)\mapsto (b,a+b),\qquad R:(a,b)\mapsto (a,a+b).$$
Начиная с \((0,1)\), эти переходы порождают дерево типа Stern-Brocot из всех неотрицательных примитивных пар. Каждый ход добавляет единицу к труду Евклида, поэтому путь длины \(s\) соответствует классу вычетов с трудом \(s\).
Для пробного бюджета \(s\) берется
$$d=\left\lfloor\frac{s+1}{2}\right\rfloor.$$
Первая половина пути явно просматривается до глубины \(d\). Чтобы описать вторую половину, поддерживается вектор коэффициентов \((c_a,c_b)\), удовлетворяющий инварианту
$$a\,c_a+b\,c_b=n.$$
Он сохраняется потому, что коэффициентный вектор обновляется обратной транспонированной матрицей того же шага:
$$L^{-T}:(c_a,c_b)\mapsto (c_b-c_a,c_a),\qquad R^{-T}:(c_a,c_b)\mapsto (c_a-c_b,c_b).$$
Следовательно, каждая допустимая середина кратчайшего пути лежит на диофантовой прямой \(a\,c_a+b\,c_b=n\).
Все целочисленные решения уравнения \(a\,c_a+b\,c_b=n\) отличаются на кратные вектора \((b,-a)\). Обозначим
$$N=a^2+b^2,\qquad X=c_a b-c_b a.$$
Если заменить \((c_a,c_b)\) на \((c_a+k b,c_b-k a)\), скалярное произведение не изменится, а перекрестный член перейдет в
$$X\mapsto X+kN.$$
Поэтому середину можно сдвинуть в каноническую полосу \(0\le X<N\). Дополнительное условие
$$c_a^2+c_b^2\le N$$
означает, что вектор коэффициентов не длиннее прямого вектора. После такой редукции остается не более двух соседних узлов решетки, которые еще могут удовлетворять нормовой границе; именно поэтому терминальная проверка тестирует только два кандидата.
Когда \(s\) нечетно, середина попадает не между двумя полными уровнями, а внутрь одного евклидова шага. Этот случай приводится к той же геометрии заменой
$$ (a,b,c_a,c_b)\longmapsto (2a,\ 2b-a,\ 2c_a+c_b,\ 2c_b). $$
После этого сохраняемое скалярное произведение становится равным \(4n\), но вся дальнейшая логика редукции и завершения остается той же.
Из допустимой середины оставшийся труд добирается вычитательным спуском по коэффициентам \((x,y)\) вместе с двойственным обновлением примитивной пары \((v_x,v_y)\). После упорядочения \(x\le y\) один шаг имеет вид
$$ (x,y,v_x,v_y)\mapsto (x,\ y-x,\ v_x+v_y,\ v_y). $$
При этом сохраняется
$$x\,v_x+y\,v_y=n.$$
Если один коэффициент обращается в 0 в пределах оставшегося бюджета, получается вычет
$$o\equiv v_x+v_y-n \pmod n.$$
Затем проверяется обратимость \(o\) по модулю \(n\), и оценивается представитель орбиты
$$\min\{o,\ n-o,\ o^{-1},\ n-o^{-1}\}.$$
Первое значение \(s\), при котором существует такой терминальный узел, и есть минимальный труд Евклида.
Для \(n=7\) и \(m=2\)
$$\frac{7}{2}=[3,2],$$
поэтому труд равен \(3+2=5\). Та же величина появляется на всей орбите
$$\{2,5,4,3\}=\{m,\ 7-m,\ m^{-1},\ 7-m^{-1}\},$$
поскольку \(2^{-1}\equiv 4\pmod 7\). Наименьший положительный элемент этой орбиты равен \(2\), что и дает проверочное значение \(f(7)=2\).
Реализации на C++, Python и Java постепенно увеличивают кандидатный труд \(s\), начиная с 0. Для каждого \(s\) берется \(d=\lfloor(s+1)/2\rfloor\), после чего запускается поиск в глубину по промежуточным состояниям \((a,b,c_a,c_b)\). На каждом шаге поддерживается нормализация \(a\le b\), коэффициент \(c_a\) при необходимости сдвигается вдоль \((b,-a)\), а состояния с \(c_b<0\) или с нарушенным инвариантом \(a\,c_a+b\,c_b=n\) отбрасываются немедленно.
Перед дальнейшим спуском программа вычисляет оптимистическое продолжение с наименьшим ростом нормы. Если даже оно не может дотянуться до допустимой терминальной нормы, вся ветвь невозможна. В результате используются оценки
$$x^2+y^2\ge n$$
для четного бюджета и
$$x^2+xy+\frac{5}{4}y^2\ge n$$
для нечетной геометрии середины.
На глубине \(d\) код, если нужно, применяет нечетное преобразование, затем вычисляет \(N\) и \(X\) и переносит коэффициентный вектор в полосу \(0\le X<N\). После этого условию \(c_a^2+c_b^2\le N\) могут удовлетворять не более двух соседних точек решетки, поэтому терминальная стадия выполняет ровно две проверки.
Каждый выживший терминальный кандидат завершается ограниченной вычитательной евклидовой цепочкой. Для нечетного бюджета сначала проверяются четности и отменяется преобразование середины, чтобы работать в исходном целочисленном пространстве. Если спуск укладывается в оставшийся бюджет, вычисляется \(o\), проверяется существование обратного по модулю, а лучшая пара обновляется по правилу «сначала меньший труд, затем меньший представитель орбиты».
Если минимальный труд Евклида равен \(s^\ast\), то наивный перебор всех слов длины \(s^\ast\) был бы экспоненциальным. Разрез посередине уменьшает явно просматриваемую глубину примерно до \(s^\ast/2\), так что грубая форма поиска ближе к \(O(2^{s^\ast/2})\) промежуточных состояний, чем к \(O(2^{s^\ast})\) полных путей.
Каждая выжившая середина требует лишь арифметики над несколькими целыми числами и максимум \(s^\ast-d\) дополнительных вычитаний. Память равна \(O(s^\ast)\), поскольку хранятся в основном рекурсивный стек и небольшой терминальный набор данных. На практике главную роль играет отсечение: нормализация знаков, нормовые границы, редукция к полосе и проверка обратимости уничтожают подавляющее большинство теоретических ветвей.
لعدد صحيح موجب ثابت \(n\)، ننظر إلى خوارزمية إقليدس الطرحية على الزوج المتباين أوليًا \((n,m)\): في كل خطوة نستبدل العدد الأكبر بفرق العددين حتى تصبح إحدى القيمتين صفرًا. الكمية التي تُصغَّر في Problem 958 هي هذا «الجهد الإقليدي»، ثم نأخذ أصغر ممثل موجب داخل المدار
$$\{m,\ n-m,\ m^{-1},\ n-m^{-1}\}\pmod n,$$
حيث \(m^{-1}\) هو المعكوس الضربي لـ \(m\) بترديد \(n\).
قيم التحقق المضمنة في التطبيقات هي
$$f(7)=2,\qquad f(89)=34,\qquad f(8191)=1856.$$
عند الإدخال النهائي \(n=1{,}000{,}000{,}000{,}039\) يصبح فحص جميع القيم \(m\) مستحيلًا عمليًا. لذلك تعيد الحلول صياغة المسألة على أنها بحث داخل شجرة الأزواج البدائية المرتبطة بخطوات إقليدس، ثم تقسِّم المسار الأمثل قرب منتصفه، وتحول النصف الثاني إلى مسألة شبكية صحيحة مختزلة يتبعها نزول إقليدي قصير لإنهاء الحالة.
إذا كان
$$\frac{n}{m}=[q_0,q_1,\dots,q_r]$$
هو التمثيل بالكسر المستمر المنتظم لـ \(n/m\)، فإن خوارزمية إقليدس الطرحية تنفذ بالضبط
$$\ell(n,m)=q_0+q_1+\cdots+q_r$$
عملية طرح. إذن المطلوب ليس أصغر \(m\) على الإطلاق، بل أصغر \(m\) بين البواقي التي تحقق أصغر مجموع لمعاملات الكسر المستمر.
ينظم البحث التحويلان أحاديا المحدد
$$L=\begin{pmatrix}0&1\\1&1\end{pmatrix},\qquad R=\begin{pmatrix}1&0\\1&1\end{pmatrix},$$
اللذان يؤثران في الزوج البدائي المرتب \((a,b)\) كما يلي:
$$L:(a,b)\mapsto (b,a+b),\qquad R:(a,b)\mapsto (a,a+b).$$
انطلاقًا من \((0,1)\) نحصل على شجرة من نمط Stern-Brocot تولد جميع الأزواج البدائية غير السالبة. كل انتقال يضيف وحدة واحدة إلى الجهد الإقليدي، ولذلك فإن مسارًا طوله \(s\) يمثل فئة بواقي يكون جهدها \(s\).
لميزانية تجربة مقدارها \(s\)، يُعرَّف
$$d=\left\lfloor\frac{s+1}{2}\right\rfloor.$$
يُستكشف النصف الأمامي من المسار صراحة حتى العمق \(d\). ولتمثيل النصف الخلفي، تُحمَل متجهة معاملات \((c_a,c_b)\) تحقق الثابت
$$a\,c_a+b\,c_b=n.$$
يبقى هذا الثابت صحيحًا لأن متجهة المعاملات تُحدَّث بالمصفوفة المعكوسة المنقولة لنفس التحويل المستعمل على \((a,b)\):
$$L^{-T}:(c_a,c_b)\mapsto (c_b-c_a,c_a),\qquad R^{-T}:(c_a,c_b)\mapsto (c_a-c_b,c_b).$$
إذًا فكل نقطة وسط صحيحة لمسار أقصر ممكن لا بد أن تقع على المستقيم الديوفانتي \(a\,c_a+b\,c_b=n\).
كل الحلول الصحيحة للمعادلة \(a\,c_a+b\,c_b=n\) تختلف بمضاعفات المتجه \((b,-a)\). نعرّف
$$N=a^2+b^2,\qquad X=c_a b-c_b a.$$
إذا استبدلنا \((c_a,c_b)\) بـ \((c_a+k b,c_b-k a)\)، فإن الجداء القياسي لا يتغير، لكن الحد المتقاطع يتحول إلى
$$X\mapsto X+kN.$$
ولذلك يمكن نقل نقطة الوسط إلى الشريط القياسي \(0\le X<N\). ويضيف الشرط
$$c_a^2+c_b^2\le N$$
أن طول متجهة المعاملات يجب ألا يتجاوز طول المتجهة الأمامية. بعد هذا الاختزال لا يبقى إلا نقطتان شبكيتان متجاورتان على الأكثر يمكن أن تستوفيا شرط المعيار، ولهذا يكتفي التنفيذ باختبار مرشحين نهائيين فقط.
إذا كانت \(s\) فردية، فإن نقطة الوسط تقع داخل خطوة إقليدية واحدة لا بين مستويين كاملين. يعالج التنفيذ ذلك بالتحويل
$$ (a,b,c_a,c_b)\longmapsto (2a,\ 2b-a,\ 2c_a+c_b,\ 2c_b). $$
بعد هذا التحويل تصبح قيمة الجداء القياسي المحفوظ \(4n\)، لكن تبقى بنية الاختزال وفحص النهاية كما هي.
من نقطة وسط صالحة، يُستكمل الجهد المتبقي عبر نزول إقليدي طرحي على الزوج \((x,y)\)، وبالتوازي مع تحديث مزدوج للزوج البدائي \((v_x,v_y)\). بعد ترتيب \(x\le y\)، تكون الخطوة الواحدة
$$ (x,y,v_x,v_y)\mapsto (x,\ y-x,\ v_x+v_y,\ v_y). $$
ويظل الثابت
$$x\,v_x+y\,v_y=n$$
صحيحًا طوال العملية. فإذا وصل أحد المعاملين إلى 0 ضمن الميزانية المتبقية، كان الباقي الموافق هو
$$o\equiv v_x+v_y-n \pmod n.$$
ثم يُفحص ما إذا كان \(o\) قابلاً للعكس بترديد \(n\)، وتُقيَّم أصغر قيمة في المدار
$$\min\{o,\ n-o,\ o^{-1},\ n-o^{-1}\}.$$
وأول ميزانية \(s\) يظهر عندها مثل هذا الطرف النهائي هي بالضبط أقل جهد إقليدي ممكن.
عندما \(n=7\) و\(m=2\)، فإن
$$\frac{7}{2}=[3,2],$$
ومن ثم يكون الجهد \(3+2=5\). ويظهر الجهد نفسه على المدار الكامل
$$\{2,5,4,3\}=\{m,\ 7-m,\ m^{-1},\ 7-m^{-1}\},$$
لأن \(2^{-1}\equiv 4\pmod 7\). أصغر عنصر موجب في هذا المدار هو \(2\)، وهذا يفسر قيمة التحقق \(f(7)=2\).
تزيد تطبيقات C++ وPython وJava قيمة الجهد المرشحة \(s\) بدءًا من 0. لكل قيمة، تُضبط \(d=\lfloor(s+1)/2\rfloor\) ثم يُجرى بحث عمق أول على حالات الوسط \((a,b,c_a,c_b)\). في كل نداء تُطبَّق أولًا تسوية \(a\le b\)، ثم يُرفع \(c_a\) بإضافة نسخ صحيحة من \((b,-a)\) عند الحاجة، وتُرفض فورًا الحالات التي تحقق \(c_b<0\) أو تكسر الثابت \(a\,c_a+b\,c_b=n\).
قبل النزول أعمق، يحسب التنفيذ امتدادًا متفائلًا بأصغر نمو ممكن. فإذا كان هذا الامتداد نفسه غير قادر على بلوغ معيار نهائي كافٍ، تُقطع الشجرة الفرعية كلها. وتنتج من ذلك الاختبارات
$$x^2+y^2\ge n$$
في الحالة الزوجية، و
$$x^2+xy+\frac{5}{4}y^2\ge n$$
في هندسة المنتصف الفردية.
عند العمق \(d\) يُطبَّق تحويل الحالة الفردية إذا لزم الأمر، ثم يُحسب \(N\) و\(X\) وتُنقل متجهة المعاملات إلى الشريط \(0\le X<N\). وبعد ذلك لا يبقى إلا احتمال نقطتين شبكيتين متجاورتين تحققان الشرط \(c_a^2+c_b^2\le N\)، ولهذا يجري التنفيذ فحصين نهائيين فقط.
كل مرشح نهائي ناجٍ يُكمَّل بسلسلة إقليدية طرحية محدودة الطول. وفي الميزانية الفردية، تُفك أولًا عملية تحويل المنتصف عبر فحوص التكافؤ حتى يعود التنفيذ إلى فضاء الأعداد الصحيحة الأصلي. وإذا انتهى النزول ضمن الميزانية المتبقية، يُحسب \(o\)، ويُختبر وجود معكوسه المعياري، ثم يُحدَّث أفضل جواب وفق المعيار: جهد أقل أولًا، ثم ممثل مداري أصغر ثانيًا.
إذا كان أقل جهد إقليدي هو \(s^\ast\)، فإن البحث الساذج في جميع الكلمات ذات الطول \(s^\ast\) سيكون أسيًا. تقسيم المسار عند المنتصف يخفض العمق المستكشف صراحة إلى نحو \(s^\ast/2\)، ولذلك يصبح الشكل الخام للبحث أقرب إلى \(O(2^{s^\ast/2})\) من حالات الوسط بدلًا من \(O(2^{s^\ast})\) من المسارات الكاملة.
كل نقطة وسط باقية تحتاج فقط إلى عمليات حسابية محدودة على عدد صغير من القيم الصحيحة، إضافة إلى ما لا يزيد على \(s^\ast-d\) خطوة طرحية نهائية. استهلاك الذاكرة هو \(O(s^\ast)\) لأن المخزن الأساسي هو مكدس الاستدعاء مع حالة نهائية صغيرة. أما عمليًا، فالقوة الحاسمة تأتي من القطع: تسوية الإشارات، وحدود المعيار، واختزال الشريط، وفحص المعكوس المعياري تزيل معظم الفروع النظرية قبل أن تكبر.