As implied by the C++, Python, and Java implementations, the billiard problem is solved by unfolding reflections into straight-line motion on an integer lattice. For an input \(N\), the geometry is compressed into the arithmetic parameter
$$n=3N+6,$$
and the answer becomes a weighted count of primitive lattice directions lying inside a thin strip between two rational boundary lines. The direct geometric search is replaced by Möbius inversion, Mertens-prefix summation, and a fast lattice-point counter.
The implementations show that one symmetry sector can be counted through the quantity
$$q(g)=L(18,10;g)-L(18,30;g),$$
where \(L(a,b;c)\) denotes the number of positive integer pairs \((x,y)\) satisfying
$$ax+by\le c.$$
Therefore
$$q(g)=\#\left\{(x,y)\in\mathbb{Z}_{>0}^2:18x+10y\le g<18x+30y\right\}.$$
So \(q(g)\) counts lattice points in a narrow strip: below the line \(18x+10y=g\), but not below the steeper line \(18x+30y=g\). This is the geometric core hidden inside the billiard unfolding.
For fixed \(a,b,c\), the basic lattice count is
$$L(a,b;c)=\sum_{x=1}^{\lfloor c/a\rfloor}\left\lfloor\frac{c-ax}{b}\right\rfloor.$$
Assume \(a\ge b\), and write
$$m=\left\lfloor\frac{c}{a}\right\rfloor,\qquad k=\left\lfloor\frac{a-1}{b}\right\rfloor,\qquad r=a-kb,\qquad h=\left\lfloor\frac{c-am}{b}\right\rfloor.$$
Then the lattice triangle can be decomposed into complete blocks plus a smaller remainder region, giving the recursion
$$L(a,b;c)=L(b,r;c-b(km+h))+k\frac{m(m-1)}{2}+mh.$$
The base cases are immediate: if \(a>c\), there are no positive solutions; if \(a=b\), then
$$L(a,a;c)=\frac{m(m-1)}{2}.$$
This is a Euclidean-algorithm descent on the pair \((a,b)\), so the recursion is very shallow. Because the coefficients \(18,10,30\) are fixed, the strip count is effectively constant-time once the formula is known.
Let
$$M(x)=\sum_{m\le x}\mu(m)$$
be the classical Mertens function, and define the transformed prefix
$$A(x)=\sum_{j\ge 0} M\!\left(\left\lfloor\frac{x}{3^j}\right\rfloor\right).$$
Its discrete difference is
$$A(d)-A(d-1)=\sum_{3^j\mid d}\mu\!\left(\frac{d}{3^j}\right).$$
If \(3\nmid d\), only the term \(j=0\) appears, so the difference is simply \(\mu(d)\). If \(3\mid d\), then the only potentially nonzero terms come in the pair \(\mu(u)+\mu(3u)\), which cancel. Hence
$$A(d)-A(d-1)= \begin{cases} \mu(d), & 3\nmid d,\\ 0, & 3\mid d. \end{cases}$$
This identity explains why the implementations do not sum plain Mertens values: they need the Möbius weight on integers whose common factor is not allowed to contain any prime other than possibly \(3\).
With \(n=3N+6\), the reduced-sector count is
$$z=\sum_{d=1}^{n}\bigl(A(d)-A(d-1)\bigr)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
Using the previous step, this can be written more transparently as
$$z=\sum_{\substack{1\le d\le n\\3\nmid d}}\mu(d)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
This is a standard Möbius-inversion pattern: first count all directions in the strip, then remove those that are non-primitive, except that powers of \(3\) remain allowed by the transformed weight. That special treatment of the prime \(3\) is exactly what the summed Mertens transform encodes.
The value \(\lfloor n/d\rfloor\) is constant on intervals. If an interval \([a,b]\) satisfies
$$\left\lfloor\frac{n}{d}\right\rfloor=g\qquad\text{for all }d\in[a,b],$$
then its total contribution is
$$q(g)\sum_{d=a}^{b}\bigl(A(d)-A(d-1)\bigr)=q(g)\bigl(A(b)-A(a-1)\bigr).$$
This is why the implementations split the sum into quotient blocks. Only about \(2\sqrt{n}\) distinct quotients occur, so the expensive part is reduced to prefix evaluations and one strip count per block.
The implementations finally return
$$F(N)=4z+2.$$
This shows that the arithmetic sum \(z\) counts one reduced symmetry sector first. The factor \(4\) restores the mirrored sectors, while the final \(+2\) accounts for two exceptional symmetric cases that are handled separately in the normalization.
For \(N=10\), we have
$$n=3\cdot 10+6=36.$$
The smallest lattice point in the strip is \((x,y)=(1,1)\), and it enters when
$$18\cdot 1+10\cdot 1=28\le g.$$
Therefore \(q(g)=0\) for all \(g<28\). If \(d\ge 2\), then \(\lfloor 36/d\rfloor\le 18\), so every such term vanishes. Only \(d=1\) survives:
$$q(36)=1,$$
because \((1,1)\) satisfies \(28\le 36<48\). Also \(A(1)-A(0)=\mu(1)=1\). Hence
$$z=1,$$
and the final count is
$$F(10)=4\cdot 1+2=6,$$
which matches the checkpoint built into the implementations.
The C++, Python, and Java implementations all follow the same plan. First they set \(n=3N+6\). Next they memoize the Mertens function \(M(x)\), because the transformed prefix \(A(x)\) repeatedly asks for values of \(M(\lfloor x/3^j\rfloor)\) on overlapping arguments. This turns the Möbius-weight prefix into a cache-friendly arithmetic routine.
For the geometric part, the implementation evaluates \(q(g)\) as the difference of two recursive lattice counters. Each lattice counter repeatedly reduces \((a,b)\) by a Euclidean step, adds the contribution of full triangular blocks, and stops once the remaining region is empty or symmetric. Since the coefficients are fixed, this part is very small compared with the arithmetic prefix work.
The final summation is not performed divisor by divisor. Instead, the implementation walks through the distinct values of \(\lfloor n/d\rfloor\): one loop handles the small divisors directly, and the complementary loop handles the large divisor ranges through interval endpoints. On each block it multiplies a prefix difference of \(A\) by one strip count \(q(g)\). As soon as \(q(g)=0\), the remaining blocks are known to contribute nothing, so the loop can stop early.
The outer summation uses quotient grouping, so only \(O(\sqrt{n})\) blocks are visited instead of all \(n\) divisors. Each strip evaluation uses a Euclidean descent on fixed coefficients, so its cost is effectively constant for this problem. The dominant work is the memoized evaluation of the Mertens prefix on the distinct arguments generated by the quotient blocks and repeated division by \(3\).
So the visible structure is sublinear in \(n\), with memory usage dominated by the Mertens cache. This is far smaller than any direct billiard simulation or naive scan of all candidate lattice directions.
Wie die C++-, Python- und Java-Implementierungen zeigen, wird das Billardproblem durch Entfalten der Reflexionen in geradlinige Bewegung auf einem ganzzahligen Gitter gelöst. Für einen gegebenen Wert \(N\) wird die Geometrie auf den arithmetischen Parameter
$$n=3N+6$$
reduziert. Danach zählt man keine Bahnen mehr direkt, sondern primitive Gitterrichtungen in einem schmalen Streifen zwischen zwei rationalen Geraden. Die eigentliche Arbeit leisten Möbius-Inversion, Mertens-Präfixsummen und ein schneller Gitterpunktzähler.
Die Implementierungen zeigen, dass ein Symmetriesektor durch
$$q(g)=L(18,10;g)-L(18,30;g)$$
beschrieben wird, wobei \(L(a,b;c)\) die Anzahl positiver ganzzahliger Paare \((x,y)\) mit
$$ax+by\le c$$
bezeichnet. Also gilt
$$q(g)=\#\left\{(x,y)\in\mathbb{Z}_{>0}^2:18x+10y\le g<18x+30y\right\}.$$
Damit zählt \(q(g)\) genau die Gitterpunkte in einem schmalen Bereich: unter der Geraden \(18x+10y=g\), aber nicht unter der steileren Geraden \(18x+30y=g\). Genau dieser Streifen ist die arithmetische Spur des entfalteten Billards.
Für feste \(a,b,c\) ist
$$L(a,b;c)=\sum_{x=1}^{\lfloor c/a\rfloor}\left\lfloor\frac{c-ax}{b}\right\rfloor.$$
Nehmen wir \(a\ge b\) an und setzen
$$m=\left\lfloor\frac{c}{a}\right\rfloor,\qquad k=\left\lfloor\frac{a-1}{b}\right\rfloor,\qquad r=a-kb,\qquad h=\left\lfloor\frac{c-am}{b}\right\rfloor.$$
Dann zerfällt das Gitterdreieck in volle Blöcke und einen kleineren Rest, woraus die Rekursion
$$L(a,b;c)=L(b,r;c-b(km+h))+k\frac{m(m-1)}{2}+mh$$
folgt. Die Basisfälle sind direkt: Ist \(a>c\), gibt es keine positiven Lösungen; ist \(a=b\), dann gilt
$$L(a,a;c)=\frac{m(m-1)}{2}.$$
Das ist ein euklidischer Abstieg für \((a,b)\). Da die Koeffizienten \(18,10,30\) fest sind, ist diese Rekursion in der Praxis sehr flach.
Sei
$$M(x)=\sum_{m\le x}\mu(m)$$
die klassische Mertens-Funktion, und definiere das transformierte Präfix
$$A(x)=\sum_{j\ge 0} M\!\left(\left\lfloor\frac{x}{3^j}\right\rfloor\right).$$
Seine diskrete Differenz ist
$$A(d)-A(d-1)=\sum_{3^j\mid d}\mu\!\left(\frac{d}{3^j}\right).$$
Falls \(3\nmid d\), bleibt nur \(j=0\), also erhält man \(\mu(d)\). Falls \(3\mid d\), heben sich die möglichen nichtverschwindenden Beiträge als \(\mu(u)+\mu(3u)\) weg. Somit
$$A(d)-A(d-1)= \begin{cases} \mu(d), & 3\nmid d,\\ 0, & 3\mid d. \end{cases}$$
Genau deshalb verwenden die Implementierungen nicht einfach rohe Mertens-Werte, sondern dieses transformierte Präfix: benötigt wird das Möbius-Gewicht für Zahlen, deren gemeinsamer Faktor höchstens aus Dreierpotenzen bestehen darf.
Mit \(n=3N+6\) lautet die Zählung für den reduzierten Sektor
$$z=\sum_{d=1}^{n}\bigl(A(d)-A(d-1)\bigr)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
Mit dem Resultat aus dem vorigen Schritt wird daraus
$$z=\sum_{\substack{1\le d\le n\\3\nmid d}}\mu(d)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
Das ist ein typisches Möbius-Inversionsmuster: Zuerst zählt man alle Richtungen im Streifen, dann entfernt man die nicht-primitiven, wobei Dreierpotenzen durch die spezielle Gewichtung ausdrücklich zugelassen bleiben.
Der Ausdruck \(\lfloor n/d\rfloor\) ist auf ganzen Intervallen konstant. Gilt für alle \(d\in[a,b]\)
$$\left\lfloor\frac{n}{d}\right\rfloor=g,$$
so ist der gesamte Blockbeitrag
$$q(g)\sum_{d=a}^{b}\bigl(A(d)-A(d-1)\bigr)=q(g)\bigl(A(b)-A(a-1)\bigr).$$
Darum arbeiten die Implementierungen mit Quotientenblöcken. Es treten nur ungefähr \(2\sqrt{n}\) verschiedene Quotienten auf, also genügen Präfixdifferenzen und ein Streifenzähler pro Block.
Am Ende liefern die Implementierungen
$$F(N)=4z+2.$$
Das zeigt, dass \(z\) zuerst nur einen reduzierten Symmetriesektor zählt. Der Faktor \(4\) ergänzt die gespiegelten Sektoren, und das abschließende \(+2\) behandelt zwei spezielle symmetrische Randfälle separat.
Für \(N=10\) ist
$$n=3\cdot 10+6=36.$$
Der kleinste Gitterpunkt im Streifen ist \((1,1)\), und dieser erscheint ab
$$18\cdot 1+10\cdot 1=28\le g.$$
Daher gilt \(q(g)=0\) für alle \(g<28\). Für \(d\ge 2\) ist aber \(\lfloor 36/d\rfloor\le 18\), also verschwinden alle diese Terme. Nur \(d=1\) bleibt übrig:
$$q(36)=1,$$
denn \((1,1)\) erfüllt \(28\le 36<48\). Außerdem ist \(A(1)-A(0)=\mu(1)=1\). Also
$$z=1$$
und damit
$$F(10)=4\cdot 1+2=6,$$
genau wie in den Implementierungen geprüft wird.
Die C++-, Python- und Java-Implementierungen folgen derselben Strategie. Zuerst setzen sie \(n=3N+6\). Danach wird die Mertens-Funktion \(M(x)\) memoisiert, weil das transformierte Präfix \(A(x)\) dieselben Argumente \(\lfloor x/3^j\rfloor\) immer wieder benötigt. So wird aus dem Möbius-Gewicht eine cachefreundliche arithmetische Vorwärtsfunktion.
Für den geometrischen Teil wird \(q(g)\) als Differenz zweier rekursiver Gitterzähler berechnet. Jeder dieser Zähler reduziert das Paar \((a,b)\) per euklidischem Schritt, addiert volle Dreiecksblöcke und stoppt, sobald kein Restbereich mehr übrig ist oder ein symmetrischer Basisfall erreicht wurde.
Die endgültige Summe wird nicht Divisor für Divisor ausgewertet. Stattdessen laufen die Implementierungen über die verschiedenen Werte von \(\lfloor n/d\rfloor\): eine Schleife behandelt kleine Divisoren direkt, die komplementäre Schleife deckt große Bereiche über Intervallgrenzen ab. Pro Block wird eine Präfixdifferenz von \(A\) mit genau einem Wert \(q(g)\) multipliziert. Sobald \(q(g)=0\) ist, können die restlichen Blöcke sofort verworfen werden.
Durch die Quotientengruppierung werden nur \(O(\sqrt{n})\) Blöcke besucht statt aller \(n\) Divisoren. Jede Streifenauswertung benutzt einen euklidischen Abstieg mit festen Koeffizienten und ist daher für diese Aufgabe praktisch konstant schnell. Die dominante Arbeit ist die memoisiert berechnete Mertens-Vorfunktion auf den verschiedenen Argumenten, die durch Quotientenblöcke und wiederholtes Teilen durch \(3\) entstehen.
Die sichtbare Struktur ist also sublinear in \(n\), und der Speicherverbrauch wird vom Mertens-Cache dominiert. Das ist um Größenordnungen kleiner als eine direkte Billardsimulation oder ein naiver Scan aller möglichen Gitterrichtungen.
C++, Python ve Java implementasyonlarının gösterdiği şey şu: bilardo problemi, yansımaları açıp doğrusal hareketi tamsayı kafesi üzerinde sayma problemine dönüştürülerek çözülüyor. Verilen \(N\) için geometri
$$n=3N+6$$
parametresine indirgeniyor. Bundan sonra doğrudan yörünge takibi yapmak yerine, iki rasyonel doğru arasında kalan ince bir şeritteki ilkel kafes yönleri Möbius terslemesi, Mertens önekleri ve hızlı bir kafes-nokta sayacıyla hesaplanıyor.
Implementasyonlar, tek bir simetri sektörünün
$$q(g)=L(18,10;g)-L(18,30;g)$$
ile sayıldığını gösteriyor. Burada \(L(a,b;c)\),
$$ax+by\le c$$
koşulunu sağlayan pozitif tamsayı \((x,y)\) çiftlerinin sayısıdır. Dolayısıyla
$$q(g)=\#\left\{(x,y)\in\mathbb{Z}_{>0}^2:18x+10y\le g<18x+30y\right\}.$$
Yani \(q(g)\), \(18x+10y=g\) doğrusunun altında kalan fakat \(18x+30y=g\) doğrusunun altında kalmayan noktaları sayar. Bilardo açılımından çıkan temel geometrik bölge tam olarak bu dar şerittir.
Sabit \(a,b,c\) için temel sayım
$$L(a,b;c)=\sum_{x=1}^{\lfloor c/a\rfloor}\left\lfloor\frac{c-ax}{b}\right\rfloor$$
şeklindedir. \(a\ge b\) varsayalım ve
$$m=\left\lfloor\frac{c}{a}\right\rfloor,\qquad k=\left\lfloor\frac{a-1}{b}\right\rfloor,\qquad r=a-kb,\qquad h=\left\lfloor\frac{c-am}{b}\right\rfloor$$
tanımlarını yapalım. O zaman bölge, tam bloklar ve daha küçük bir artık bölgeye ayrılarak
$$L(a,b;c)=L(b,r;c-b(km+h))+k\frac{m(m-1)}{2}+mh$$
özyinelemesi elde edilir. Taban durumları açıktır: \(a>c\) ise hiç çözüm yoktur; \(a=b\) ise
$$L(a,a;c)=\frac{m(m-1)}{2}.$$
Bu, \((a,b)\) üzerinde çalışan bir Öklid algoritması inişidir. Buradaki katsayılar \(18,10,30\) sabit olduğu için özyineleme derinliği çok küçüktür.
Klasik Mertens fonksiyonunu
$$M(x)=\sum_{m\le x}\mu(m)$$
olarak alalım ve dönüştürülmüş öneği
$$A(x)=\sum_{j\ge 0} M\!\left(\left\lfloor\frac{x}{3^j}\right\rfloor\right)$$
diye tanımlayalım. Ayrık fark
$$A(d)-A(d-1)=\sum_{3^j\mid d}\mu\!\left(\frac{d}{3^j}\right)$$
olur. Eğer \(3\nmid d\) ise yalnızca \(j=0\) vardır ve sonuç \(\mu(d)\) olur. Eğer \(3\mid d\) ise sıfır olmayan olası terimler \(\mu(u)+\mu(3u)\) biçiminde birbirini götürür. Sonuç olarak
$$A(d)-A(d-1)= \begin{cases} \mu(d), & 3\nmid d,\\ 0, & 3\mid d. \end{cases}$$
Bu özdeşlik, implementasyonların neden düz Mertens toplamı yerine bu dönüşmüş öneği kullandığını açıklar: gereken ağırlık, yalnızca \(3\) dışındaki ortak asal çarpanları dışlayan Möbius filtresidir.
\(n=3N+6\) için azaltılmış sektör sayısı
$$z=\sum_{d=1}^{n}\bigl(A(d)-A(d-1)\bigr)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)$$
şeklindedir. Bir önceki adımdan sonra bu
$$z=\sum_{\substack{1\le d\le n\\3\nmid d}}\mu(d)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)$$
haline gelir. Bu klasik bir Möbius terslemesi biçimidir: önce şeritteki bütün yönler sayılır, sonra ilkel olmayanlar çıkarılır; yalnızca \(3\) kuvvetleri bu özel ağırlık nedeniyle izinli kalır.
\(\lfloor n/d\rfloor\) ifadesi aralıklarda sabittir. Eğer tüm \(d\in[a,b]\) için
$$\left\lfloor\frac{n}{d}\right\rfloor=g$$
ise, bu bloğun katkısı
$$q(g)\sum_{d=a}^{b}\bigl(A(d)-A(d-1)\bigr)=q(g)\bigl(A(b)-A(a-1)\bigr)$$
olur. Bu yüzden implementasyonlar tek tek bölen dolaşmak yerine bölüm blokları üzerinden ilerler. Yaklaşık \(2\sqrt{n}\) farklı bölüm değeri bulunduğundan, her blok için yalnızca bir önek farkı ve bir şerit sayısı gerekir.
Son aşamada implementasyonlar
$$F(N)=4z+2$$
döndürür. Bu, \(z\)'nin önce tek bir indirgenmiş simetri sektörünü saydığını gösterir. \(4\) katsayısı ayna sektörleri geri ekler, son \(+2\) ise iki özel simetrik sınır durumunu ayrıca hesaba katar.
\(N=10\) için
$$n=3\cdot 10+6=36$$
olur. Şeritteki en küçük nokta \((1,1)\)'dir ve bu nokta ancak
$$18\cdot 1+10\cdot 1=28\le g$$
olduğunda içeri girer. Demek ki \(g<28\) için \(q(g)=0\). \(d\ge 2\) iken \(\lfloor 36/d\rfloor\le 18\) olduğundan bu terimlerin hepsi sıfırdır. Yalnızca \(d=1\) kalır:
$$q(36)=1,$$
çünkü \((1,1)\) için \(28\le 36<48\) sağlanır. Ayrıca \(A(1)-A(0)=\mu(1)=1\). Böylece
$$z=1$$
ve son sonuç
$$F(10)=4\cdot 1+2=6$$
olur; bu da implementasyonlardaki kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları aynı akışı izler. Önce \(n=3N+6\) hesaplanır. Ardından Mertens fonksiyonu \(M(x)\) belleklenir; çünkü dönüştürülmüş önek \(A(x)\), \(\lfloor x/3^j\rfloor\) biçimindeki çok sayıda tekrar eden argümana ihtiyaç duyar. Böylece Möbius ağırlığı hızlı bir aritmetik önek sorgusuna dönüşür.
Geometrik bölümde \(q(g)\), iki özyinelemeli kafes sayacının farkı olarak bulunur. Her sayaç \((a,b)\) çiftini Öklid adımıyla küçültür, tam üçgensel blokların katkısını ekler ve bölge boşaldığında ya da simetrik taban duruma geldiğinde durur.
Son toplam tüm bölenler üzerinden tek tek yapılmaz. Bunun yerine \(\lfloor n/d\rfloor\) değerlerinin sabit kaldığı bloklar dolaşılır: bir döngü küçük bölenleri, diğer tamamlayıcı döngü büyük aralıkları kapsar. Her blokta \(A\)'nın bir önek farkı ile tek bir \(q(g)\) değeri çarpılır. \(q(g)=0\) olduğunda kalan blokların katkısı da sıfır olacağından erkenden çıkılabilir.
Dış toplam bölüm gruplaması kullandığı için tüm \(n\) bölenler yerine yalnızca \(O(\sqrt{n})\) blok ziyaret edilir. Her şerit hesabı sabit katsayılı bir Öklid inişi kullandığından bu problem özelinde neredeyse sabit zamanlıdır. Baskın maliyet, bölüm blokları ve \(3\)'e tekrar tekrar bölme işlemleriyle oluşan farklı argümanlar üzerinde çalışan Mertens önbelleğidir.
Dolayısıyla görünür yapı \(n\)'e göre alt-doğrusal davranır; bellek kullanımı da büyük ölçüde Mertens önbelleği tarafından belirlenir. Bu, doğrudan bilardo simülasyonundan veya bütün aday kafes yönlerini taramaktan çok daha küçüktür.
Las implementaciones en C++, Python y Java muestran que el problema de billar se resuelve desplegando las reflexiones y convirtiéndolas en movimiento rectilíneo sobre una red entera. Para un valor dado de \(N\), la geometría se comprime en el parámetro aritmético
$$n=3N+6,$$
y la respuesta pasa a ser un conteo ponderado de direcciones primitivas dentro de una franja estrecha limitada por dos rectas racionales. En vez de seguir rebotes uno por uno, el método usa inversión de Möbius, prefijos de Mertens y un contador rápido de puntos de red.
Las implementaciones muestran que un sector de simetría se cuenta mediante
$$q(g)=L(18,10;g)-L(18,30;g),$$
donde \(L(a,b;c)\) es el número de pares enteros positivos \((x,y)\) tales que
$$ax+by\le c.$$
Por tanto,
$$q(g)=\#\left\{(x,y)\in\mathbb{Z}_{>0}^2:18x+10y\le g<18x+30y\right\}.$$
Así, \(q(g)\) cuenta los puntos de la red situados bajo la recta \(18x+10y=g\), pero no bajo la recta más inclinada \(18x+30y=g\). Esa franja es la huella aritmética del despliegue geométrico del billar.
Para \(a,b,c\) fijos, el conteo básico es
$$L(a,b;c)=\sum_{x=1}^{\lfloor c/a\rfloor}\left\lfloor\frac{c-ax}{b}\right\rfloor.$$
Si \(a\ge b\), definimos
$$m=\left\lfloor\frac{c}{a}\right\rfloor,\qquad k=\left\lfloor\frac{a-1}{b}\right\rfloor,\qquad r=a-kb,\qquad h=\left\lfloor\frac{c-am}{b}\right\rfloor.$$
Entonces la región se descompone en bloques completos más un resto más pequeño, y aparece la recursión
$$L(a,b;c)=L(b,r;c-b(km+h))+k\frac{m(m-1)}{2}+mh.$$
Los casos base son inmediatos: si \(a>c\), no hay soluciones positivas; si \(a=b\), entonces
$$L(a,a;c)=\frac{m(m-1)}{2}.$$
Esto es un descenso tipo algoritmo de Euclides sobre \((a,b)\). Como aquí los coeficientes \(18,10,30\) son fijos, la profundidad recursiva es muy pequeña.
Sea
$$M(x)=\sum_{m\le x}\mu(m)$$
la función de Mertens clásica, y definamos el prefijo transformado
$$A(x)=\sum_{j\ge 0} M\!\left(\left\lfloor\frac{x}{3^j}\right\rfloor\right).$$
Su diferencia discreta es
$$A(d)-A(d-1)=\sum_{3^j\mid d}\mu\!\left(\frac{d}{3^j}\right).$$
Si \(3\nmid d\), solo contribuye \(j=0\), así que el valor es \(\mu(d)\). Si \(3\mid d\), los posibles términos no nulos aparecen como \(\mu(u)+\mu(3u)\) y se cancelan. Por ello
$$A(d)-A(d-1)= \begin{cases} \mu(d), & 3\nmid d,\\ 0, & 3\mid d. \end{cases}$$
Esa identidad explica por qué las implementaciones no usan una suma de Mertens simple: lo que se necesita es el peso de Möbius sobre enteros cuyo factor común no puede contener primos distintos de \(3\), salvo que aparezcan potencias de \(3\).
Con \(n=3N+6\), el conteo del sector reducido es
$$z=\sum_{d=1}^{n}\bigl(A(d)-A(d-1)\bigr)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
Usando el paso anterior, esto se convierte en
$$z=\sum_{\substack{1\le d\le n\\3\nmid d}}\mu(d)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
Es el patrón típico de la inversión de Möbius: primero se cuentan todas las direcciones dentro de la franja y luego se eliminan las no primitivas, dejando que las potencias de \(3\) sobrevivan al filtro especial.
El valor \(\lfloor n/d\rfloor\) es constante por intervalos. Si para todo \(d\in[a,b]\) se cumple
$$\left\lfloor\frac{n}{d}\right\rfloor=g,$$
entonces la contribución total del bloque es
$$q(g)\sum_{d=a}^{b}\bigl(A(d)-A(d-1)\bigr)=q(g)\bigl(A(b)-A(a-1)\bigr).$$
Por eso las implementaciones no recorren todos los divisores. Solo procesan bloques de cociente constante, y aparecen aproximadamente \(2\sqrt{n}\) valores distintos.
Al final, las implementaciones devuelven
$$F(N)=4z+2.$$
Esto muestra que \(z\) cuenta primero un único sector reducido. El factor \(4\) reconstruye los sectores reflejados y el término \(+2\) añade dos casos simétricos excepcionales tratados aparte.
Para \(N=10\),
$$n=3\cdot 10+6=36.$$
El punto más pequeño de la franja es \((1,1)\), que aparece cuando
$$18\cdot 1+10\cdot 1=28\le g.$$
Por tanto, \(q(g)=0\) para todo \(g<28\). Si \(d\ge 2\), entonces \(\lfloor 36/d\rfloor\le 18\), así que todos esos términos se anulan. Solo sobrevive \(d=1\):
$$q(36)=1,$$
porque \((1,1)\) satisface \(28\le 36<48\). Además, \(A(1)-A(0)=\mu(1)=1\). Luego
$$z=1,$$
y la respuesta final es
$$F(10)=4\cdot 1+2=6,$$
en acuerdo exacto con la comprobación incluida en las implementaciones.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero calculan \(n=3N+6\). Después memorizan la función de Mertens \(M(x)\), porque el prefijo transformado \(A(x)\) pide muchas veces valores de la forma \(\lfloor x/3^j\rfloor\) y esos argumentos se repiten con frecuencia.
Para la parte geométrica, la implementación evalúa \(q(g)\) como diferencia entre dos contadores recursivos de puntos de red. Cada contador reduce \((a,b)\) con un paso euclídeo, suma la contribución de bloques triangulares completos y termina cuando la región restante es vacía o cae en un caso base simétrico.
La suma final no se ejecuta divisor por divisor. En su lugar, la implementación recorre los bloques donde \(\lfloor n/d\rfloor\) es constante: un bucle maneja divisores pequeños y el otro cubre los intervalos complementarios mediante extremos de bloque. En cada bloque, una diferencia de prefijos de \(A\) se multiplica por un único valor \(q(g)\). Cuando \(q(g)=0\), el resto de bloques ya no puede aportar nada y el proceso se corta antes.
La agrupación por cocientes hace que solo se visiten \(O(\sqrt{n})\) bloques en lugar de los \(n\) divisores. Cada evaluación de la franja usa un descenso euclídeo con coeficientes fijos, por lo que en esta tarea su coste es prácticamente constante. El trabajo dominante está en la evaluación memoizada del prefijo de Mertens sobre los argumentos distintos generados por los bloques y por la división repetida entre \(3\).
En consecuencia, la estructura observable es sublineal en \(n\), y la memoria queda dominada por la caché de Mertens. Eso es mucho más pequeño que simular trayectorias de billar de forma directa o recorrer ingenuamente todas las direcciones candidatas.
从 C++、Python 和 Java 的实现可以看出，这道台球题并不是直接逐条轨迹模拟，而是先把反射展开成整数格点上的直线运动。对给定的 \(N\)，几何条件被压缩成参数
$$n=3N+6,$$
随后问题转化为：在两条有理斜率边界之间的一条狭窄条带里，统计满足特定原始性条件的格点方向。真正起作用的是 Möbius 反演、Mertens 前缀和，以及一个快速的格点计数递归。
实现表明，一个基本对称扇区的计数可以写成
$$q(g)=L(18,10;g)-L(18,30;g),$$
其中 \(L(a,b;c)\) 表示满足
$$ax+by\le c$$
的正整数点 \((x,y)\) 的个数。因此
$$q(g)=\#\left\{(x,y)\in\mathbb{Z}_{>0}^2:18x+10y\le g<18x+30y\right\}.$$
也就是说，\(q(g)\) 统计的是落在直线 \(18x+10y=g\) 下方、但没有落在更陡的直线 \(18x+30y=g\) 下方的格点。这个“窄条带”就是展开后的台球几何在算术上的核心对象。
对固定的 \(a,b,c\)，基本计数函数是
$$L(a,b;c)=\sum_{x=1}^{\lfloor c/a\rfloor}\left\lfloor\frac{c-ax}{b}\right\rfloor.$$
若 \(a\ge b\)，定义
$$m=\left\lfloor\frac{c}{a}\right\rfloor,\qquad k=\left\lfloor\frac{a-1}{b}\right\rfloor,\qquad r=a-kb,\qquad h=\left\lfloor\frac{c-am}{b}\right\rfloor.$$
这样原来的大三角区域可以拆成若干完整块和一个更小的剩余区域，从而得到递归
$$L(a,b;c)=L(b,r;c-b(km+h))+k\frac{m(m-1)}{2}+mh.$$
边界情形也很直接：如果 \(a>c\)，则没有正整数解；如果 \(a=b\)，那么
$$L(a,a;c)=\frac{m(m-1)}{2}.$$
这本质上是对系数对 \((a,b)\) 做欧几里得算法式的递降。由于这里的系数始终是 \(18,10,30\)，递归深度非常小。
设经典 Mertens 函数为
$$M(x)=\sum_{m\le x}\mu(m),$$
并定义实现中实际需要的变形前缀
$$A(x)=\sum_{j\ge 0} M\!\left(\left\lfloor\frac{x}{3^j}\right\rfloor\right).$$
它的离散差分满足
$$A(d)-A(d-1)=\sum_{3^j\mid d}\mu\!\left(\frac{d}{3^j}\right).$$
如果 \(3\nmid d\)，只有 \(j=0\) 这一项，因此差分就是 \(\mu(d)\)。如果 \(3\mid d\)，可能非零的项会以 \(\mu(u)+\mu(3u)\) 的形式成对抵消，所以结果为 \(0\)。于是得到精确恒等式
$$A(d)-A(d-1)= \begin{cases} \mu(d), & 3\nmid d,\\ 0, & 3\mid d. \end{cases}$$
这说明实现并不是在用普通的 Mertens 前缀，而是在构造一种特殊的 Möbius 过滤器：它会去掉所有含有非 \(3\) 公因子的方向，但允许保留 \(3\) 的幂次所带来的缩放。
令 \(n=3N+6\)，那么缩减后扇区的计数是
$$z=\sum_{d=1}^{n}\bigl(A(d)-A(d-1)\bigr)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
结合上一步，可改写为更透明的形式
$$z=\sum_{\substack{1\le d\le n\\3\nmid d}}\mu(d)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
这就是典型的 Möbius 反演结构：先把条带中的所有方向都算进去，再通过 Möbius 权重去掉非原始方向；不过与普通“只保留互素”不同，这里对素数 \(3\) 做了特例处理，因此 \(3\) 的幂仍然允许存在。
\(\lfloor n/d\rfloor\) 在整段区间上保持不变。若对所有 \(d\in[a,b]\) 都有
$$\left\lfloor\frac{n}{d}\right\rfloor=g,$$
那么这整段的贡献就是
$$q(g)\sum_{d=a}^{b}\bigl(A(d)-A(d-1)\bigr)=q(g)\bigl(A(b)-A(a-1)\bigr).$$
因此实现并不会把 \(1\) 到 \(n\) 的每个 \(d\) 都扫一遍，而是只处理商值相同的区块。不同的商大约只有 \(2\sqrt{n}\) 个，所以复杂度被显著压缩。
最后实现返回
$$F(N)=4z+2.$$
这说明算术和 \(z\) 只统计了一个约化后的对称扇区。乘上 \(4\) 是把镜像扇区补回去，而额外的 \(+2\) 则对应两个需要单独补上的特殊对称情形。
当 \(N=10\) 时，
$$n=3\cdot 10+6=36.$$
条带中最小的格点是 \((1,1)\)，它出现的门槛是
$$18\cdot 1+10\cdot 1=28\le g.$$
所以只要 \(g<28\)，就有 \(q(g)=0\)。若 \(d\ge 2\)，则 \(\lfloor 36/d\rfloor\le 18\)，对应项全部消失。唯一留下的是 \(d=1\)：
$$q(36)=1,$$
因为 \((1,1)\) 满足 \(28\le 36<48\)。同时 \(A(1)-A(0)=\mu(1)=1\)。于是
$$z=1,$$
最终得到
$$F(10)=4\cdot 1+2=6,$$
与实现中的校验值完全一致。
C++、Python 和 Java 实现的流程是一样的。首先计算 \(n=3N+6\)。然后对 Mertens 函数 \(M(x)\) 做记忆化，因为变形前缀 \(A(x)\) 需要大量重复查询 \(\lfloor x/3^j\rfloor\) 这些参数，缓存可以避免重复递归。
在几何部分，实现把 \(q(g)\) 写成两个格点递归计数的差。每个计数器都对 \((a,b)\) 执行欧几里得式缩减，累计完整三角块的贡献，并在区域为空或进入对称基例时停止。由于系数固定，这一部分非常轻量。
最终求和并不是对所有 \(d\) 逐项计算，而是按照 \(\lfloor n/d\rfloor\) 的相同取值分成若干块。一个循环处理较小的除数，另一个互补循环处理较大的区间端点。每个块只需要一次前缀差 \(A(b)-A(a-1)\) 和一次条带计数 \(q(g)\)。一旦 \(q(g)=0\)，后续块必然也没有贡献，于是可以直接提前结束。
由于使用了商值分块，外层求和只访问 \(O(\sqrt{n})\) 个区块，而不是全部 \(n\) 个除数。每次条带计数都只是固定系数上的欧几里得递归，因此对本题而言几乎可以视为常数时间。主导成本来自 Mertens 前缀的记忆化递归，它作用在由分块和不断除以 \(3\) 所产生的那些不同参数上。
因此，从可见结构来看，算法对 \(n\) 呈明显的次线性行为，内存主要由 Mertens 缓存占据。这远小于直接模拟台球路径或朴素枚举所有候选格点方向的代价。
Из реализаций на C++, Python и Java видно, что задача о бильярде решается не прямым моделированием отражений, а разворачиванием траекторий в прямые лучи на целочисленной решётке. Для данного \(N\) геометрия сводится к параметру
$$n=3N+6,$$
после чего нужно подсчитать примитивные направления в узкой полосе между двумя рациональными прямыми. Вместо перебора ударов используются инверсия Мёбиуса, префиксы функции Мертенса и быстрый рекурсивный счётчик решётчатых точек.
Реализации показывают, что один сектор симметрии задаётся величиной
$$q(g)=L(18,10;g)-L(18,30;g),$$
где \(L(a,b;c)\) обозначает число положительных целочисленных пар \((x,y)\), удовлетворяющих
$$ax+by\le c.$$
Следовательно,
$$q(g)=\#\left\{(x,y)\in\mathbb{Z}_{>0}^2:18x+10y\le g<18x+30y\right\}.$$
То есть \(q(g)\) считает точки под прямой \(18x+10y=g\), но не под более крутой прямой \(18x+30y=g\). Именно такая узкая полоса и появляется после развёртки бильярдной геометрии.
Для фиксированных \(a,b,c\) базовый счётчик имеет вид
$$L(a,b;c)=\sum_{x=1}^{\lfloor c/a\rfloor}\left\lfloor\frac{c-ax}{b}\right\rfloor.$$
Пусть \(a\ge b\), и положим
$$m=\left\lfloor\frac{c}{a}\right\rfloor,\qquad k=\left\lfloor\frac{a-1}{b}\right\rfloor,\qquad r=a-kb,\qquad h=\left\lfloor\frac{c-am}{b}\right\rfloor.$$
Тогда область раскладывается на полные блоки и меньший остаток, откуда получается рекурсия
$$L(a,b;c)=L(b,r;c-b(km+h))+k\frac{m(m-1)}{2}+mh.$$
Базовые случаи просты: если \(a>c\), положительных решений нет; если \(a=b\), то
$$L(a,a;c)=\frac{m(m-1)}{2}.$$
Это по сути евклидов спуск по паре коэффициентов \((a,b)\). Поскольку в задаче используются фиксированные коэффициенты \(18,10,30\), глубина рекурсии мала.
Пусть
$$M(x)=\sum_{m\le x}\mu(m)$$
— классическая функция Мертенса, а
$$A(x)=\sum_{j\ge 0} M\!\left(\left\lfloor\frac{x}{3^j}\right\rfloor\right)$$
— преобразованный префикс, который фактически используется в реализации. Его дискретная разность равна
$$A(d)-A(d-1)=\sum_{3^j\mid d}\mu\!\left(\frac{d}{3^j}\right).$$
Если \(3\nmid d\), остаётся только член \(j=0\), то есть получается \(\mu(d)\). Если \(3\mid d\), то возможные ненулевые члены приходят в виде \(\mu(u)+\mu(3u)\) и взаимно сокращаются. Поэтому
$$A(d)-A(d-1)= \begin{cases} \mu(d), & 3\nmid d,\\ 0, & 3\mid d. \end{cases}$$
Именно это объясняет специальную роль числа \(3\): преобразованный префикс реализует фильтр Мёбиуса, который устраняет общие множители, кроме степеней \(3\).
При \(n=3N+6\) число объектов в сокращённом секторе равно
$$z=\sum_{d=1}^{n}\bigl(A(d)-A(d-1)\bigr)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
С учётом предыдущего шага это переписывается так:
$$z=\sum_{\substack{1\le d\le n\\3\nmid d}}\mu(d)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
Это типичная схема инверсии Мёбиуса: сначала считаются все направления в полосе, затем вычёркиваются непримитивные, но степени \(3\) сохраняются благодаря специальному весу.
Величина \(\lfloor n/d\rfloor\) постоянна на целых интервалах. Если для всех \(d\in[a,b]\)
$$\left\lfloor\frac{n}{d}\right\rfloor=g,$$
то вклад всего блока равен
$$q(g)\sum_{d=a}^{b}\bigl(A(d)-A(d-1)\bigr)=q(g)\bigl(A(b)-A(a-1)\bigr).$$
Поэтому реализации не перебирают все \(d\) по одному. Они обходят только блоки одинакового частного, а различных значений возникает порядка \(2\sqrt{n}\).
В конце реализации возвращают
$$F(N)=4z+2.$$
Это означает, что \(z\) сначала считает только один приведённый сектор симметрии. Множитель \(4\) возвращает зеркальные копии, а добавка \(+2\) учитывает два особых симметричных граничных случая.
Для \(N=10\)
$$n=3\cdot 10+6=36.$$
Минимальная точка полосы — \((1,1)\), и она появляется при
$$18\cdot 1+10\cdot 1=28\le g.$$
Значит, для всех \(g<28\) имеем \(q(g)=0\). Если \(d\ge 2\), то \(\lfloor 36/d\rfloor\le 18\), и соответствующий вклад исчезает. Остаётся только \(d=1\):
$$q(36)=1,$$
поскольку точка \((1,1)\) удовлетворяет \(28\le 36<48\). Кроме того, \(A(1)-A(0)=\mu(1)=1\). Следовательно,
$$z=1,$$
а окончательный ответ равен
$$F(10)=4\cdot 1+2=6,$$
что точно совпадает с контрольным значением в реализациях.
Реализации на C++, Python и Java устроены одинаково. Сначала вычисляется \(n=3N+6\). Затем мемоизируется функция Мертенса \(M(x)\), поскольку преобразованный префикс \(A(x)\) многократно запрашивает значения вида \(\lfloor x/3^j\rfloor\), и без кэша рекурсия бы слишком часто повторялась.
Для геометрической части реализация вычисляет \(q(g)\) как разность двух рекурсивных счётчиков решётчатых точек. Каждый такой счётчик делает евклидов шаг по коэффициентам \((a,b)\), добавляет вклад полных треугольных блоков и останавливается, когда оставшаяся область пуста или сводится к симметричному базовому случаю.
Финальная сумма считается не по каждому делителю отдельно, а по блокам, на которых \(\lfloor n/d\rfloor\) постоянно. Один цикл покрывает малые делители, второй — дополняющие интервалы больших диапазонов. Для каждого блока берётся одна разность префиксов \(A\) и одно значение \(q(g)\). Как только \(q(g)=0\), оставшиеся блоки уже не могут дать вклад, и вычисление завершается раньше.
Благодаря группировке по значениям частного внешний проход использует только \(O(\sqrt{n})\) блоков вместо всех \(n\) делителей. Каждое вычисление полосы опирается на евклидов спуск с фиксированными коэффициентами, поэтому для данной задачи его стоимость практически постоянна. Основная работа сосредоточена в мемоизированном вычислении префикса Мертенса на различных аргументах, возникающих из блоков и повторного деления на \(3\).
Следовательно, наблюдаемая структура алгоритма существенно сублинейна по \(n\), а память в основном определяется размером кэша Мертенса. Это гораздо эффективнее прямого моделирования бильярдных траекторий или наивного перебора всех кандидатных направлений.
تُظهر تطبيقات C++ وPython وJava أن مسألة البلياردو لا تُحل بمحاكاة كل انعكاس مباشرة، بل عبر فرد المسار وتحويله إلى حركة مستقيمة على شبكة من النقاط الصحيحة. عند قيمة معطاة \(N\)، تُضغط الهندسة في المعامل
$$n=3N+6,$$
ثم تصبح المهمة هي عدّ الاتجاهات البدائية الواقعة داخل شريط ضيق بين مستقيمين ذوي معاملات نسبية. وبدلاً من تتبع الارتدادات واحداً واحداً، يعتمد الحل على قلب Möbius، ومجاميع Mertens التراكمية، وعدّاد سريع لنقاط الشبكة.
تبيّن التطبيقات أن قطاع تماثل واحداً يمكن عدّه بواسطة
$$q(g)=L(18,10;g)-L(18,30;g),$$
حيث إن \(L(a,b;c)\) هو عدد الأزواج الصحيحة الموجبة \((x,y)\) التي تحقق
$$ax+by\le c.$$
وبالتالي
$$q(g)=\#\left\{(x,y)\in\mathbb{Z}_{>0}^2:18x+10y\le g<18x+30y\right\}.$$
إذن \(q(g)\) يعدّ النقاط الواقعة تحت المستقيم \(18x+10y=g\)، ولكن غير الواقعة تحت المستقيم الأكثر انحداراً \(18x+30y=g\). هذا الشريط هو الصورة الحسابية للمنطقة التي تظهر بعد فرد انعكاسات البلياردو.
لثوابت \(a,b,c\)، يكون العد الأساسي
$$L(a,b;c)=\sum_{x=1}^{\lfloor c/a\rfloor}\left\lfloor\frac{c-ax}{b}\right\rfloor.$$
إذا افترضنا \(a\ge b\)، ونعرّف
$$m=\left\lfloor\frac{c}{a}\right\rfloor,\qquad k=\left\lfloor\frac{a-1}{b}\right\rfloor,\qquad r=a-kb,\qquad h=\left\lfloor\frac{c-am}{b}\right\rfloor,$$
فإن المنطقة تنقسم إلى كتل كاملة وباقٍ أصغر، فنحصل على العودية
$$L(a,b;c)=L(b,r;c-b(km+h))+k\frac{m(m-1)}{2}+mh.$$
أما الحالات الأساسية فمباشرة: إذا كان \(a>c\) فلا توجد حلول موجبة، وإذا كان \(a=b\) فإن
$$L(a,a;c)=\frac{m(m-1)}{2}.$$
هذا في جوهره هبوط خوارزمية إقليدس على الزوج \((a,b)\). ولأن المعاملات هنا ثابتة وهي \(18,10,30\)، فإن عمق العودية صغير جداً.
لتكن
$$M(x)=\sum_{m\le x}\mu(m)$$
هي دالة Mertens التقليدية، ولنعرّف السابقة المحوّلة
$$A(x)=\sum_{j\ge 0} M\!\left(\left\lfloor\frac{x}{3^j}\right\rfloor\right).$$
عند أخذ الفرق المنفصل نحصل على
$$A(d)-A(d-1)=\sum_{3^j\mid d}\mu\!\left(\frac{d}{3^j}\right).$$
إذا كان \(3\nmid d\)، فالمساهمة الوحيدة هي \(j=0\)، وبالتالي يكون الفرق \(\mu(d)\). أما إذا كان \(3\mid d\)، فإن الحدود غير الصفرية الممكنة تأتي على الصورة \(\mu(u)+\mu(3u)\) فتتلاشى. لذلك
$$A(d)-A(d-1)= \begin{cases} \mu(d), & 3\nmid d,\\ 0, & 3\mid d. \end{cases}$$
وهذا يفسر لماذا لا تستخدم التطبيقات مجاميع Mertens الخام مباشرة: المطلوب هو مرشح Möbius يزيل العوامل المشتركة غير المرتبطة بالقوة \(3\)-ية، مع الإبقاء على قوى \(3\) مسموحاً بها.
عندما \(n=3N+6\)، يكون عدّ القطاع المختزل هو
$$z=\sum_{d=1}^{n}\bigl(A(d)-A(d-1)\bigr)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
وباستخدام النتيجة السابقة يمكن كتابة ذلك بصورة أوضح:
$$z=\sum_{\substack{1\le d\le n\\3\nmid d}}\mu(d)\,q\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
هذا هو الشكل المعتاد لقلب Möbius: نعدّ أولاً جميع الاتجاهات داخل الشريط، ثم نحذف غير البدائي منها، لكن مع معاملة خاصة للعدد \(3\) كما يفرضها وزن السابقة المحوّلة.
القيمة \(\lfloor n/d\rfloor\) تبقى ثابتة على فترات كاملة. فإذا تحقق لكل \(d\in[a,b]\) أن
$$\left\lfloor\frac{n}{d}\right\rfloor=g,$$
فإن مساهمة هذا القطاع كله تساوي
$$q(g)\sum_{d=a}^{b}\bigl(A(d)-A(d-1)\bigr)=q(g)\bigl(A(b)-A(a-1)\bigr).$$
ولهذا لا تمرّ التطبيقات على كل \(d\) على حدة، بل تتعامل مع كتل لها نفس قيمة القسمة الصحيحة. وعدد هذه القيم المختلفة يقارب \(2\sqrt{n}\) فقط.
في النهاية تُرجع التطبيقات
$$F(N)=4z+2.$$
وهذا يعني أن \(z\) يحسب أولاً قطاع تماثل مختزلاً واحداً، ثم يُعاد بناء العدد الكامل عبر عامل \(4\)، بينما تضيف \(+2\) حالتين تماثليتين خاصتين تُعالجان على نحو منفصل.
عندما \(N=10\)، يكون
$$n=3\cdot 10+6=36.$$
أصغر نقطة في الشريط هي \((1,1)\)، وتدخل عندما
$$18\cdot 1+10\cdot 1=28\le g.$$
ولذلك فإن \(q(g)=0\) لكل \(g<28\). وإذا كان \(d\ge 2\)، فإن \(\lfloor 36/d\rfloor\le 18\)، فتختفي كل هذه الحدود. يبقى فقط \(d=1\):
$$q(36)=1,$$
لأن \((1,1)\) يحقق \(28\le 36<48\). كذلك لدينا \(A(1)-A(0)=\mu(1)=1\). إذن
$$z=1,$$
ويصبح الجواب النهائي
$$F(10)=4\cdot 1+2=6,$$
وهو نفس مقدار التحقق الموجود في التطبيقات.
تسير تطبيقات C++ وPython وJava على الخطة نفسها. أولاً تُحسب القيمة \(n=3N+6\). ثم تُخزَّن قيم دالة Mertens \(M(x)\) في ذاكرة مؤقتة، لأن السابقة المحوّلة \(A(x)\) تطلب كثيراً القيم من الشكل \(\lfloor x/3^j\rfloor\)، وهذه القيم تتكرر بشكل كبير.
في الجزء الهندسي، تحسب الشيفرة \(q(g)\) على أنها فرق بين عدّادين عوديين لنقاط الشبكة. كل عدّاد يختزل الزوج \((a,b)\) بخطوة إقليدية، ويضيف مساهمة الكتل المثلثية الكاملة، ثم يتوقف عندما تصبح المنطقة المتبقية فارغة أو تصل إلى حالة أساسية متماثلة. وبما أن المعاملات ثابتة، فهذه المرحلة صغيرة الكلفة.
أما الجمع النهائي فلا يُنفذ حدّاً حدّاً على كل القواسم. بدلاً من ذلك، تمرّ الشيفرة على الكتل التي تكون فيها \(\lfloor n/d\rfloor\) ثابتة: حلقة أولى للأعداد الصغيرة، وحلقة مكملة للفترات الكبيرة عبر حدود المقاطع. في كل كتلة يُضرب فرق سابقات \(A\) في قيمة واحدة من \(q(g)\). وما إن تصبح \(q(g)=0\)، يصبح من المعروف أن بقية الكتل عديمة الأثر، فتتوقف العملية مبكراً.
بفضل تجميع القيم حسب القسمة الصحيحة، فإن الحلقة الخارجية تزور فقط \(O(\sqrt{n})\) كتل بدلاً من جميع القواسم حتى \(n\). وكل حساب للشريط يعتمد على هبوط إقليدي بمعاملات ثابتة، ولذلك تكون كلفته شبه ثابتة في هذه المسألة. أما الجزء المسيطر فهو تقييم سابقة Mertens المذكرة على الوسائط المختلفة الناتجة من الكتل ومن القسمة المتكررة على \(3\).
لذلك فالبنية الظاهرة للخوارزمية دون خطية بوضوح بالنسبة إلى \(n\)، وتبقى الذاكرة محكومة أساساً بحجم ذاكرة Mertens المؤقتة. وهذا أصغر بكثير من أي محاكاة مباشرة للمسارات أو تعداد ساذج لجميع الاتجاهات المحتملة على الشبكة.