Starting from a triple \((a,b,c)\), one move reflects exactly one coordinate:
$$ (a,b,c)\to (2(b+c)-a,b,c),\quad (a,b,c)\to (a,2(c+a)-b,c),\quad (a,b,c)\to (a,b,2(a+b)-c). $$
For fixed positive integers \(a\) and \(b\), the relevant positive values of \(c\) are exactly those for which
$$ (a+b-c)^2-4ab $$
is a perfect square. If \(T(a,b,c)\) denotes the minimum number of moves needed to make at least one coordinate equal to \(0\), then
$$ F(a,b)=\sum T(a,b,c), $$
where the sum runs over all such positive \(c\). The Project Euler task asks for
$$ \sum_{k=1}^{18} F(2^k3^k,2^k5^k). $$
A direct graph search is useful only for very small checks. The full solution replaces that search by a divisor-pair parametrization and by counting reflection steps through the Euclidean algorithm.
Fix \(a\) and \(b\). The goal is to describe all admissible third coordinates \(c\), then evaluate the minimal distance to a zero coordinate for each of them.
Set
$$ u=\lvert a+b-c\rvert. $$
The admissibility condition used by the implementations is that
$$ (a+b-c)^2-4ab=s^2 $$
for some integer \(s\). With \(u=\lvert a+b-c\rvert\), this becomes
$$ u^2-s^2=4ab. $$
So every admissible state is encoded by a factorization of \(4ab\) as a difference of two squares.
Write
$$ (u-s)(u+s)=4ab. $$
Define
$$ q=u-s,\qquad p=u+s. $$
Then \(pq=4ab\), \(p\ge q>0\), and \(p+q=2u\) is even. Conversely, every factor pair
$$ pq=4ab,\qquad p\ge q,\qquad p+q\text{ even} $$
recovers
$$ u=\frac{p+q}{2},\qquad s=\frac{p-q}{2}. $$
This replaces the original search over \(c\) by a finite search over divisor pairs of \(4ab\).
Since \(u=\lvert a+b-c\rvert\), the corresponding third coordinates are
$$ c_-=a+b+u,\qquad c_+=a+b-u. $$
The larger branch \(c_-\) is always positive. The smaller branch \(c_+\) is admissible only when
$$ a+b-u>0 \iff \frac{p+q}{2}<a+b \iff p+q<2(a+b). $$
If equality holds, then \(c_+=0\), which is excluded because the sum defining \(F(a,b)\) only uses positive third coordinates.
For positive integers \(x\ge y\), run the ordinary Euclidean algorithm
$$ x=q_0y+r_0,\qquad y=q_1r_0+r_1,\qquad \dots,\qquad r_{m-2}=q_m r_{m-1}. $$
Define the quotient sum
$$ E(x,y)=q_0+q_1+\cdots+q_m. $$
This is exactly the number of subtraction steps compressed by the division form of Euclid's algorithm. For a divisor pair \((p,q)\), the reflection system reduces to two possible Euclidean chains, one aiming to eliminate \(a\) and one aiming to eliminate \(b\). Their lengths are
$$ E(2a,q)\qquad\text{and}\qquad E(2b,q), $$
so the optimal distance for the larger branch is
$$ f(p,q)=\min\bigl(E(2a,q),E(2b,q)\bigr). $$
The two branches are consecutive along the same reflection chain, because reflecting the third coordinate sends
$$ 2(a+b)-c_-=2(a+b)-(a+b+u)=a+b-u=c_+. $$
Therefore \(c_-\) contributes \(f(p,q)\), while the smaller branch \(c_+\) contributes one less move, namely \(f(p,q)-1\), whenever \(c_+\) is positive.
Summing over all factor pairs gives
$$ F(a,b)= \sum_{\substack{pq=4ab\\ q\le p\\ p+q\text{ even}}} \left( f(p,q)+ \begin{cases} f(p,q)-1, & p+q<2(a+b),\\ 0, & p+q\ge 2(a+b). \end{cases} \right). $$
This is the exact formula evaluated by the implementations.
For the actual problem,
$$ a=2^k3^k,\qquad b=2^k5^k, $$
so
$$ 4ab=2^{2k+2}3^k5^k. $$
Hence every divisor \(q\) of \(4ab\) has the form
$$ q=2^{e_2}3^{e_3}5^{e_5}, \qquad 0\le e_2\le 2k+2, \qquad 0\le e_3,e_5\le k. $$
That is why the implementation can enumerate all candidates by three nested loops over exponents, then recover \(p=(4ab)/q\) and apply the filters \(q\le p\) and \(p+q\) even.
Take \(k=1\). Then
$$ a=6,\qquad b=10,\qquad 4ab=240. $$
The valid factor pairs with \(q\le p\) and \(p+q\) even are
$$ (p,q)\in\{(120,2),(60,4),(40,6),(30,8),(24,10),(20,12)\}. $$
Now compute the Euclidean quotient sums:
$$ \begin{aligned} q=2&:& E(12,2)=6,\quad E(20,2)=10,\quad f=6,\\ q=4&:& E(12,4)=3,\quad E(20,4)=5,\quad f=3,\\ q=6&:& E(12,6)=2,\quad E(20,6)=6,\quad f=2,\\ q=8&:& E(12,8)=3,\quad E(20,8)=4,\quad f=3,\\ q=10&:& E(12,10)=6,\quad E(20,10)=2,\quad f=2,\\ q=12&:& E(12,12)=1,\quad E(20,12)=4,\quad f=1. \end{aligned} $$
Here \(2(a+b)=32\), and every valid pair has \(p+q\ge 32\), so the smaller branch never contributes a positive \(c\). Therefore
$$ F(6,10)=6+3+2+3+2+1=17, $$
which matches the sample check used by the implementation.
The C++, Python, and Java implementations all follow the same arithmetic plan. First they precompute the powers of \(2\), \(3\), and \(5\) needed to build \(a\), \(b\), and \(4ab\) for every \(1\le k\le 18\). For each \(k\), they enumerate all divisors \(q\) of \(4ab\) through the exponent ranges above, set \(p=(4ab)/q\), and discard pairs with \(q>p\) or odd \(p+q\).
For each surviving divisor pair they evaluate two Euclidean quotient sums, one for \((2a,q)\) and one for \((2b,q)\), keep the smaller of the two, and add the two branch contributions exactly as in the closed formula. The C++ implementation parallelizes independent values of \(k\); the Python and Java implementations perform the same computation sequentially.
Small internal checks confirm the derived formula on tiny cases and on the checkpoints
$$ F(6,10)=17,\qquad F(36,100)=179. $$
For a fixed \(k\), the raw divisor enumeration uses
$$ (2k+3)(k+1)^2 $$
choices of \((e_2,e_3,e_5)\). Each surviving choice performs two Euclidean algorithms, and each Euclidean computation takes \(O(\log(4ab))\) division steps. So the arithmetic cost for one \(k\) is
$$ O\bigl((2k+3)(k+1)^2\log(4ab)\bigr). $$
If one generalizes the upper limit from \(18\) to \(K\), then the total candidate count is
$$ \sum_{k=1}^{K}(2k+3)(k+1)^2=O(K^4). $$
The memory usage is \(O(1)\) beyond the small power tables and loop variables.
Ausgehend von einem Tripel \((a,b,c)\) darf in einem Zug genau eine Koordinate gespiegelt werden:
$$ (a,b,c)\to (2(b+c)-a,b,c),\quad (a,b,c)\to (a,2(c+a)-b,c),\quad (a,b,c)\to (a,b,2(a+b)-c). $$
Für feste positive ganze Zahlen \(a\) und \(b\) sind genau diejenigen positiven Werte \(c\) relevant, für die
$$ (a+b-c)^2-4ab $$
ein Quadrat ist. Bezeichnet \(T(a,b,c)\) die minimale Zugzahl, bis mindestens eine Koordinate \(0\) wird, dann ist
$$ F(a,b)=\sum T(a,b,c), $$
wobei über alle solchen positiven \(c\) summiert wird. Gesucht ist schließlich
$$ \sum_{k=1}^{18} F(2^k3^k,2^k5^k). $$
Eine direkte Breitensuche reicht nur für sehr kleine Tests. Die eigentliche Lösung ersetzt die Graphsuche durch eine Parametrisierung über Teilerpaare und eine Zählung mittels euklidischem Algorithmus.
Fixiere \(a\) und \(b\). Dann müssen erst alle zulässigen dritten Koordinaten \(c\) beschrieben und danach ihre Distanzen zu einem Zustand mit Null-Koordinate ausgewertet werden.
Setze
$$ u=\lvert a+b-c\rvert. $$
Die von den Implementierungen benutzte Zulässigkeitsbedingung lautet
$$ (a+b-c)^2-4ab=s^2 $$
für ein ganzzahliges \(s\). Mit \(u=\lvert a+b-c\rvert\) wird daraus
$$ u^2-s^2=4ab. $$
Jeder zulässige Zustand entspricht also einer Darstellung von \(4ab\) als Differenz zweier Quadrate.
Schreibe
$$ (u-s)(u+s)=4ab. $$
Definiere
$$ q=u-s,\qquad p=u+s. $$
Dann gilt \(pq=4ab\), \(p\ge q>0\) und \(p+q=2u\) ist gerade. Umgekehrt rekonstruiert jedes Teilerpaar
$$ pq=4ab,\qquad p\ge q,\qquad p+q\text{ gerade} $$
die Größen
$$ u=\frac{p+q}{2},\qquad s=\frac{p-q}{2}. $$
Damit wird die ursprüngliche Suche über \(c\) auf eine endliche Suche über Teilerpaare von \(4ab\) reduziert.
Aus \(u=\lvert a+b-c\rvert\) folgen die beiden Kandidaten
$$ c_-=a+b+u,\qquad c_+=a+b-u. $$
Der größere Zweig \(c_-\) ist immer positiv. Der kleinere Zweig \(c_+\) ist nur dann zulässig, wenn
$$ a+b-u>0 \iff \frac{p+q}{2}<a+b \iff p+q<2(a+b). $$
Im Gleichheitsfall wäre \(c_+=0\) und damit nicht Teil der Summe.
Für positive ganze Zahlen \(x\ge y\) betrachten wir den gewöhnlichen euklidischen Algorithmus
$$ x=q_0y+r_0,\qquad y=q_1r_0+r_1,\qquad \dots,\qquad r_{m-2}=q_m r_{m-1}. $$
Definiere die Quotientensumme durch
$$ E(x,y)=q_0+q_1+\cdots+q_m. $$
Das ist genau die Anzahl der Subtraktionsschritte, die in der Divisionsform des euklidischen Algorithmus zusammengefasst werden. Für ein Teilerpaar \((p,q)\) zerfällt das Reflexionssystem in zwei mögliche Reduktionsketten, eine zum Eliminieren von \(a\) und eine zum Eliminieren von \(b\). Ihre Längen sind
$$ E(2a,q)\qquad\text{und}\qquad E(2b,q), $$
also ist die optimale Distanz des größeren Zweigs
$$ f(p,q)=\min\bigl(E(2a,q),E(2b,q)\bigr). $$
Die beiden Zweige liegen auf derselben Reflexionskette direkt hintereinander, denn eine Spiegelung der dritten Koordinate sendet
$$ 2(a+b)-c_-=2(a+b)-(a+b+u)=a+b-u=c_+. $$
Daher trägt \(c_-\) den Wert \(f(p,q)\) bei, während \(c_+\) genau einen Zug weniger beiträgt, also \(f(p,q)-1\), sofern \(c_+\) positiv ist.
Durch Summation über alle Teilerpaare erhält man
$$ F(a,b)= \sum_{\substack{pq=4ab\\ q\le p\\ p+q\text{ gerade}}} \left( f(p,q)+ \begin{cases} f(p,q)-1, & p+q<2(a+b),\\ 0, & p+q\ge 2(a+b). \end{cases} \right). $$
Genau diese Formel werten die Implementierungen aus.
Für die eigentliche Aufgabe gilt
$$ a=2^k3^k,\qquad b=2^k5^k, $$
also
$$ 4ab=2^{2k+2}3^k5^k. $$
Damit hat jeder Teiler \(q\) von \(4ab\) die Form
$$ q=2^{e_2}3^{e_3}5^{e_5}, \qquad 0\le e_2\le 2k+2, \qquad 0\le e_3,e_5\le k. $$
Genau deshalb kann die Implementierung alle Kandidaten mit drei geschachtelten Schleifen über Exponenten erzeugen, danach \(p=(4ab)/q\) bilden und die Filter \(q\le p\) sowie gerade Summe \(p+q\) anwenden.
Für \(k=1\) gilt
$$ a=6,\qquad b=10,\qquad 4ab=240. $$
Die gültigen Teilerpaare mit \(q\le p\) und geradem \(p+q\) sind
$$ (p,q)\in\{(120,2),(60,4),(40,6),(30,8),(24,10),(20,12)\}. $$
Nun berechnen wir die Quotientensummen des euklidischen Algorithmus:
$$ \begin{aligned} q=2&:& E(12,2)=6,\quad E(20,2)=10,\quad f=6,\\ q=4&:& E(12,4)=3,\quad E(20,4)=5,\quad f=3,\\ q=6&:& E(12,6)=2,\quad E(20,6)=6,\quad f=2,\\ q=8&:& E(12,8)=3,\quad E(20,8)=4,\quad f=3,\\ q=10&:& E(12,10)=6,\quad E(20,10)=2,\quad f=2,\\ q=12&:& E(12,12)=1,\quad E(20,12)=4,\quad f=1. \end{aligned} $$
Hier ist \(2(a+b)=32\), und für alle gültigen Paare gilt \(p+q\ge 32\). Der kleinere Zweig liefert also kein positives \(c\). Deshalb
$$ F(6,10)=6+3+2+3+2+1=17, $$
genau der Kontrollwert aus der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen demselben Rechenplan. Zuerst werden die benötigten Potenzen von \(2\), \(3\) und \(5\) vorbereitet, damit für jedes \(1\le k\le 18\) die Werte \(a\), \(b\) und \(4ab\) sofort verfügbar sind. Danach werden alle Teiler \(q\) von \(4ab\) über die Exponentenbereiche erzeugt, \(p=(4ab)/q\) berechnet und alle Fälle mit \(q>p\) oder ungeradem \(p+q\) verworfen.
Für jedes verbleibende Teilerpaar werden zwei euklidische Quotientensummen ausgewertet, nämlich für \((2a,q)\) und \((2b,q)\). Der kleinere dieser beiden Werte liefert den Beitrag des größeren Zweigs; falls zusätzlich \(p+q<2(a+b)\) gilt, kommt der Beitrag des kleineren Zweigs mit genau einem Zug weniger hinzu. Die C++-Version parallelisiert unabhängige \(k\)-Werte, während die Python- und Java-Versionen dieselbe Arithmetik sequentiell ausführen.
Kleine interne Prüfungen bestätigen die Formel sowohl für winzige Fälle als auch für die Kontrollwerte
$$ F(6,10)=17,\qquad F(36,100)=179. $$
Für festes \(k\) umfasst die rohe Teilerenumeration
$$ (2k+3)(k+1)^2 $$
Exponenten-Triple \((e_2,e_3,e_5)\). Jede zulässige Wahl führt zu zwei euklidischen Algorithmen, und jede dieser Rechnungen benötigt \(O(\log(4ab))\) Divisionsschritte. Damit ist der arithmetische Aufwand für ein festes \(k\)
$$ O\bigl((2k+3)(k+1)^2\log(4ab)\bigr). $$
Verallgemeinert man die obere Grenze von \(18\) auf \(K\), dann ist die Gesamtzahl der Kandidaten
$$ \sum_{k=1}^{K}(2k+3)(k+1)^2=O(K^4). $$
Der Speicherverbrauch ist bis auf kleine Potenztabellen und Schleifenvariablen \(O(1)\).
\((a,b,c)\) üçlüsünden başlayarak tek hamlede yalnızca bir koordinat şu biçimde yansıtılır:
$$ (a,b,c)\to (2(b+c)-a,b,c),\quad (a,b,c)\to (a,2(c+a)-b,c),\quad (a,b,c)\to (a,b,2(a+b)-c). $$
Sabit pozitif \(a\) ve \(b\) için, yalnızca
$$ (a+b-c)^2-4ab $$
ifadesi tam kare olan pozitif \(c\) değerleri dikkate alınır. En az bir koordinatı \(0\) yapmaya gereken minimum hamle sayısını \(T(a,b,c)\) ile gösterirsek,
$$ F(a,b)=\sum T(a,b,c) $$
olur; toplam bu özelliği sağlayan tüm pozitif \(c\) değerleri üzerindedir. İstenen nihai toplam ise
$$ \sum_{k=1}^{18} F(2^k3^k,2^k5^k). $$
Küçük örneklerde doğrudan durum araması yapılabilir, fakat gerçek problem için çözüm bölen çifti parametrelemesine ve Öklid algoritması üzerinden adım saymaya dayanır.
\(a\) ve \(b\) sabitken önce uygun üçüncü koordinatları \(c\) bulmamız, sonra da her biri için sıfıra uzaklığı hesaplamamız gerekir.
Şunu tanımlayalım:
$$ u=\lvert a+b-c\rvert. $$
İmplementasyonların kullandığı uygunluk koşulu,
$$ (a+b-c)^2-4ab=s^2 $$
eşitliğinin bir tam sayı \(s\) için sağlanmasıdır. \(u=\lvert a+b-c\rvert\) yazınca bu
$$ u^2-s^2=4ab $$
haline gelir. Yani uygun her durum, \(4ab\)'nin iki karenin farkı olarak yazılmasına karşılık gelir.
Şimdi
$$ (u-s)(u+s)=4ab $$
yazalım ve
$$ q=u-s,\qquad p=u+s $$
tanımlarını yapalım. Böylece \(pq=4ab\), \(p\ge q>0\) ve \(p+q=2u\) çift olur. Tersine,
$$ pq=4ab,\qquad p\ge q,\qquad p+q\text{ çift} $$
şartlarını sağlayan her bölen çifti
$$ u=\frac{p+q}{2},\qquad s=\frac{p-q}{2} $$
değerlerini geri verir. Böylece \(c\) araması sonlu sayıda bölen çifti aramasına indirgenir.
\(u=\lvert a+b-c\rvert\) olduğundan iki aday şunlardır:
$$ c_-=a+b+u,\qquad c_+=a+b-u. $$
Büyük dal \(c_-\) her zaman pozitiftir. Küçük dal \(c_+\) ise ancak
$$ a+b-u>0 \iff \frac{p+q}{2}<a+b \iff p+q<2(a+b) $$
olduğunda geçerlidir. Eşitlik halinde \(c_+=0\) olur ve toplamın dışında kalır.
\(x\ge y>0\) için sıradan Öklid algoritmasını
$$ x=q_0y+r_0,\qquad y=q_1r_0+r_1,\qquad \dots,\qquad r_{m-2}=q_m r_{m-1} $$
şeklinde yazalım. Bölüm toplamını
$$ E(x,y)=q_0+q_1+\cdots+q_m $$
olarak tanımlayalım. Bu değer, Öklid algoritmasının bölmeli biçiminde sıkıştırılmış çıkarma adımlarının toplam sayısıdır. Bir \((p,q)\) bölen çifti için yansıma sistemi iki olası indirgeme zincirine ayrılır: biri \(a\)'yı, diğeri \(b\)'yi yok etmeye gider. Bu zincirlerin uzunlukları
$$ E(2a,q)\qquad\text{ve}\qquad E(2b,q) $$
olur. Dolayısıyla büyük dalın en iyi uzaklığı
$$ f(p,q)=\min\bigl(E(2a,q),E(2b,q)\bigr) $$
şeklindedir. Ayrıca iki dal aynı zincir üzerinde art arda gelir, çünkü üçüncü koordinatı yansıtmak
$$ 2(a+b)-c_-=2(a+b)-(a+b+u)=a+b-u=c_+ $$
verir. Bu yüzden \(c_-\) dalı \(f(p,q)\), pozitif olduğu durumda \(c_+\) dalı ise bir adım daha yakın olduğu için \(f(p,q)-1\) katkısı yapar.
Tüm bölen çiftleri toplanınca
$$ F(a,b)= \sum_{\substack{pq=4ab\\ q\le p\\ p+q\text{ çift}}} \left( f(p,q)+ \begin{cases} f(p,q)-1, & p+q<2(a+b),\\ 0, & p+q\ge 2(a+b). \end{cases} \right) $$
elde edilir. İmplementasyonların hesapladığı ifade tam olarak budur.
Asıl problemde
$$ a=2^k3^k,\qquad b=2^k5^k $$
olduğundan
$$ 4ab=2^{2k+2}3^k5^k $$
olur. Bu nedenle \(4ab\)'nin her böleni
$$ q=2^{e_2}3^{e_3}5^{e_5}, \qquad 0\le e_2\le 2k+2, \qquad 0\le e_3,e_5\le k $$
şeklindedir. Kodun üç iç içe üstel döngü kullanmasının nedeni budur; ardından \(p=(4ab)/q\) hesaplanır ve \(q\le p\) ile çiftlik koşulu uygulanır.
\(k=1\) için
$$ a=6,\qquad b=10,\qquad 4ab=240. $$
\(q\le p\) ve \(p+q\) çift koşullarını sağlayan bölen çiftleri
$$ (p,q)\in\{(120,2),(60,4),(40,6),(30,8),(24,10),(20,12)\} $$
olur. Şimdi Öklid bölüm toplamlarını hesaplayalım:
$$ \begin{aligned} q=2&:& E(12,2)=6,\quad E(20,2)=10,\quad f=6,\\ q=4&:& E(12,4)=3,\quad E(20,4)=5,\quad f=3,\\ q=6&:& E(12,6)=2,\quad E(20,6)=6,\quad f=2,\\ q=8&:& E(12,8)=3,\quad E(20,8)=4,\quad f=3,\\ q=10&:& E(12,10)=6,\quad E(20,10)=2,\quad f=2,\\ q=12&:& E(12,12)=1,\quad E(20,12)=4,\quad f=1. \end{aligned} $$
Burada \(2(a+b)=32\) ve tüm geçerli çiftler için \(p+q\ge 32\) olduğundan küçük dal pozitif bir \(c\) üretmez. O halde
$$ F(6,10)=6+3+2+3+2+1=17, $$
ki bu da implementasyondaki örnek kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları aynı aritmetik planı izler. Önce \(2\), \(3\) ve \(5\) kuvvetleri önceden hazırlanır; böylece her \(1\le k\le 18\) için \(a\), \(b\) ve \(4ab\) hızlıca kurulur. Sonra üstel aralıklar üzerinden tüm \(q\) bölenleri üretilir, \(p=(4ab)/q\) bulunur ve \(q>p\) veya \(p+q\) tek olan durumlar elenir.
Kalan her bölen çifti için \((2a,q)\) ve \((2b,q)\) üzerinde iki Öklid bölüm toplamı hesaplanır. Bunların küçüğü büyük dalın katkısını verir; eğer ayrıca \(p+q<2(a+b)\) ise küçük dal için bir eksik katkı daha eklenir. C++ implementasyonu bağımsız \(k\) değerlerini paralel çalıştırır; Python ve Java implementasyonları aynı hesabı sıralı biçimde yapar.
Küçük iç kontroller, türetilen formülü hem minik örneklerde hem de şu kontrol noktalarında doğrular:
$$ F(6,10)=17,\qquad F(36,100)=179. $$
Sabit bir \(k\) için ham bölen taraması
$$ (2k+3)(k+1)^2 $$
adet \((e_2,e_3,e_5)\) üçlüsü üretir. Geçerli her aday için iki Öklid algoritması çalıştırılır ve her biri \(O(\log(4ab))\) bölme adımı gerektirir. Bu nedenle bir \(k\) için aritmetik maliyet
$$ O\bigl((2k+3)(k+1)^2\log(4ab)\bigr) $$
olur. Üst sınır \(18\) yerine genel olarak \(K\) alınırsa toplam aday sayısı
$$ \sum_{k=1}^{K}(2k+3)(k+1)^2=O(K^4) $$
mertebesindedir. Küçük kuvvet tabloları ve döngü değişkenleri dışında bellek kullanımı \(O(1)\)'dir.
Partimos de una terna \((a,b,c)\) y en un movimiento se refleja exactamente una coordenada:
$$ (a,b,c)\to (2(b+c)-a,b,c),\quad (a,b,c)\to (a,2(c+a)-b,c),\quad (a,b,c)\to (a,b,2(a+b)-c). $$
Para valores positivos fijos \(a\) y \(b\), los únicos \(c>0\) relevantes son aquellos para los que
$$ (a+b-c)^2-4ab $$
es un cuadrado perfecto. Si \(T(a,b,c)\) es el número mínimo de movimientos necesario para hacer que alguna coordenada valga \(0\), definimos
$$ F(a,b)=\sum T(a,b,c), $$
donde la suma recorre todos esos valores positivos de \(c\). El problema pide finalmente
$$ \sum_{k=1}^{18} F(2^k3^k,2^k5^k). $$
Una búsqueda directa en el grafo solo sirve para comprobaciones diminutas. La solución real sustituye esa búsqueda por una parametrización con pares de divisores y un conteo de pasos mediante el algoritmo de Euclides.
Fijemos \(a\) y \(b\). Hay que describir primero todos los terceros valores admisibles \(c\) y después calcular la distancia mínima a una coordenada nula para cada uno.
Definimos
$$ u=\lvert a+b-c\rvert. $$
La condición de admisibilidad usada por las implementaciones es
$$ (a+b-c)^2-4ab=s^2 $$
para algún entero \(s\). Con \(u=\lvert a+b-c\rvert\), esto se convierte en
$$ u^2-s^2=4ab. $$
Así, cada estado admisible queda codificado por una representación de \(4ab\) como diferencia de dos cuadrados.
Escribimos
$$ (u-s)(u+s)=4ab. $$
Definimos entonces
$$ q=u-s,\qquad p=u+s. $$
Se obtiene \(pq=4ab\), \(p\ge q>0\), y además \(p+q=2u\) es par. A la inversa, cualquier par de divisores
$$ pq=4ab,\qquad p\ge q,\qquad p+q\text{ par} $$
recupera
$$ u=\frac{p+q}{2},\qquad s=\frac{p-q}{2}. $$
Con ello, la búsqueda original sobre \(c\) se transforma en una búsqueda finita sobre pares de divisores de \(4ab\).
Como \(u=\lvert a+b-c\rvert\), los dos candidatos son
$$ c_-=a+b+u,\qquad c_+=a+b-u. $$
La rama grande \(c_-\) siempre es positiva. La rama pequeña \(c_+\) solo es válida cuando
$$ a+b-u>0 \iff \frac{p+q}{2}<a+b \iff p+q<2(a+b). $$
Si hay igualdad, entonces \(c_+=0\) y no entra en la suma.
Para enteros positivos \(x\ge y\), ejecutamos el algoritmo de Euclides
$$ x=q_0y+r_0,\qquad y=q_1r_0+r_1,\qquad \dots,\qquad r_{m-2}=q_m r_{m-1}. $$
Definimos la suma de cocientes
$$ E(x,y)=q_0+q_1+\cdots+q_m. $$
Esa cantidad coincide con el número de restas comprimidas por la versión con divisiones del algoritmo de Euclides. Para un par \((p,q)\), el sistema de reflexiones se reduce a dos cadenas posibles: una que elimina \(a\) y otra que elimina \(b\). Sus longitudes son
$$ E(2a,q)\qquad\text{y}\qquad E(2b,q), $$
de modo que la distancia óptima de la rama grande es
$$ f(p,q)=\min\bigl(E(2a,q),E(2b,q)\bigr). $$
Las dos ramas están una detrás de la otra en la misma cadena, porque reflejar la tercera coordenada envía
$$ 2(a+b)-c_-=2(a+b)-(a+b+u)=a+b-u=c_+. $$
Por eso \(c_-\) aporta \(f(p,q)\), mientras que \(c_+\), cuando es positiva, aporta exactamente un movimiento menos: \(f(p,q)-1\).
Al sumar sobre todos los pares de divisores se obtiene
$$ F(a,b)= \sum_{\substack{pq=4ab\\ q\le p\\ p+q\text{ par}}} \left( f(p,q)+ \begin{cases} f(p,q)-1, & p+q<2(a+b),\\ 0, & p+q\ge 2(a+b). \end{cases} \right). $$
Esa es exactamente la expresión que evalúan las implementaciones.
En la entrada real,
$$ a=2^k3^k,\qquad b=2^k5^k, $$
luego
$$ 4ab=2^{2k+2}3^k5^k. $$
Por tanto, cualquier divisor \(q\) de \(4ab\) tiene la forma
$$ q=2^{e_2}3^{e_3}5^{e_5}, \qquad 0\le e_2\le 2k+2, \qquad 0\le e_3,e_5\le k. $$
De ahí salen los tres bucles anidados sobre exponentes: generan todos los candidatos \(q\), reconstruyen \(p=(4ab)/q\) y aplican los filtros \(q\le p\) y paridad de \(p+q\).
Tomemos \(k=1\). Entonces
$$ a=6,\qquad b=10,\qquad 4ab=240. $$
Los pares válidos con \(q\le p\) y \(p+q\) par son
$$ (p,q)\in\{(120,2),(60,4),(40,6),(30,8),(24,10),(20,12)\}. $$
Calculamos ahora las sumas de cocientes:
$$ \begin{aligned} q=2&:& E(12,2)=6,\quad E(20,2)=10,\quad f=6,\\ q=4&:& E(12,4)=3,\quad E(20,4)=5,\quad f=3,\\ q=6&:& E(12,6)=2,\quad E(20,6)=6,\quad f=2,\\ q=8&:& E(12,8)=3,\quad E(20,8)=4,\quad f=3,\\ q=10&:& E(12,10)=6,\quad E(20,10)=2,\quad f=2,\\ q=12&:& E(12,12)=1,\quad E(20,12)=4,\quad f=1. \end{aligned} $$
Aquí \(2(a+b)=32\), y todos los pares válidos cumplen \(p+q\ge 32\). Por eso la rama pequeña no produce ningún \(c\) positivo adicional. En consecuencia,
$$ F(6,10)=6+3+2+3+2+1=17, $$
que coincide con la verificación de la implementación.
Las implementaciones en C++, Python y Java siguen el mismo plan aritmético. Primero precomputan las potencias de \(2\), \(3\) y \(5\) necesarias para construir rápidamente \(a\), \(b\) y \(4ab\) para todo \(1\le k\le 18\). Después enumeran todos los divisores \(q\) de \(4ab\) mediante los rangos de exponentes, calculan \(p=(4ab)/q\) y descartan los casos con \(q>p\) o \(p+q\) impar.
Para cada par superviviente evalúan dos sumas de cocientes euclidianos, una sobre \((2a,q)\) y otra sobre \((2b,q)\), toman la menor y añaden la contribución de la rama grande; si además \(p+q<2(a+b)\), también añaden la contribución de la rama pequeña con un movimiento menos. La versión en C++ paraleliza los distintos valores de \(k\), mientras que las versiones en Python y Java hacen la misma cuenta de manera secuencial.
Pequeñas comprobaciones internas confirman la fórmula en casos diminutos y en los puntos de control
$$ F(6,10)=17,\qquad F(36,100)=179. $$
Para un \(k\) fijo, la enumeración bruta de divisores recorre
$$ (2k+3)(k+1)^2 $$
tripletas \((e_2,e_3,e_5)\). Cada candidato válido requiere dos algoritmos de Euclides, y cada uno de ellos tarda \(O(\log(4ab))\) pasos de división. Por tanto, el coste aritmético para un solo \(k\) es
$$ O\bigl((2k+3)(k+1)^2\log(4ab)\bigr). $$
Si se generaliza el límite superior de \(18\) a \(K\), el número total de candidatos es
$$ \sum_{k=1}^{K}(2k+3)(k+1)^2=O(K^4). $$
El uso de memoria es \(O(1)\) aparte de las pequeñas tablas de potencias y las variables de bucle.
从三元组 \((a,b,c)\) 出发，一次操作可以只反射其中一个坐标：
$$ (a,b,c)\to (2(b+c)-a,b,c),\quad (a,b,c)\to (a,2(c+a)-b,c),\quad (a,b,c)\to (a,b,2(a+b)-c). $$
对固定的正整数 \(a,b\)，只有那些满足
$$ (a+b-c)^2-4ab $$
是完全平方数的正整数 \(c\) 才会进入求和。若 \(T(a,b,c)\) 表示把至少一个坐标变成 \(0\) 所需的最少步数，那么
$$ F(a,b)=\sum T(a,b,c), $$
其中求和遍历所有满足该条件的正整数 \(c\)。题目最终要求的是
$$ \sum_{k=1}^{18} F(2^k3^k,2^k5^k). $$
如果直接在状态图上做广度优先搜索，只能处理非常小的测试。真正可行的做法是：先把第三个坐标转化为 \(4ab\) 的因子对问题，再把最短步数转化为欧几里得算法的商之和。
下面固定 \(a,b\)。核心任务分成两步：先刻画所有合法的第三坐标 \(c\)，再对每个合法 \(c\) 计算到某个坐标变成 \(0\) 的最短距离。
定义
$$ u=\lvert a+b-c\rvert. $$
实现所使用的等价条件是存在整数 \(s\)，使得
$$ (a+b-c)^2-4ab=s^2. $$
由于 \(u=\lvert a+b-c\rvert\)，这就等价于
$$ u^2-s^2=4ab. $$
因此，合法状态本质上对应于把 \(4ab\) 表示成两个平方的差。
把上式写成
$$ (u-s)(u+s)=4ab. $$
令
$$ q=u-s,\qquad p=u+s. $$
于是有 \(pq=4ab\)、\(p\ge q>0\)，而且 \(p+q=2u\) 必为偶数。反过来，只要一个因子对满足
$$ pq=4ab,\qquad p\ge q,\qquad p+q\text{ 为偶数}, $$
就能恢复出
$$ u=\frac{p+q}{2},\qquad s=\frac{p-q}{2}. $$
这一步非常关键，因为原来需要在许多 \(c\) 上做搜索，现在只需要枚举 \(4ab\) 的有限个因子对即可。
由 \(u=\lvert a+b-c\rvert\) 可知，对应的第三坐标只能是
$$ c_-=a+b+u,\qquad c_+=a+b-u. $$
较大的分支 \(c_-\) 总是正数。较小的分支 \(c_+\) 只有在
$$ a+b-u>0 \iff \frac{p+q}{2}<a+b \iff p+q<2(a+b) $$
时才是正数并参与求和。若 \(p+q=2(a+b)\)，那么 \(c_+=0\)，题目要求的是正整数 \(c\)，因此这一支不计入。
对正整数 \(x\ge y\)，考虑通常的欧几里得算法
$$ x=q_0y+r_0,\qquad y=q_1r_0+r_1,\qquad \dots,\qquad r_{m-2}=q_m r_{m-1}. $$
定义商之和
$$ E(x,y)=q_0+q_1+\cdots+q_m. $$
它正好等于“减法版欧几里得算法”中的总减法次数，只不过被除法形式压缩在一起了。对某个固定的因子对 \((p,q)\)，反射过程会退化成两条可能的约化链：一条对应最终消去 \(a\)，另一条对应最终消去 \(b\)。这两条链的长度分别是
$$ E(2a,q)\qquad\text{和}\qquad E(2b,q). $$
所以，大分支 \(c_-\) 的最优距离就是
$$ f(p,q)=\min\bigl(E(2a,q),E(2b,q)\bigr). $$
为什么小分支少一步？因为对第三坐标做一次反射就会把
$$ c_-=a+b+u $$
直接送到
$$ 2(a+b)-c_-=a+b-u=c_+. $$
也就是说，\(c_+\) 在同一条反射链上正好比 \(c_-\) 更靠近终点一步。因此 \(c_-\) 贡献 \(f(p,q)\)，而当 \(c_+>0\) 时，它贡献 \(f(p,q)-1\)。
把所有因子对的贡献加起来，得到
$$ F(a,b)= \sum_{\substack{pq=4ab\\ q\le p\\ p+q\text{ 为偶数}}} \left( f(p,q)+ \begin{cases} f(p,q)-1, & p+q<2(a+b),\\ 0, & p+q\ge 2(a+b). \end{cases} \right). $$
这就是实现实际计算的公式。
题目里
$$ a=2^k3^k,\qquad b=2^k5^k, $$
因此
$$ 4ab=2^{2k+2}3^k5^k. $$
于是 \(4ab\) 的每个因子 \(q\) 都可唯一写成
$$ q=2^{e_2}3^{e_3}5^{e_5}, \qquad 0\le e_2\le 2k+2, \qquad 0\le e_3,e_5\le k. $$
这正是实现中三重循环的来源：枚举所有指数三元组，构造出 \(q\)，再由 \(p=(4ab)/q\) 还原另一个因子，然后检查 \(q\le p\) 和 \(p+q\) 为偶数这两个条件。
取 \(k=1\)，则
$$ a=6,\qquad b=10,\qquad 4ab=240. $$
满足 \(q\le p\) 且 \(p+q\) 为偶数的因子对为
$$ (p,q)\in\{(120,2),(60,4),(40,6),(30,8),(24,10),(20,12)\}. $$
接着计算商之和：
$$ \begin{aligned} q=2&:& E(12,2)=6,\quad E(20,2)=10,\quad f=6,\\ q=4&:& E(12,4)=3,\quad E(20,4)=5,\quad f=3,\\ q=6&:& E(12,6)=2,\quad E(20,6)=6,\quad f=2,\\ q=8&:& E(12,8)=3,\quad E(20,8)=4,\quad f=3,\\ q=10&:& E(12,10)=6,\quad E(20,10)=2,\quad f=2,\\ q=12&:& E(12,12)=1,\quad E(20,12)=4,\quad f=1. \end{aligned} $$
这里 \(2(a+b)=32\)，而所有有效因子对都满足 \(p+q\ge 32\)，因此小分支没有额外的正整数 \(c\) 可以加入。于是
$$ F(6,10)=6+3+2+3+2+1=17, $$
与实现里的校验值完全一致。
C++、Python 和 Java 实现都遵循同一套算术流程。首先预计算所需的 \(2\)、\(3\)、\(5\) 的幂，这样对每个 \(1\le k\le 18\) 都能快速构造出 \(a\)、\(b\) 和 \(4ab\)。随后根据上面的指数范围枚举所有 \(q\)，再计算 \(p=(4ab)/q\)，并剔除 \(q>p\) 或 \(p+q\) 为奇数的情况。
对于每个保留下来的因子对，实现都会分别计算 \((2a,q)\) 与 \((2b,q)\) 的欧几里得商之和，取二者较小值作为大分支的贡献；如果 \(p+q<2(a+b)\)，就再把小分支的贡献 \(f-1\) 加进去。C++ 版本把不同的 \(k\) 并行处理；Python 和 Java 版本则顺序执行完全相同的数值公式。
实现内部还用小规模案例和两个检查点验证公式：
$$ F(6,10)=17,\qquad F(36,100)=179. $$
固定 \(k\) 时，原始的因子枚举一共会遍历
$$ (2k+3)(k+1)^2 $$
个指数三元组 \((e_2,e_3,e_5)\)。每个有效候选都要做两次欧几里得算法，而每次欧几里得算法需要 \(O(\log(4ab))\) 次除法步骤。因此，单个 \(k\) 的算术复杂度为
$$ O\bigl((2k+3)(k+1)^2\log(4ab)\bigr). $$
如果把上界从 \(18\) 推广到一般的 \(K\)，那么总候选数是
$$ \sum_{k=1}^{K}(2k+3)(k+1)^2=O(K^4). $$
除了少量幂表和循环变量之外，额外空间可以看作 \(O(1)\)。
Начинаем с тройки \((a,b,c)\). За один ход можно отразить ровно одну координату:
$$ (a,b,c)\to (2(b+c)-a,b,c),\quad (a,b,c)\to (a,2(c+a)-b,c),\quad (a,b,c)\to (a,b,2(a+b)-c). $$
При фиксированных положительных \(a\) и \(b\) в суммирование входят только те положительные значения \(c\), для которых
$$ (a+b-c)^2-4ab $$
является полным квадратом. Если \(T(a,b,c)\) обозначает минимальное число ходов до состояния, где хотя бы одна координата равна \(0\), то
$$ F(a,b)=\sum T(a,b,c), $$
где сумма берется по всем таким положительным \(c\). Итоговая величина задачи равна
$$ \sum_{k=1}^{18} F(2^k3^k,2^k5^k). $$
Прямой поиск по графу состояний годится только для очень маленьких проверок. Полное решение заменяет этот поиск параметризацией через пары делителей и подсчетом шагов через алгоритм Евклида.
Зафиксируем \(a\) и \(b\). Сначала нужно описать все допустимые третьи координаты \(c\), а затем вычислить минимальную дистанцию до нулевой координаты для каждой из них.
Положим
$$ u=\lvert a+b-c\rvert. $$
Эквивалентное условие допустимости, используемое в реализации, имеет вид
$$ (a+b-c)^2-4ab=s^2 $$
для некоторого целого \(s\). Тогда из \(u=\lvert a+b-c\rvert\) получаем
$$ u^2-s^2=4ab. $$
Значит, каждое допустимое состояние соответствует представлению числа \(4ab\) как разности двух квадратов.
Запишем
$$ (u-s)(u+s)=4ab. $$
Введем
$$ q=u-s,\qquad p=u+s. $$
Тогда \(pq=4ab\), \(p\ge q>0\), а сумма \(p+q=2u\) четна. Обратно, каждая пара делителей
$$ pq=4ab,\qquad p\ge q,\qquad p+q\text{ четно} $$
восстанавливает
$$ u=\frac{p+q}{2},\qquad s=\frac{p-q}{2}. $$
Тем самым исходный перебор по \(c\) сводится к конечному перебору пар делителей числа \(4ab\).
Так как \(u=\lvert a+b-c\rvert\), возможны два кандидата:
$$ c_-=a+b+u,\qquad c_+=a+b-u. $$
Большая ветвь \(c_-\) всегда положительна. Малая ветвь \(c_+\) допустима только при
$$ a+b-u>0 \iff \frac{p+q}{2}<a+b \iff p+q<2(a+b). $$
Если же \(p+q=2(a+b)\), то \(c_+=0\), а такие значения в сумму не входят.
Для положительных целых \(x\ge y\) рассмотрим обычный алгоритм Евклида
$$ x=q_0y+r_0,\qquad y=q_1r_0+r_1,\qquad \dots,\qquad r_{m-2}=q_m r_{m-1}. $$
Определим сумму частных
$$ E(x,y)=q_0+q_1+\cdots+q_m. $$
Это в точности число шагов вычитания, которые сжимаются в делительной форме алгоритма Евклида. Для фиксированной пары \((p,q)\) система отражений распадается на две возможные цепочки редукции: одна ведет к занулению \(a\), другая к занулению \(b\). Их длины равны
$$ E(2a,q)\qquad\text{и}\qquad E(2b,q), $$
поэтому оптимальная длина для большой ветви равна
$$ f(p,q)=\min\bigl(E(2a,q),E(2b,q)\bigr). $$
Почему малая ветвь на один ход ближе? Потому что отражение третьей координаты переводит
$$ c_-=a+b+u $$
в
$$ 2(a+b)-c_-=a+b-u=c_+. $$
Значит, \(c_+\) лежит на той же цепочке ровно на один шаг ближе к нулевому состоянию. Поэтому вклад \(c_-\) равен \(f(p,q)\), а вклад \(c_+\), если он положителен, равен \(f(p,q)-1\).
Суммируя по всем парам делителей, получаем
$$ F(a,b)= \sum_{\substack{pq=4ab\\ q\le p\\ p+q\text{ четно}}} \left( f(p,q)+ \begin{cases} f(p,q)-1, & p+q<2(a+b),\\ 0, & p+q\ge 2(a+b). \end{cases} \right). $$
Именно эту формулу и вычисляют реализации.
В задаче
$$ a=2^k3^k,\qquad b=2^k5^k, $$
поэтому
$$ 4ab=2^{2k+2}3^k5^k. $$
Следовательно, любой делитель \(q\) числа \(4ab\) записывается как
$$ q=2^{e_2}3^{e_3}5^{e_5}, \qquad 0\le e_2\le 2k+2, \qquad 0\le e_3,e_5\le k. $$
Этим и объясняются три вложенных цикла по показателям степеней: они порождают все варианты \(q\), после чего восстанавливается \(p=(4ab)/q\) и проверяются условия \(q\le p\) и четности \(p+q\).
Пусть \(k=1\). Тогда
$$ a=6,\qquad b=10,\qquad 4ab=240. $$
Подходящие пары делителей с \(q\le p\) и четным \(p+q\) таковы:
$$ (p,q)\in\{(120,2),(60,4),(40,6),(30,8),(24,10),(20,12)\}. $$
Вычислим суммы частных:
$$ \begin{aligned} q=2&:& E(12,2)=6,\quad E(20,2)=10,\quad f=6,\\ q=4&:& E(12,4)=3,\quad E(20,4)=5,\quad f=3,\\ q=6&:& E(12,6)=2,\quad E(20,6)=6,\quad f=2,\\ q=8&:& E(12,8)=3,\quad E(20,8)=4,\quad f=3,\\ q=10&:& E(12,10)=6,\quad E(20,10)=2,\quad f=2,\\ q=12&:& E(12,12)=1,\quad E(20,12)=4,\quad f=1. \end{aligned} $$
Здесь \(2(a+b)=32\), и для всех допустимых пар выполняется \(p+q\ge 32\). Значит, малая ветвь не дает дополнительного положительного \(c\). Поэтому
$$ F(6,10)=6+3+2+3+2+1=17, $$
что совпадает с контрольным значением реализации.
Реализации на C++, Python и Java следуют одному и тому же арифметическому плану. Сначала они заранее строят степени \(2\), \(3\) и \(5\), чтобы для каждого \(1\le k\le 18\) быстро получить \(a\), \(b\) и \(4ab\). Затем по диапазонам показателей перечисляются все делители \(q\), вычисляется \(p=(4ab)/q\), и отбрасываются случаи \(q>p\) либо нечетного \(p+q\).
Для каждой оставшейся пары вычисляются две суммы частных алгоритма Евклида, для \((2a,q)\) и \((2b,q)\), берется минимум и добавляется вклад большой ветви; если дополнительно выполнено \(p+q<2(a+b)\), то добавляется и вклад малой ветви с уменьшением на один ход. Версия на C++ распараллеливает независимые значения \(k\), а версии на Python и Java выполняют те же вычисления последовательно.
Небольшие внутренние проверки подтверждают формулу как на совсем маленьких случаях, так и на контрольных значениях
$$ F(6,10)=17,\qquad F(36,100)=179. $$
Для фиксированного \(k\) грубый перебор делителей проходит по
$$ (2k+3)(k+1)^2 $$
тройкам показателей \((e_2,e_3,e_5)\). Каждый допустимый кандидат требует двух запусков алгоритма Евклида, а каждый такой запуск занимает \(O(\log(4ab))\) шагов деления. Следовательно, арифметическая сложность для одного \(k\) равна
$$ O\bigl((2k+3)(k+1)^2\log(4ab)\bigr). $$
Если заменить верхнюю границу \(18\) на общий параметр \(K\), суммарное число кандидатов составит
$$ \sum_{k=1}^{K}(2k+3)(k+1)^2=O(K^4). $$
Память, помимо небольших таблиц степеней и счетчиков циклов, остается \(O(1)\).
ننطلق من ثلاثية \((a,b,c)\)، وفي كل خطوة يُسمح بعكس إحداثي واحد فقط:
$$ (a,b,c)\to (2(b+c)-a,b,c),\quad (a,b,c)\to (a,2(c+a)-b,c),\quad (a,b,c)\to (a,b,2(a+b)-c). $$
عند تثبيت عددين موجبين \(a\) و\(b\)، فإن قيم \(c>0\) التي تدخل في الحساب هي بالضبط القيم التي تجعل
$$ (a+b-c)^2-4ab $$
مربعًا كاملًا. وإذا رمزنا إلى أقل عدد من الحركات اللازمة لجعل أحد الإحداثيات مساويًا للصفر بـ \(T(a,b,c)\)، فإننا نعرّف
$$ F(a,b)=\sum T(a,b,c), $$
حيث يمتد الجمع على جميع قيم \(c\) الموجبة التي تحقق هذا الشرط. والمطلوب في النهاية هو
$$ \sum_{k=1}^{18} F(2^k3^k,2^k5^k). $$
البحث المباشر في فضاء الحالات لا يصلح إلا لاختبارات صغيرة جدًا. أمّا الحل الفعلي فيحوّل المسألة إلى توصيف عبر أزواج القواسم ثم يحسب عدد الخطوات بواسطة خوارزمية إقليدس.
لنثبّت \(a\) و\(b\). عندها نحتاج أولًا إلى توصيف جميع القيم المسموح بها للإحداثي الثالث \(c\)، ثم نحسب المسافة الدنيا إلى حالة تحتوي على إحداثي صفري لكل واحدة منها.
لنضع
$$ u=\lvert a+b-c\rvert. $$
الشرط المكافئ الذي تعتمد عليه التطبيقات هو وجود عدد صحيح \(s\) بحيث
$$ (a+b-c)^2-4ab=s^2. $$
ومع \(u=\lvert a+b-c\rvert\) يصبح ذلك
$$ u^2-s^2=4ab. $$
إذن كل حالة مقبولة تقابل تمثيلًا للعدد \(4ab\) على أنه فرق بين مربعين.
نكتب
$$ (u-s)(u+s)=4ab. $$
ثم نعرّف
$$ q=u-s,\qquad p=u+s. $$
فنحصل على \(pq=4ab\) و\(p\ge q>0\)، كما أن \(p+q=2u\) عدد زوجي. وبالعكس، فإن كل زوج قواسم يحقق
$$ pq=4ab,\qquad p\ge q,\qquad p+q\text{ even} $$
يعيد لنا
$$ u=\frac{p+q}{2},\qquad s=\frac{p-q}{2}. $$
وبذلك تتحول عملية البحث في جميع قيم \(c\) إلى تعداد منتهٍ لأزواج قواسم العدد \(4ab\).
بما أن \(u=\lvert a+b-c\rvert\)، فإن الإحداثي الثالث الممكن هو أحد الفرعين
$$ c_-=a+b+u,\qquad c_+=a+b-u. $$
الفرع الأكبر \(c_-\) موجب دائمًا. أمّا الفرع الأصغر \(c_+\) فلا يكون مقبولًا إلا إذا تحقق
$$ a+b-u>0 \iff \frac{p+q}{2}<a+b \iff p+q<2(a+b). $$
وفي حالة المساواة نحصل على \(c_+=0\)، وهو مستبعد لأن الجمع يتم على قيم موجبة فقط.
لعددين صحيحين موجبين \(x\ge y\) نطبق خوارزمية إقليدس بالشكل
$$ x=q_0y+r_0,\qquad y=q_1r_0+r_1,\qquad \dots,\qquad r_{m-2}=q_m r_{m-1}. $$
ونعرّف
$$ E(x,y)=q_0+q_1+\cdots+q_m. $$
هذا المقدار يساوي تمامًا عدد خطوات الطرح المتتالية التي تختصرها الصيغة القَسمية لخوارزمية إقليدس. وبالنسبة إلى زوج قواسم \((p,q)\)، فإن نظام الانعكاسات ينهار إلى سلسلتين ممكنتين: واحدة تنتهي بتصفير \(a\)، وأخرى تنتهي بتصفير \(b\). وطول السلسلتين هو
$$ E(2a,q)\qquad\text{and}\qquad E(2b,q). $$
ومن ثم فإن أفضل مسافة للفرع الأكبر هي
$$ f(p,q)=\min\bigl(E(2a,q),E(2b,q)\bigr). $$
ولماذا يساهم الفرع الأصغر بخطوة أقل؟ لأن عكس الإحداثي الثالث يرسل
$$ c_-=a+b+u $$
إلى
$$ 2(a+b)-c_-=a+b-u=c_+. $$
أي أن \(c_+\) يقع على السلسلة نفسها ولكنه أقرب إلى النهاية بخطوة واحدة. لذلك يساهم \(c_-\) بالمقدار \(f(p,q)\)، بينما يساهم \(c_+\) بالمقدار \(f(p,q)-1\) متى كان موجبًا.
عند جمع مساهمات جميع أزواج القواسم نحصل على
$$ F(a,b)= \sum_{\substack{pq=4ab\\ q\le p\\ p+q\text{ even}}} \left( f(p,q)+ \begin{cases} f(p,q)-1, & p+q<2(a+b),\\ 0, & p+q\ge 2(a+b). \end{cases} \right). $$
وهذه هي الصيغة التي تطبقها الشيفرات مباشرة.
في المسألة الأصلية لدينا
$$ a=2^k3^k,\qquad b=2^k5^k, $$
ومن ثم
$$ 4ab=2^{2k+2}3^k5^k. $$
وعليه فإن كل قاسم \(q\) للعدد \(4ab\) يكتب على الصورة
$$ q=2^{e_2}3^{e_3}5^{e_5}, \qquad 0\le e_2\le 2k+2, \qquad 0\le e_3,e_5\le k. $$
وهذا يفسر وجود ثلاث حلقات متداخلة على الأسس في التنفيذ: فهي تولد كل القواسم الممكنة \(q\)، ثم تستخرج \(p=(4ab)/q\)، وبعد ذلك تطبق شرطي \(q\le p\) وكون \(p+q\) زوجيًا.
لنأخذ \(k=1\). عندئذ
$$ a=6,\qquad b=10,\qquad 4ab=240. $$
أزواج القواسم الصالحة التي تحقق \(q\le p\) و\(p+q\) زوجي هي
$$ (p,q)\in\{(120,2),(60,4),(40,6),(30,8),(24,10),(20,12)\}. $$
ثم نحسب مجاميع خارجات القسمة:
$$ \begin{aligned} q=2&:& E(12,2)=6,\quad E(20,2)=10,\quad f=6,\\ q=4&:& E(12,4)=3,\quad E(20,4)=5,\quad f=3,\\ q=6&:& E(12,6)=2,\quad E(20,6)=6,\quad f=2,\\ q=8&:& E(12,8)=3,\quad E(20,8)=4,\quad f=3,\\ q=10&:& E(12,10)=6,\quad E(20,10)=2,\quad f=2,\\ q=12&:& E(12,12)=1,\quad E(20,12)=4,\quad f=1. \end{aligned} $$
هنا لدينا \(2(a+b)=32\)، وجميع الأزواج الصالحة تحقق \(p+q\ge 32\)، لذا فإن الفرع الأصغر لا يضيف أي قيمة موجبة إضافية لـ \(c\). وبالتالي
$$ F(6,10)=6+3+2+3+2+1=17, $$
وهو تمامًا مقدار التحقق المستخدم في التنفيذ.
تتبع تطبيقات C++ وPython وJava الخطة الحسابية نفسها. أولًا تُحسب قوى \(2\) و\(3\) و\(5\) مسبقًا بحيث يمكن بناء \(a\) و\(b\) و\(4ab\) بسرعة لكل \(1\le k\le 18\). ثم تُعدَّد جميع القواسم \(q\) عبر مجالات الأسس السابقة، ويُحسب \(p=(4ab)/q\)، وتُستبعد الحالات التي فيها \(q>p\) أو يكون فيها \(p+q\) فرديًا.
ولكل زوج ناجٍ تُحسب قيمتا \(E(2a,q)\) و\(E(2b,q)\)، ويؤخذ الأصغر منهما بوصفه مساهمة الفرع الأكبر؛ وإذا تحقق كذلك \(p+q<2(a+b)\) تُضاف مساهمة الفرع الأصغر بعد إنقاص خطوة واحدة. تنفيذ C++ يوازي قيم \(k\) المستقلة، أمّا تنفيذا Python وJava فينفذان الحساب نفسه بصورة متسلسلة.
كما تتضمن الشيفرات اختبارات داخلية صغيرة تؤكد الصيغة على حالات بسيطة وعلى نقطتي التحقق
$$ F(6,10)=17,\qquad F(36,100)=179. $$
عند تثبيت \(k\)، فإن التعداد الخام للقواسم يمر عبر
$$ (2k+3)(k+1)^2 $$
ثلاثيات أسية \((e_2,e_3,e_5)\). وكل مرشح صالح يتطلب تشغيل خوارزمية إقليدس مرتين، وكل تشغيل يحتاج \(O(\log(4ab))\) خطوة قسمة. لذلك تكون الكلفة الحسابية لقيمة واحدة من \(k\) هي
$$ O\bigl((2k+3)(k+1)^2\log(4ab)\bigr). $$
وإذا عممنا الحد الأعلى من \(18\) إلى \(K\)، فإن العدد الكلي للمرشحين يساوي
$$ \sum_{k=1}^{K}(2k+3)(k+1)^2=O(K^4). $$
أما الذاكرة فتبقى \(O(1)\) باستثناء جداول صغيرة للقوى ومتغيرات الحلقات.