In the equilateral-triangle mirror system of Problem 202, the task is to count how many admissible laser directions leave through vertex \(C\) after exactly \(R=12017639147\) reflections. The important point is that the implementations do not simulate reflections one by one; they replace the geometric path count by a much smaller arithmetic counting problem.
The key reduction is to introduce
$$n=\frac{R+3}{2}.$$
Once that number is known, every valid trajectory is encoded by an integer \(k\) with \(1 \le k \lt n\), and the answer becomes a count of those integers satisfying two precise conditions: one congruence condition picks out the correct exit corner, and one coprimality condition rules out trajectories that would hit a corner too early.
The arithmetic used by the C++, Python, and Java implementations comes from the standard unfolding of mirror reflections in an equilateral triangle. After unfolding, a zig-zag laser path becomes a straight segment in a triangular lattice, so the geometric question turns into a lattice-point visibility question.
Reflect the triangle across the side hit by the beam after each bounce. In the unfolded picture, the beam no longer reflects; instead it travels in a straight line across copies of the original triangle. Endpoints that correspond to exiting through a vertex lie on a specific lattice row, and the reduction used by the implementations labels that row by
$$R=2n-3 \qquad\Longleftrightarrow\qquad n=\frac{R+3}{2}.$$
Using oblique coordinates adapted to the triangular tiling, candidate endpoints on that row can be indexed by a single integer \(k\), with coordinates proportional to \((k,n-k)\) and range
$$1 \le k \lt n.$$
So the geometric problem has already been compressed to a finite list of possible straight-line directions.
As one moves along the relevant lattice row, the vertex types repeat with period 3. Only one of those three residue classes folds back to the physical exit vertex \(C\). With the indexing convention used in the implementations, the correct class is
$$k \equiv 2 \pmod{3}.$$
This is why the code does not count all \(k\), but only every third candidate. The congruence is not a generic template; it is the specific signature of which unfolded vertices correspond to the correct corner of the original equilateral triangle.
A straight segment to the candidate point indexed by \(k\) is valid only if it reaches that point before touching any earlier lattice vertex. Otherwise the folded beam would arrive at a corner sooner, so it would not realize exactly \(R\) reflections.
The direction vector is proportional to \((k,n-k)\). That vector is primitive exactly when
$$\gcd(k,n-k)=1.$$
Because \(\gcd(k,n-k)=\gcd(k,n)\), the visibility condition is equivalent to
$$\gcd(k,n)=1.$$
Therefore the full counting problem is
$$\#\{\,k:1 \le k \lt n,\ k \equiv 2 \pmod{3},\ \gcd(k,n)=1\,\}.$$
Let \(p_1,p_2,\dots,p_r\) be the distinct prime factors of \(n\). To enforce \(\gcd(k,n)=1\), the implementations apply inclusion-exclusion over divisibility by these primes. For a chosen subset \(S\subseteq\{1,\dots,r\}\), define the squarefree divisor
$$d=\prod_{i\in S} p_i.$$
We count those admissible \(k\) that are also divisible by \(d\). Writing \(k=dt\), the range \(1 \le k \lt n\) becomes
$$1 \le t \le \left\lfloor\frac{n-1}{d}\right\rfloor,$$
and the residue condition becomes
$$dt \equiv 2 \pmod{3}.$$
If \(3 \mid d\), this congruence has no solutions. Otherwise \(d\) is invertible modulo 3, so
$$t \equiv 2d^{-1} \pmod{3}.$$
Since modulo 3 the inverse of 1 is 1 and the inverse of 2 is 2, the code only needs two cases: if \(d \equiv 1 \pmod{3}\), then \(t \equiv 2 \pmod{3}\); if \(d \equiv 2 \pmod{3}\), then \(t \equiv 1 \pmod{3}\).
Now let
$$m_d=\left\lfloor\frac{n-1}{d}\right\rfloor.$$
If the required residue class begins at the first positive value \(f_d\in\{1,2,3\}\), then the number of valid \(t\) is
$$C_d=\begin{cases} 0, & 3 \mid d,\\[4pt] 0, & f_d \gt m_d,\\[4pt] 1+\left\lfloor\frac{m_d-f_d}{3}\right\rfloor, & f_d \le m_d. \end{cases}$$
The final count is
$$A(n)=\sum_{S\subseteq\{1,\dots,r\}} (-1)^{|S|} C_{d(S)}.$$
That formula is exactly what the implementations evaluate.
Take a smaller reflection count \(R=67\). Then
$$n=\frac{67+3}{2}=35.$$
The candidates with the correct exit residue are
$$k \in \{2,5,8,11,14,17,20,23,26,29,32\}.$$
Now enforce \(\gcd(k,35)=1\). Since \(35=5\cdot 7\), we remove candidates divisible by 5 or 7. Among the listed values, the forbidden ones are \(5,14,20\). No candidate is divisible by \(35\), so inclusion-exclusion gives
$$11-2-1+0=8.$$
Hence there are 8 admissible trajectories for \(R=67\). This is the same counting mechanism used for the full input; only the value of \(n\) is much larger.
All three implementations begin by replacing the reflection count with \(n=(R+3)/2\). From that point on, the problem is treated entirely arithmetically. The code then factors \(n\) by trial division and stores only the distinct prime divisors, because inclusion-exclusion only needs to know which primes divide \(k\), not their exponents in \(n\).
The C++ and Java implementations enumerate subsets of the distinct prime divisors recursively, while the Python implementation iterates over bitmasks. Each subset determines one squarefree divisor \(d\). The parity of the subset size determines whether that contribution is added or subtracted in the inclusion-exclusion sum.
For each divisor \(d\), the implementation computes \(m_d=\lfloor(n-1)/d\rfloor\), decides which residue class of \(t\) modulo 3 solves \(dt\equiv 2\pmod{3}\), and counts how many terms of that arithmetic progression lie in \([1,m_d]\). If \(d\) is a multiple of 3, the contribution is immediately zero. After all subsets have been processed, the accumulated inclusion-exclusion total is the answer. One implementation also checks smaller known reflection counts before printing the final result, which confirms that the arithmetic reduction matches the geometry.
If \(n=(R+3)/2\), the factorization step uses trial division up to \(\sqrt{n}\), so its cost is \(O(\sqrt{n})\) in the straightforward implementation used here. After factorization, let \(r\) be the number of distinct prime factors of \(n\). Inclusion-exclusion then visits exactly \(2^r\) subsets.
Each subset contributes only constant-time arithmetic: a few integer divisions, one congruence case split modulo 3, and one add or subtract. Thus the post-factorization cost is \(O(2^r)\), and the memory usage is \(O(r)\). For the actual input, this is tiny compared with any approach that tries to trace reflections directly.
Im gleichseitigen Dreieck aus Spiegeln von Problem 202 soll gezählt werden, wie viele zulässige Laserrichtungen nach genau \(R=12017639147\) Reflexionen durch den Eckpunkt \(C\) austreten. Die Implementierungen simulieren die Reflexionen nicht einzeln, sondern ersetzen die Geometrie durch eine kleine arithmetische Zählaufgabe.
Die zentrale Reduktion lautet
$$n=\frac{R+3}{2}.$$
Danach wird jede gültige Bahn durch eine ganze Zahl \(k\) mit \(1 \le k \lt n\) beschrieben. Gezählt werden genau die \(k\), die zugleich die richtige Restklasse modulo 3 haben und teilerfremd zu \(n\) sind.
Die C++-, Python- und Java-Implementierungen benutzen die übliche Entfaltung eines Spiegelweges im gleichseitigen Dreieck. Nach der Entfaltung wird aus der reflektierten Bahn eine Gerade in einem Dreiecksgitter, und aus der geometrischen Frage wird ein Sichtbarkeitsproblem auf Gitterpunkten.
Man spiegelt das Dreieck nach jedem Aufprall an der getroffenen Seite. In diesem entfalten Bild reflektiert der Strahl nicht mehr, sondern läuft geradlinig durch Kopien des Ausgangsdreiecks. Endpunkte, die einem Austritt durch einen Eckpunkt entsprechen, liegen auf einer bestimmten Gitterzeile, und die Reduktion der Implementierungen parametrisiert diese Zeile durch
$$R=2n-3 \qquad\Longleftrightarrow\qquad n=\frac{R+3}{2}.$$
Mit schiefen Koordinaten des Dreiecksgitters lassen sich die möglichen Endpunkte dieser Zeile durch eine einzelne Zahl \(k\) indizieren; der Richtungsvektor ist proportional zu \((k,n-k)\) und es gilt
$$1 \le k \lt n.$$
Damit ist die Menge möglicher Strahlrichtungen endlich und rein arithmetisch beschrieben.
Entlang der relevanten Gitterzeile wiederholen sich die Typen der Eckpunkte periodisch mit Periode 3. Nur eine dieser drei Restklassen faltet sich auf den gewünschten Austritt durch den physischen Eckpunkt \(C\) zurück. In der von den Implementierungen verwendeten Nummerierung ist das genau die Bedingung
$$k \equiv 2 \pmod{3}.$$
Der modulare Filter ist also direkt an die Geometrie des Problems gekoppelt: Er wählt genau diejenigen entfalten Gitterpunkte aus, die zum richtigen Eckpunkt gehören.
Eine Gerade zum Kandidaten \(k\) ist nur dann zulässig, wenn sie diesen Punkt erreicht, ohne vorher einen anderen Gittereckpunkt zu treffen. Sonst würde die gefaltete Bahn schon früher einen Eckpunkt erreichen und nicht genau \(R\) Reflexionen realisieren.
Der Richtungsvektor ist proportional zu \((k,n-k)\). Er ist genau dann primitiv, wenn
$$\gcd(k,n-k)=1.$$
Wegen \(\gcd(k,n-k)=\gcd(k,n)\) ist das gleichbedeutend mit
$$\gcd(k,n)=1.$$
Somit lautet die endgültige Zählaufgabe
$$\#\{\,k:1 \le k \lt n,\ k \equiv 2 \pmod{3},\ \gcd(k,n)=1\,\}.$$
Seien \(p_1,p_2,\dots,p_r\) die verschiedenen Primfaktoren von \(n\). Um die Bedingung \(\gcd(k,n)=1\) durchzusetzen, verwenden die Implementierungen das Inklusions-Exklusions-Prinzip über die Teilbarkeit durch diese Primzahlen. Für eine Teilmenge \(S\subseteq\{1,\dots,r\}\) setze
$$d=\prod_{i\in S} p_i.$$
Dann zählt man zunächst diejenigen zulässigen \(k\), die zusätzlich durch \(d\) teilbar sind. Mit \(k=dt\) wird aus \(1 \le k \lt n\) die Schranke
$$1 \le t \le \left\lfloor\frac{n-1}{d}\right\rfloor,$$
und aus der Restklassenbedingung folgt
$$dt \equiv 2 \pmod{3}.$$
Ist \(3 \mid d\), gibt es keine Lösung. Andernfalls ist \(d\) modulo 3 invertierbar und damit
$$t \equiv 2d^{-1} \pmod{3}.$$
Mod 3 gibt es nur zwei nichttriviale Fälle: Aus \(d\equiv 1\pmod 3\) folgt \(t\equiv 2\pmod 3\), aus \(d\equiv 2\pmod 3\) folgt \(t\equiv 1\pmod 3\).
Mit
$$m_d=\left\lfloor\frac{n-1}{d}\right\rfloor$$
und dem ersten positiven Wert \(f_d\in\{1,2,3\}\) der geforderten Restklasse erhält man
$$C_d=\begin{cases} 0, & 3 \mid d,\\[4pt] 0, & f_d \gt m_d,\\[4pt] 1+\left\lfloor\frac{m_d-f_d}{3}\right\rfloor, & f_d \le m_d. \end{cases}$$
Die gesuchte Anzahl ist dann
$$A(n)=\sum_{S\subseteq\{1,\dots,r\}} (-1)^{|S|} C_{d(S)}.$$
Genau diese Summe wird in den Implementierungen ausgewertet.
Nehmen wir einen kleineren Reflexionswert \(R=67\). Dann ist
$$n=\frac{67+3}{2}=35.$$
Die Kandidaten mit korrekter Austrittsklasse sind
$$k \in \{2,5,8,11,14,17,20,23,26,29,32\}.$$
Nun muss \(\gcd(k,35)=1\) gelten. Da \(35=5\cdot 7\), entfernen wir die durch 5 oder 7 teilbaren Kandidaten. In der Liste sind das \(5,14,20\). Keiner der Kandidaten ist durch \(35\) teilbar, also liefert Inklusion-Exklusion
$$11-2-1+0=8.$$
Damit gibt es für \(R=67\) genau 8 zulässige Bahnen. Für den eigentlichen Input ist die Logik identisch; nur \(n\) ist größer.
Alle drei Implementierungen berechnen zuerst \(n=(R+3)/2\). Ab diesem Moment wird das Problem rein arithmetisch behandelt. Anschließend wird \(n\) per Probedivision faktorisiert, und gespeichert werden nur die verschiedenen Primteiler, weil Inklusion-Exklusion nur die Teilbarkeit durch eine Primzahl, nicht ihre Potenz in \(n\), benötigt.
Die C++- und Java-Implementierungen erzeugen die Teilmengen der verschiedenen Primteiler rekursiv; die Python-Implementierung verwendet dafür Bitmasken. Jede Teilmenge bestimmt genau einen quadratfreien Teiler \(d\). Ob der Beitrag addiert oder subtrahiert wird, hängt nur von der Parität der Teilmengen-Größe ab.
Für jeden solchen Teiler \(d\) berechnet die Implementierung \(m_d=\lfloor(n-1)/d\rfloor\), bestimmt die passende Restklasse von \(t\) modulo 3 aus der Kongruenz \(dt\equiv 2\pmod 3\) und zählt dann die zugehörige arithmetische Progression in \([1,m_d]\). Ist \(d\) durch 3 teilbar, ist der Beitrag sofort null. Nach der Verarbeitung aller Teilmengen ist die aufsummierte Inklusions-Exklusions-Summe bereits die endgültige Antwort. Eine Implementierung prüft zusätzlich kleinere bekannte Reflexionszahlen, um die Reduktion rechnerisch zu verifizieren.
Für \(n=(R+3)/2\) verwendet die Faktorisierung eine Probedivision bis \(\sqrt{n}\), also in dieser direkten Umsetzung \(O(\sqrt{n})\). Sei danach \(r\) die Anzahl verschiedener Primfaktoren von \(n\). Dann betrachtet die Inklusions-Exklusions-Phase genau \(2^r\) Teilmengen.
Jede Teilmenge erfordert nur konstante Arbeit: einige ganzzahlige Divisionen, einen kleinen Kongruenzfall modulo 3 und eine Addition oder Subtraktion. Damit kostet der Schritt nach der Faktorisierung \(O(2^r)\), und der Speicherbedarf ist \(O(r)\). Für den tatsächlichen Eingabewert ist das verschwindend klein gegenüber jeder direkten Reflexionssimulation.
Problem 202’deki eşkenar üçgen ayna düzeninde, tam olarak \(R=12017639147\) yansımadan sonra \(C\) köşesinden çıkan geçerli lazer doğrultularının sayısı istenir. C++, Python ve Java çözümleri yansımaları tek tek izlemez; bunun yerine geometriyi küçük bir aritmetik sayma problemine indirger.
Bu indirgeme
$$n=\frac{R+3}{2}$$
tanımıyla başlar. Bundan sonra her geçerli yol, \(1 \le k \lt n\) aralığında bir tam sayıyla temsil edilir. Sonuç, hem doğru çıkış sınıfını veren mod 3 koşulunu hem de daha erken bir köşeye çarpmayı engelleyen aralarında asallık koşulunu sağlayan \(k\) değerlerinin sayısıdır.
Uygulamaların kullandığı sayı teorisi, eşkenar üçgendeki ayna yansımalarının standart açılımından gelir. Her çarpışmadan sonra üçgeni vurulan kenara göre yansıtırsak, kırıklı lazer yolu üçgensel kafes üzerinde tek bir doğru parçasına dönüşür. Böylece problem, kafes noktalarının görünürlüğünü saymaya iner.
Her sıçramada üçgeni aynalayınca ışın artık kırılmaz; açılmış düzlemde üçgen kopyaları boyunca dümdüz ilerler. Bir köşeden çıkışa karşılık gelen uç noktalar belli bir kafes satırı üzerindedir ve çözümlerin kullandığı parametreleme bu satırı
$$R=2n-3 \qquad\Longleftrightarrow\qquad n=\frac{R+3}{2}$$
ilişkisiyle numaralandırır. Üçgensel döşemeye uygun eğik koordinatlarda bu satırdaki aday uç noktalar tek bir \(k\) ile temsil edilebilir; yön vektörü \((k,n-k)\) ile orantılıdır ve
$$1 \le k \lt n$$
olur. Böylece geometrik problem sonlu sayıda doğrultudan oluşan aritmetik bir listeye dönüşür.
İlgili kafes satırı boyunca köşe tipleri 3 periyotlu tekrar eder. Bu üç artık sınıfından yalnızca biri katlandığında fiziksel \(C\) köşesine denk gelir. Uygulamalardaki indekslemeyle bu tam olarak
$$k \equiv 2 \pmod{3}$$
koşuludur. Dolayısıyla mod 3 filtresi rastgele bir şablon değildir; açılmış düzlemde doğru köşe türünü seçen problem-özgü bir koşuldur.
\(k\) ile belirlenen doğru parçası, hedef kafes köşesine daha önce başka bir kafes köşesine uğramadan ulaşmalıdır. Aksi halde katlanmış ışın daha erken bir köşeye gelir ve istenen tam \(R\) yansımayı gerçekleştirmez.
Yön vektörü \((k,n-k)\) ile orantılıdır. Bu vektörün primitif olması
$$\gcd(k,n-k)=1$$
ile eşdeğerdir. Ama \(\gcd(k,n-k)=\gcd(k,n)\) olduğundan görünürlük koşulu doğrudan
$$\gcd(k,n)=1$$
şeklini alır. Böylece sayılması gereken nicelik
$$\#\{\,k:1 \le k \lt n,\ k \equiv 2 \pmod{3},\ \gcd(k,n)=1\,\}$$
olur.
\(n\)’in farklı asal çarpanları \(p_1,p_2,\dots,p_r\) olsun. \(\gcd(k,n)=1\) şartını sağlamak için uygulamalar, bu asal çarpanlara bölünebilirlik üzerinden dahil et-hariç tut uygular. \(\{1,\dots,r\}\) kümesinin bir altkümesi \(S\) için karesiz bölen
$$d=\prod_{i\in S} p_i$$
tanımlanır. Önce hem geçerli artık sınıfta olan hem de \(d\)’ye bölünen \(k\) sayılır. \(k=dt\) yazınca sınır
$$1 \le t \le \left\lfloor\frac{n-1}{d}\right\rfloor$$
ve mod koşulu
$$dt \equiv 2 \pmod{3}$$
olur. Eğer \(3 \mid d\) ise çözüm yoktur. Aksi halde \(d\), mod 3’te terslenebilir ve
$$t \equiv 2d^{-1} \pmod{3}$$
elde edilir. Mod 3’te yalnızca iki durum vardır: \(d\equiv 1\pmod 3\) ise \(t\equiv 2\pmod 3\), \(d\equiv 2\pmod 3\) ise \(t\equiv 1\pmod 3\).
Şimdi
$$m_d=\left\lfloor\frac{n-1}{d}\right\rfloor$$
olsun. İstenen artık sınıfın ilk pozitif temsilcisi \(f_d\in\{1,2,3\}\) ise uygun \(t\) sayısı
$$C_d=\begin{cases} 0, & 3 \mid d,\\[4pt] 0, & f_d \gt m_d,\\[4pt] 1+\left\lfloor\frac{m_d-f_d}{3}\right\rfloor, & f_d \le m_d \end{cases}$$
olur. Son cevap
$$A(n)=\sum_{S\subseteq\{1,\dots,r\}} (-1)^{|S|} C_{d(S)}$$
şeklindedir. Kodların hesapladığı nicelik tam olarak budur.
Daha küçük bir örnek olarak \(R=67\) alınsın. O zaman
$$n=\frac{67+3}{2}=35.$$
Doğru çıkış kalıntı sınıfındaki adaylar şunlardır:
$$k \in \{2,5,8,11,14,17,20,23,26,29,32\}.$$
Şimdi \(\gcd(k,35)=1\) şartını uygularız. \(35=5\cdot 7\) olduğundan 5 veya 7’ye bölünen adayları sileriz. Bu listedeki yasaklı değerler \(5,14,20\)’dir. Hiçbiri 35’e bölünmediği için dahil et-hariç tut sonucu
$$11-2-1+0=8$$
olur. Demek ki \(R=67\) için 8 geçerli ışın vardır. Gerçek girişte yapılan işlem de aynıdır; yalnızca \(n\) çok daha büyüktür.
Üç uygulama da önce \(n=(R+3)/2\) hesaplar. Bundan sonra geometri tamamen bırakılır ve işlem saf tam sayı aritmetiği olarak yürür. Ardından \(n\), deneme bölmesiyle asal çarpanlarına ayrılır; yalnızca farklı asal çarpanlar saklanır, çünkü dahil et-hariç tut için kuvvetler değil, yalnızca bir asalın bölüp bölmediği gerekir.
C++ ve Java sürümleri farklı asal çarpanların altkümelerini özyinelemeli olarak gezer; Python sürümü aynı işi bitmask ile yapar. Her altküme bir karesiz \(d\) böleni üretir. Alt küme büyüklüğünün tek ya da çift olması, ilgili katkının çıkarılacağını mı ekleneceğini mi belirler.
Her \(d\) için uygulama \(m_d=\lfloor(n-1)/d\rfloor\) değerini bulur, \(dt\equiv 2\pmod 3\) eşitliğini çözen \(t\) artık sınıfını belirler ve \([1,m_d]\) aralığında bu aritmetik dizinin kaç terimi olduğunu hesaplar. \(d\), 3’ün katıysa katkı hemen sıfır olur. Bütün altkümeler işlendiğinde birikmiş dahil et-hariç tut toplamı doğrudan cevaptır. Uygulamalardan biri ayrıca daha küçük bilinen yansıma sayılarıyla kontrol de yapar.
\(n=(R+3)/2\) için kullanılan asal çarpanlara ayırma, \(\sqrt{n}\)’ye kadar deneme bölmesi yaptığı için bu doğrudan yaklaşımda \(O(\sqrt{n})\) maliyetlidir. Sonra \(n\)’in farklı asal çarpan sayısı \(r\) ise dahil et-hariç tut tam olarak \(2^r\) altküme gezer.
Her altkümenin katkısı sabit zamanda hesaplanır: birkaç tamsayı bölmesi, mod 3’e göre küçük bir durum ayrımı ve bir toplama ya da çıkarma. Bu yüzden çarpanlara ayırmadan sonraki maliyet \(O(2^r)\), bellek kullanımı ise \(O(r)\) olur. Gerçek giriş için bu maliyet, yansımaları doğrudan izleyen her yöntemden çok daha küçüktür.
En el sistema de espejos en forma de triángulo equilátero de Problem 202, hay que contar cuántas direcciones de láser válidas salen por el vértice \(C\) después de exactamente \(R=12017639147\) reflexiones. Las implementaciones en C++, Python y Java no siguen el rayo rebote a rebote; sustituyen la geometría por un conteo aritmético mucho más pequeño.
La reducción central introduce
$$n=\frac{R+3}{2}.$$
A partir de ahí, cada trayectoria válida queda codificada por un entero \(k\) con \(1 \le k \lt n\). El resultado es simplemente el número de esos enteros que satisfacen una condición de congruencia, que selecciona el vértice de salida correcto, y una condición de coprimalidad, que evita trayectorias que llegarían a un vértice antes de tiempo.
La aritmética usada por las implementaciones nace del desplegado estándar de las reflexiones en un triángulo equilátero. En la figura desplegada, una trayectoria quebrada por reflexiones se convierte en un solo segmento recto dentro de una red triangular, de modo que la pregunta geométrica pasa a ser un problema de visibilidad de puntos de la red.
Después de cada choque, se refleja el triángulo respecto del lado alcanzado. En ese plano desplegado el rayo ya no rebota, sino que sigue una línea recta atravesando copias del triángulo original. Los puntos finales que corresponden a salir por un vértice se encuentran sobre una fila concreta de la red, y la reducción usada por las implementaciones etiqueta esa fila mediante
$$R=2n-3 \qquad\Longleftrightarrow\qquad n=\frac{R+3}{2}.$$
Con coordenadas oblicuas adaptadas al mosaico triangular, los puntos candidatos de esa fila se indexan con un único entero \(k\); el vector dirección es proporcional a \((k,n-k)\) y se cumple
$$1 \le k \lt n.$$
Así, el problema geométrico queda reducido a una lista finita de direcciones posibles.
Al recorrer la fila relevante de la red, los tipos de vértice se repiten con periodo 3. Solo una de esas tres clases de residuos se pliega de nuevo sobre el vértice físico \(C\). Con la convención de índices de las implementaciones, esa clase es
$$k \equiv 2 \pmod{3}.$$
Por eso el filtro módulo 3 no es un adorno genérico: identifica exactamente qué vértices del problema desplegado representan la salida correcta.
El segmento hacia el candidato \(k\) solo es válido si llega a ese punto sin atravesar antes otro vértice de la red. Si hubiera un vértice intermedio, el rayo plegado alcanzaría una esquina antes y no correspondería a exactamente \(R\) reflexiones.
El vector dirección es proporcional a \((k,n-k)\). Ese vector es primitivo exactamente cuando
$$\gcd(k,n-k)=1.$$
Como \(\gcd(k,n-k)=\gcd(k,n)\), la condición de visibilidad se escribe simplemente como
$$\gcd(k,n)=1.$$
Por tanto, lo que realmente se cuenta es
$$\#\{\,k:1 \le k \lt n,\ k \equiv 2 \pmod{3},\ \gcd(k,n)=1\,\}.$$
Sean \(p_1,p_2,\dots,p_r\) los factores primos distintos de \(n\). Para imponer \(\gcd(k,n)=1\), las implementaciones aplican inclusión-exclusión sobre la divisibilidad por esos primos. Para un subconjunto \(S\subseteq\{1,\dots,r\}\), se define el divisor libre de cuadrados
$$d=\prod_{i\in S} p_i.$$
Primero se cuentan los \(k\) admisibles que además son divisibles por \(d\). Si escribimos \(k=dt\), la cota \(1 \le k \lt n\) se vuelve
$$1 \le t \le \left\lfloor\frac{n-1}{d}\right\rfloor,$$
y la condición de residuo pasa a ser
$$dt \equiv 2 \pmod{3}.$$
Si \(3 \mid d\), no hay soluciones. En caso contrario, \(d\) es invertible módulo 3 y por tanto
$$t \equiv 2d^{-1} \pmod{3}.$$
Como las únicas clases invertibles módulo 3 son 1 y 2, el código solo distingue dos casos: si \(d\equiv 1\pmod 3\), entonces \(t\equiv 2\pmod 3\); si \(d\equiv 2\pmod 3\), entonces \(t\equiv 1\pmod 3\).
Definiendo
$$m_d=\left\lfloor\frac{n-1}{d}\right\rfloor,$$
y llamando \(f_d\in\{1,2,3\}\) al primer representante positivo de la clase requerida, el número de \(t\) válidos es
$$C_d=\begin{cases} 0, & 3 \mid d,\\[4pt] 0, & f_d \gt m_d,\\[4pt] 1+\left\lfloor\frac{m_d-f_d}{3}\right\rfloor, & f_d \le m_d. \end{cases}$$
El conteo final queda
$$A(n)=\sum_{S\subseteq\{1,\dots,r\}} (-1)^{|S|} C_{d(S)}.$$
Esa es exactamente la suma que calculan las tres implementaciones.
Tomemos un caso más pequeño con \(R=67\). Entonces
$$n=\frac{67+3}{2}=35.$$
Los candidatos con la clase correcta de salida son
$$k \in \{2,5,8,11,14,17,20,23,26,29,32\}.$$
Ahora imponemos \(\gcd(k,35)=1\). Como \(35=5\cdot 7\), eliminamos los candidatos divisibles por 5 o por 7. En la lista aparecen \(5,14,20\). Ninguno es divisible por \(35\), así que la inclusión-exclusión da
$$11-2-1+0=8.$$
Por tanto, para \(R=67\) hay 8 trayectorias válidas. El mecanismo es exactamente el mismo para el valor grande del problema.
Las tres implementaciones empiezan calculando \(n=(R+3)/2\). Desde ese punto el problema se maneja por completo con enteros. Después factoran \(n\) mediante división de prueba y guardan solo los primos distintos, porque inclusión-exclusión solo necesita saber qué primos pueden dividir a \(k\).
Las versiones en C++ y Java recorren de forma recursiva los subconjuntos de primos distintos; la versión en Python hace el mismo recorrido con máscaras de bits. Cada subconjunto produce un divisor libre de cuadrados \(d\). La paridad del número de primos elegidos determina si la contribución correspondiente se suma o se resta.
Para cada \(d\), la implementación calcula \(m_d=\lfloor(n-1)/d\rfloor\), resuelve qué residuo de \(t\) módulo 3 satisface \(dt\equiv 2\pmod 3\) y cuenta cuántos términos de esa progresión quedan dentro de \([1,m_d]\). Si \(d\) es múltiplo de 3, la contribución vale cero inmediatamente. Tras procesar todos los subconjuntos, la suma de inclusión-exclusión acumulada ya es la respuesta. Una de las implementaciones también verifica algunos casos pequeños conocidos antes de imprimir el resultado final.
Si \(n=(R+3)/2\), la factorización usada aquí prueba divisores hasta \(\sqrt{n}\), de modo que cuesta \(O(\sqrt{n})\) en esta implementación directa. Después de factorizar, si \(r\) es el número de factores primos distintos de \(n\), la fase de inclusión-exclusión visita exactamente \(2^r\) subconjuntos.
Cada subconjunto requiere solo trabajo constante: unas pocas divisiones enteras, una decisión pequeña módulo 3 y una suma o resta. Por eso el costo tras la factorización es \(O(2^r)\), y la memoria es \(O(r)\). Para la entrada real, eso es diminuto comparado con cualquier enfoque que intente seguir las reflexiones una por una.
在 Problem 202 的等边三角形镜面系统中，需要计算有多少条合法的激光方向能够在恰好 \(R=12017639147\) 次反射之后从顶点 \(C\) 射出。C++、Python 和 Java 版本都没有按反射顺序去模拟整条光路，而是把几何问题压缩成了一个很小的整数计数问题。
这个压缩从
$$n=\frac{R+3}{2}$$
开始。得到 \(n\) 以后，每一条合法轨迹都对应一个满足 \(1 \le k \lt n\) 的整数。最终答案就是满足两条条件的这些整数个数：第一条是模 3 的同余条件，用来挑出真正会折回到目标出口顶点的候选点；第二条是互素条件，用来排除那些会更早撞到某个顶点的方向。
三个实现所依赖的数论结构，来自等边三角形镜面反射的标准“展开”方法。把每次碰撞后的三角形沿被撞到的边翻折出去以后，原来不断反射的折线路径会变成三角形铺砌中的一条直线。因此，原问题不再是“追踪每一次反射”，而是“数一数哪些晶格顶点可以被一条原始方向的直线第一次看到”。
每次光线撞到边时，都把三角形沿该边镜像到外侧。这样在展开后的平面里，光线不再折返，而是穿过一份又一份三角形副本，沿直线前进。与“从某个顶点射出”相对应的终点，都落在三角晶格中的某一条固定行上，而实现采用的编号把这条行写成
$$R=2n-3 \qquad\Longleftrightarrow\qquad n=\frac{R+3}{2}.$$
在适合三角铺砌的斜坐标中，这一行上的候选终点可以用单个整数 \(k\) 来编号，其方向向量与 \((k,n-k)\) 成正比，并满足
$$1 \le k \lt n.$$
到这里为止，几何问题已经被压缩成一个有限的候选方向集合。
沿着这条相关的晶格行移动时，顶点的“类型”会以周期 3 重复。只有其中一种类型在折回原始三角形时会对应到题目要求的出口顶点 \(C\)。按照实现使用的编号约定，这个条件正好是
$$k \equiv 2 \pmod{3}.$$
这说明模 3 条件并不是随便套上的模板，而是展开几何里“哪个晶格顶点折回到哪个物理顶点”这一结构的直接结果。代码先筛掉另外两类 \(k\)，只保留真正会通向 \(C\) 的候选方向。
即使某个候选点属于正确的顶点类型，它也不一定合法。因为如果从起点到这个候选点的直线在中途先经过了别的晶格顶点，那么折回原三角形以后，光线就会更早抵达某个角点，而不是在恰好 \(R\) 次反射后才到达目标。
对应的方向向量与 \((k,n-k)\) 成正比。这个向量是原始向量，也就是中途不会先穿过别的晶格顶点，当且仅当
$$\gcd(k,n-k)=1.$$
而
$$\gcd(k,n-k)=\gcd(k,n),$$
所以可见性条件可以直接改写成
$$\gcd(k,n)=1.$$
于是整个问题最终化为
$$\#\{\,k:1 \le k \lt n,\ k \equiv 2 \pmod{3},\ \gcd(k,n)=1\,\}.$$
这正是三个实现真正计算的对象。
设 \(p_1,p_2,\dots,p_r\) 是 \(n\) 的所有不同素因子。为了强制满足 \(\gcd(k,n)=1\)，实现对“是否被这些素因子整除”做容斥。对任意子集 \(S\subseteq\{1,\dots,r\}\)，定义对应的平方自由因子
$$d=\prod_{i\in S} p_i.$$
现在先数那些既满足正确模 3 条件、又能被 \(d\) 整除的 \(k\)。令 \(k=dt\)，则范围条件变成
$$1 \le t \le \left\lfloor\frac{n-1}{d}\right\rfloor,$$
同余条件变成
$$dt \equiv 2 \pmod{3}.$$
如果 \(3 \mid d\)，这个同余式无解。否则 \(d\) 在模 3 下可逆，因此
$$t \equiv 2d^{-1} \pmod{3}.$$
由于模 3 中只有 1 和 2 两个非零可逆类，实现只需要区分两种情况：当 \(d\equiv 1\pmod 3\) 时，\(t\equiv 2\pmod 3\)；当 \(d\equiv 2\pmod 3\) 时，\(t\equiv 1\pmod 3\)。
记
$$m_d=\left\lfloor\frac{n-1}{d}\right\rfloor,$$
再把所需剩余类的最小正代表记作 \(f_d\in\{1,2,3\}\)，则合法 \(t\) 的个数就是
$$C_d=\begin{cases} 0, & 3 \mid d,\\[4pt] 0, & f_d \gt m_d,\\[4pt] 1+\left\lfloor\frac{m_d-f_d}{3}\right\rfloor, & f_d \le m_d. \end{cases}$$
于是最终计数可写成
$$A(n)=\sum_{S\subseteq\{1,\dots,r\}} (-1)^{|S|} C_{d(S)}.$$
三个实现无一例外都在求这一个公式，只是遍历子集的方式略有不同。
为了看清这个过程，考虑较小的 \(R=67\)。这时
$$n=\frac{67+3}{2}=35.$$
先按正确的出口类型筛选，得到
$$k \in \{2,5,8,11,14,17,20,23,26,29,32\}.$$
接下来要求 \(\gcd(k,35)=1\)。因为 \(35=5\cdot 7\)，所以要删去能被 5 或 7 整除的候选值。上面这串数里被删掉的是 \(5,14,20\)。没有任何一个候选值能被 \(35\) 整除，因此容斥给出
$$11-2-1+0=8.$$
也就是说，当 \(R=67\) 时一共有 8 条合法轨迹。大输入的思路完全相同，只是 \(n\) 变得更大。
三个实现都会先把反射次数改写成 \(n=(R+3)/2\)。从这一步起，代码就不再处理几何对象，而只处理整数。接着通过试除法分解 \(n\)，并只保留不同的素因子，因为容斥只关心“某个素数是否整除候选值”，并不关心该素数在 \(n\) 中出现了多少次。
C++ 和 Java 版本使用递归遍历素因子子集；Python 版本使用位掩码遍历同样的子集空间。每一个子集都会对应一个平方自由因子 \(d\)。子集大小的奇偶性决定该项在容斥和中是加还是减。
对每个 \(d\)，实现都会先算出 \(m_d=\lfloor(n-1)/d\rfloor\)，再根据 \(dt\equiv 2\pmod 3\) 确定 \(t\) 应当落在哪个模 3 剩余类里，然后统计 \([1,m_d]\) 中该等差数列有多少项。如果 \(d\) 本身是 3 的倍数，贡献立刻为 0。所有子集处理结束后，累加得到的容斥总和就是答案。其中一个实现还会先验证几个较小的已知反射次数，以确认算术化简与几何结论一致。
设 \(n=(R+3)/2\)。这里使用的质因数分解方法是试除到 \(\sqrt{n}\)，因此这一阶段的复杂度是 \(O(\sqrt{n})\)。分解完成后，如果 \(n\) 有 \(r\) 个不同素因子，那么容斥阶段恰好需要遍历 \(2^r\) 个子集。
每个子集的处理都是常数时间：几次整数除法、一个模 3 的分支判断，以及一次加法或减法。因此分解之后的成本是 \(O(2^r)\)，额外空间是 \(O(r)\)。对题目的实际输入而言，这比任何显式追踪反射轨迹的方法都要小得多。
В задаче 202 рассматривается система зеркал в виде равностороннего треугольника. Нужно посчитать, сколько допустимых направлений луча приводят к выходу через вершину \(C\) ровно после \(R=12017639147\) отражений. Реальные реализации на C++, Python и Java не моделируют путь луча шаг за шагом, а заменяют геометрию компактным арифметическим подсчетом.
Основная замена состоит во введении числа
$$n=\frac{R+3}{2}.$$
После этого каждая допустимая траектория кодируется целым числом \(k\) при \(1 \le k \lt n\). Остается посчитать только те \(k\), которые одновременно попадают в правильный класс вычетов по модулю 3 и взаимно просты с \(n\).
Числовая схема, используемая реализациями, возникает из стандартного разворачивания отражений в равностороннем треугольнике. После разворачивания ломаная траектория луча превращается в прямой отрезок внутри треугольной решетки, а геометрическая задача переходит в задачу видимости решеточных вершин.
После каждого удара отражаем сам треугольник относительно соответствующей стороны. В развернутой картине луч уже не отражается, а идет по прямой через последовательность копий исходного треугольника. Конечные точки, соответствующие выходу через вершину, лежат на одной фиксированной строке решетки, и в используемой редукции эта строка параметризуется равенством
$$R=2n-3 \qquad\Longleftrightarrow\qquad n=\frac{R+3}{2}.$$
В косых координатах, естественных для треугольной мозаики, кандидаты на этой строке индексируются одним числом \(k\); направляющий вектор пропорционален \((k,n-k)\), причем
$$1 \le k \lt n.$$
Таким образом, исходная геометрия уже сведена к конечному множеству возможных направлений.
Если двигаться вдоль нужной строки решетки, типы вершин повторяются с периодом 3. Лишь один из трех классов вычетов при сворачивании обратно попадает именно в физическую вершину \(C\). В нумерации, принятой в реализациях, это условие имеет вид
$$k \equiv 2 \pmod{3}.$$
Поэтому фильтр по модулю 3 напрямую связан с геометрией задачи: он выбирает именно те вершины развернутой решетки, которые соответствуют правильному выходу.
Даже если кандидат \(k\) имеет правильный тип вершины, он допустим только тогда, когда отрезок до него не проходит через более раннюю вершину решетки. Иначе в свернутой картине луч пришел бы в угол раньше и не реализовал бы ровно \(R\) отражений.
Направляющий вектор пропорционален \((k,n-k)\). Он примитивен тогда и только тогда, когда
$$\gcd(k,n-k)=1.$$
Но \(\gcd(k,n-k)=\gcd(k,n)\), поэтому условие переписывается как
$$\gcd(k,n)=1.$$
В итоге нужно вычислить
$$\#\{\,k:1 \le k \lt n,\ k \equiv 2 \pmod{3},\ \gcd(k,n)=1\,\}.$$
Пусть \(p_1,p_2,\dots,p_r\) — различные простые делители числа \(n\). Чтобы наложить условие \(\gcd(k,n)=1\), реализации перебирают делимость на эти простые числа по принципу включения-исключения. Для подмножества \(S\subseteq\{1,\dots,r\}\) введем квадратсвободный делитель
$$d=\prod_{i\in S} p_i.$$
Сначала считаются те допустимые \(k\), которые дополнительно делятся на \(d\). Если положить \(k=dt\), то ограничение превращается в
$$1 \le t \le \left\lfloor\frac{n-1}{d}\right\rfloor,$$
а условие на класс вычетов становится
$$dt \equiv 2 \pmod{3}.$$
Если \(3 \mid d\), решений нет. Иначе \(d\) обратим по модулю 3 и получается
$$t \equiv 2d^{-1} \pmod{3}.$$
Так как по модулю 3 ненулевые классы — это только 1 и 2, код различает всего два случая: при \(d\equiv 1\pmod 3\) нужно \(t\equiv 2\pmod 3\), а при \(d\equiv 2\pmod 3\) нужно \(t\equiv 1\pmod 3\).
Обозначим
$$m_d=\left\lfloor\frac{n-1}{d}\right\rfloor,$$
и пусть \(f_d\in\{1,2,3\}\) — первый положительный представитель нужного класса. Тогда число подходящих \(t\) равно
$$C_d=\begin{cases} 0, & 3 \mid d,\\[4pt] 0, & f_d \gt m_d,\\[4pt] 1+\left\lfloor\frac{m_d-f_d}{3}\right\rfloor, & f_d \le m_d. \end{cases}$$
Окончательный ответ имеет вид
$$A(n)=\sum_{S\subseteq\{1,\dots,r\}} (-1)^{|S|} C_{d(S)}.$$
Именно эту сумму и вычисляют все три реализации.
Рассмотрим более маленький пример \(R=67\). Тогда
$$n=\frac{67+3}{2}=35.$$
Кандидаты с правильным выходным классом таковы:
$$k \in \{2,5,8,11,14,17,20,23,26,29,32\}.$$
Теперь наложим \(\gcd(k,35)=1\). Поскольку \(35=5\cdot 7\), нужно удалить числа, кратные 5 или 7. В приведенном списке это \(5,14,20\). Ни один кандидат не кратен \(35\), поэтому принцип включения-исключения дает
$$11-2-1+0=8.$$
Значит, при \(R=67\) существует 8 допустимых траекторий. Для большого входа работает ровно тот же механизм.
Во всех трех реализациях сначала вычисляется \(n=(R+3)/2\). С этого момента задача обрабатывается исключительно как задача над целыми числами. Затем число \(n\) раскладывается пробным делением на простые множители, причем сохраняются только различные простые делители: для включения-исключения важен сам факт делимости, а не показатель простого множителя.
Версии на C++ и Java перебирают подмножества различных простых делителей рекурсивно, а версия на Python делает то же самое через битовые маски. Каждое подмножество задает один квадратсвободный делитель \(d\). Четность числа выбранных простых делителей определяет, надо ли соответствующий вклад прибавлять или вычитать.
Для каждого делителя \(d\) программа вычисляет \(m_d=\lfloor(n-1)/d\rfloor\), определяет класс вычетов для \(t\) из сравнения \(dt\equiv 2\pmod 3\) и затем считает, сколько членов нужной арифметической прогрессии лежит в отрезке \([1,m_d]\). Если \(d\) кратно 3, вклад сразу равен нулю. После обработки всех подмножеств накопленная сумма включения-исключения и есть ответ. Одна из реализаций дополнительно проверяет несколько маленьких известных случаев перед выводом результата.
Если \(n=(R+3)/2\), то применяемое здесь пробное деление до \(\sqrt{n}\) стоит \(O(\sqrt{n})\). После факторизации пусть \(r\) — число различных простых делителей числа \(n\). Тогда этап включения-исключения проходит по ровно \(2^r\) подмножествам.
Каждое подмножество требует только константного количества операций: нескольких целочисленных делений, выбора остаточного класса по модулю 3 и одного прибавления или вычитания. Поэтому стоимость после факторизации равна \(O(2^r)\), а память — \(O(r)\). Для реального входа это чрезвычайно мало по сравнению с любым методом прямого отслеживания отражений.
في مسألة 202 لدينا نظام مرايا على شكل مثلث متساوي الأضلاع، والمطلوب هو عدّ عدد اتجاهات الليزر الصحيحة التي تخرج عبر الرأس \(C\) بعد عدد دقيق من الانعكاسات يساوي \(R=12017639147\). تطبيقات C++ وPython وJava لا تتبع مسار الشعاع انعكاسًا بعد انعكاس، بل تستبدل هذا الوصف الهندسي بعدٍّ حسابي صغير جدًا.
الاختزال الأساسي يبدأ من العدد
$$n=\frac{R+3}{2}.$$
بعد ذلك تصبح كل مسار صحيح ممثلًا بعدد صحيح \(k\) يحقق \(1 \le k \lt n\). والجواب النهائي هو عدد هذه القيم التي تحقق شرطين معًا: شرطًا معياريًا modulo 3 يحدد الرأس الصحيح عند الخروج، وشرط توافق نسبي مع \(n\) يمنع المسار من المرور برأس آخر قبل الموعد المطلوب.
البنية العددية التي تستخدمها التطبيقات ناتجة عن طريقة الفتح القياسية لمسارات الانعكاس داخل مثلث متساوي الأضلاع. فعندما نعكس المثلث عند كل اصطدام بالضلع، يتحول المسار المتكسر إلى قطعة مستقيمة داخل تبليط مثلثي، وتتحول المسألة من تتبع بصري للهندسة إلى مسألة رؤية نقاط شبكية.
بعد كل ارتداد نعكس المثلث حول الضلع الذي اصطدم به الشعاع. في الصورة المفتوحة لا يعود الشعاع ينعكس، بل يسير مستقيمًا عبر نسخ متتالية من المثلث الأصلي. والنهايات التي تمثل خروجًا عبر رأس تقع على سطر محدد من الشبكة المثلثية، والاختزال المستخدم في التطبيقات يربط هذا السطر بالعلاقة
$$R=2n-3 \qquad\Longleftrightarrow\qquad n=\frac{R+3}{2}.$$
وباستخدام إحداثيات مائلة مناسبة للتبليط المثلثي، يمكن فهرسة نقاط النهاية المرشحة على هذا السطر بعدد واحد \(k\)، ويكون متجه الاتجاه متناسبًا مع \((k,n-k)\)، مع القيد
$$1 \le k \lt n.$$
وهكذا تُضغط المسألة الهندسية إلى مجموعة منتهية من الاتجاهات المرشحة.
إذا تحركنا على طول السطر الشبكي المناسب، فإن أنواع الرؤوس تتكرر بدورية مقدارها 3. ومن بين هذه الفئات الثلاث لا تنطوي إلى الرأس الفيزيائي \(C\) إلا فئة واحدة فقط. ووفق ترقيم التطبيقات فإن هذه الفئة توصف بالشرط
$$k \equiv 2 \pmod{3}.$$
إذن شرط البواقي modulo 3 ليس قالبًا عامًا، بل هو الوصف الدقيق لنوع الرؤوس في الصورة المفتوحة التي تعود بعد الطي إلى رأس الخروج المطلوب.
حتى لو كانت النقطة المرشحة من النوع الصحيح، فإن المسار يكون صالحًا فقط إذا وصل إليها من دون المرور أولًا برأس شبكي وسيط. لأن وجود رأس وسيط يعني أن الشعاع بعد طي الصورة كان سيصل إلى زاوية قبل الوقت المطلوب، وبالتالي لن يحقق بالضبط \(R\) انعكاسات.
متجه الاتجاه متناسب مع \((k,n-k)\)، ويكون هذا المتجه أوليًا بالمعنى الهندسي إذا وفقط إذا تحقق
$$\gcd(k,n-k)=1.$$
وبما أن
$$\gcd(k,n-k)=\gcd(k,n),$$
فإن شرط عدم وجود رأس سابق يتحول مباشرة إلى
$$\gcd(k,n)=1.$$
لذلك يصبح المطلوب في النهاية هو حساب
$$\#\{\,k:1 \le k \lt n,\ k \equiv 2 \pmod{3},\ \gcd(k,n)=1\,\}.$$
لتكن \(p_1,p_2,\dots,p_r\) هي العوامل الأولية المختلفة للعدد \(n\). لفرض الشرط \(\gcd(k,n)=1\)، تطبق التطبيقات مبدأ الشمول والاستبعاد على قابلية القسمة على هذه العوامل الأولية. ولكل مجموعة جزئية \(S\subseteq\{1,\dots,r\}\) نعرّف القاسم الخالي من المربعات
$$d=\prod_{i\in S} p_i.$$
ثم نعد أولًا القيم \(k\) التي تقع في فئة الخروج الصحيحة وتكون في الوقت نفسه مضاعفات لـ \(d\). إذا كتبنا \(k=dt\)، فإن المجال يصبح
$$1 \le t \le \left\lfloor\frac{n-1}{d}\right\rfloor,$$
ويتحول الشرط المعياري إلى
$$dt \equiv 2 \pmod{3}.$$
إذا كان \(3 \mid d\) فلا يوجد حل. أما إذا لم يكن كذلك، فـ \(d\) قابل للعكس modulo 3، وبالتالي
$$t \equiv 2d^{-1} \pmod{3}.$$
ولأن المعكوسات غير الصفرية modulo 3 هي فقط 1 و2، فلا يحتاج الكود إلا إلى حالتين: إذا كان \(d\equiv 1\pmod 3\) فلابد أن يكون \(t\equiv 2\pmod 3\)، وإذا كان \(d\equiv 2\pmod 3\) فلابد أن يكون \(t\equiv 1\pmod 3\).
ولنعرّف
$$m_d=\left\lfloor\frac{n-1}{d}\right\rfloor.$$
إذا كان أول ممثل موجب للفئة المطلوبة هو \(f_d\in\{1,2,3\}\)، فإن عدد قيم \(t\) الموافقة يساوي
$$C_d=\begin{cases} 0, & 3 \mid d,\\[4pt] 0, & f_d \gt m_d,\\[4pt] 1+\left\lfloor\frac{m_d-f_d}{3}\right\rfloor, & f_d \le m_d. \end{cases}$$
ومن ثم يكون الجواب النهائي
$$A(n)=\sum_{S\subseteq\{1,\dots,r\}} (-1)^{|S|} C_{d(S)}.$$
وهذه هي بالضبط الصيغة التي تقيمها التطبيقات الثلاثة.
لنأخذ مثالًا أصغر حيث \(R=67\). عندئذٍ
$$n=\frac{67+3}{2}=35.$$
القيم المرشحة ذات فئة الخروج الصحيحة هي
$$k \in \{2,5,8,11,14,17,20,23,26,29,32\}.$$
الآن نفرض الشرط \(\gcd(k,35)=1\). وبما أن \(35=5\cdot 7\)، فعلينا حذف القيم القابلة للقسمة على 5 أو 7. في هذه القائمة القيم المرفوضة هي \(5,14,20\). ولا توجد أي قيمة مرشحة قابلة للقسمة على \(35\)، لذا يعطي الشمول والاستبعاد
$$11-2-1+0=8.$$
أي إن عدد المسارات الصحيحة عندما \(R=67\) يساوي 8. والطريقة نفسها تُستخدم للقيمة الكبيرة في المسألة الأصلية.
تبدأ جميع التطبيقات بحساب \(n=(R+3)/2\). ومن هذه اللحظة يصبح الحل حسابيًا بحتًا. بعد ذلك يُفكك \(n\) إلى عوامله الأولية باستخدام القسمة التجريبية، ولا تُخزن إلا العوامل الأولية المختلفة، لأن الشمول والاستبعاد يحتاج فقط إلى معرفة أيُّ الأوليات قد تقسم \(k\)، لا إلى أسسها داخل \(n\).
في نسختي C++ وJava يجري تعداد مجموعات العوامل الأولية المختلفة بطريقة عودية، بينما تستخدم نسخة Python أقنعة بتية لتمثيل المجموعات نفسها. كل مجموعة جزئية تحدد قاسمًا خاليًا من المربعات \(d\). وتحدد فردية حجم المجموعة أو زوجيته ما إذا كان الحد الموافق سيُضاف أم سيُطرح.
لكل قاسم \(d\) تحسب الشيفرة \(m_d=\lfloor(n-1)/d\rfloor\)، ثم تحدد فئة البواقي التي يجب أن يقع فيها \(t\) من أجل تحقيق \(dt\equiv 2\pmod 3\)، وبعد ذلك تعدّ عدد حدود تلك المتتالية الحسابية الواقعة داخل \([1,m_d]\). وإذا كان \(d\) من مضاعفات 3 فمساهمته تساوي صفرًا فورًا. بعد إنهاء جميع المجموعات الجزئية يكون مجموع الشمول والاستبعاد المتراكم هو الجواب النهائي. كما أن إحدى التطبيقات تتحقق أيضًا من بعض القيم الصغيرة المعروفة قبل طباعة الناتج.
إذا كان \(n=(R+3)/2\)، فإن تحليل \(n\) هنا يجري بالقسمة التجريبية حتى \(\sqrt{n}\)، ولذلك تكلفته \(O(\sqrt{n})\) في هذه الصياغة المباشرة. وبعد التحليل، إذا كان عدد العوامل الأولية المختلفة هو \(r\)، فإن مرحلة الشمول والاستبعاد تمر على \(2^r\) مجموعة جزئية بالضبط.
كل مجموعة جزئية تحتاج إلى عمل ثابت فقط: بضع قسَمات صحيحة، وفرع صغير modulo 3، ثم عملية جمع أو طرح واحدة. لذلك فالتكلفة بعد التحليل هي \(O(2^r)\)، واستهلاك الذاكرة هو \(O(r)\). وبالنسبة إلى دخل المسألة الحقيقي، فهذا أصغر بكثير من أي طريقة تحاول تتبع الانعكاسات مباشرة.