The puzzle is governed by three step sizes
$$s_0=\frac{1}{a},\qquad s_1=\frac{1}{b},\qquad s_2=\frac{1}{\sqrt{c}},$$
applied cyclically to a point on the unit interval. For each triple \(9 \le a < b < c\), we seek the least positive number of steps \(T(a,b,c)\) for which the full three-phase system is synchronized again. The overall quantity is
$$\sum_{9\le a < b < c \le n} T(a,b,c).$$
A brute-force simulation is hopeless because the synchronization time can be very large, so the solution converts the continuous process into a finite automaton and then solves the resulting congruence conditions exactly.
The key observation is that each phase uses the same piecewise map with a different step size. For \(0<s<1\), define
$$\Phi_s(x)=\begin{cases} 1-x, & 0\le x < s,\\ x-s, & s\le x < 1. \end{cases}$$
The dynamics applies \(\Phi_{s_0}\), then \(\Phi_{s_1}\), then \(\Phi_{s_2}\), and repeats this three-phase cycle forever. Each branch either reflects the interval orientation or preserves it, so every transition naturally carries one binary flip bit.
In each phase, the relevant breakpoints are the discontinuity \(s_\phi\), the endpoint \(0\), and all of their backward images under earlier phases. Once those breakpoints are known, every open interval between consecutive breakpoints behaves uniformly: every point in that interval goes to the same next interval and experiences the same orientation change.
Therefore one state is simply
$$\text{state}=(\text{phase},\ \text{interval}).$$
Because every state has exactly one successor, the entire system becomes a directed graph in which every component eventually lies on a cycle. The whole problem is then reduced to analyzing those cycles and determining when their orientation constraints can hold simultaneously.
If \(c=k^2\), then \(s_2=1/k\) is rational. In that case all breakpoints lie on the common grid with denominator
$$D=\operatorname{lcm}(a,b,k).$$
Write
$$S_0=\frac{D}{a},\qquad S_1=\frac{D}{b},\qquad S_2=\frac{D}{k}.$$
Each phase is partitioned into the \(D\) cells
$$I_j=\left[\frac{j}{D},\frac{j+1}{D}\right),\qquad 0\le j<D.$$
For phase \(\phi\), the map is explicit:
$$I_j\longmapsto\begin{cases} I_{D-1-j}, & j<S_\phi,\\ I_{j-S_\phi}, & j\ge S_\phi. \end{cases}$$
The first branch is a reflection and contributes flip bit \(1\); the second branch is a translation and contributes flip bit \(0\). Thus the square case produces a finite automaton with exactly \(3D\) states.
If \(c\) is not a square, then \(1/\sqrt{c}\) is irrational, so a simple rational grid no longer exists. The implementations instead represent every breakpoint exactly in the form
$$x=\frac{P}{ab}+\frac{Q\sqrt{c}}{c}\pmod{1},\qquad P,Q\in\mathbb{Z}.$$
This works because the three step sizes are
$$\frac{1}{a}=\frac{b}{ab},\qquad \frac{1}{b}=\frac{a}{ab},\qquad \frac{1}{\sqrt{c}}=\frac{\sqrt{c}}{c},$$
so every backward image remains in the same lattice generated by \(1/(ab)\) and \(\sqrt{c}/c\).
For each phase we begin with the seed set \(\{0,s_\phi\}\). If \(y\) is already a breakpoint in phase \(\phi\), then its preimages under the previous phase are
$$x=y+s_{\phi-1}\qquad\text{when } y<1-s_{\phi-1},$$
and
$$x=1-y\qquad\text{when } y>1-s_{\phi-1}.$$
Repeating this predecessor closure until no new points appear yields three finite breakpoint sets. They are then sorted exactly by comparing the sign of expressions of the form
$$A+B\sqrt{c},$$
which avoids floating-point ambiguity. Adjacent breakpoints again define intervals, so the non-square branch also becomes a finite deterministic automaton.
Because phases advance \(0\to1\to2\to0\), every directed cycle has length \(3m\) for some \(m\). Along that cycle the automaton records a binary word
$$f_0,f_1,\dots,f_{3m-1},\qquad f_i\in\{0,1\},$$
where \(f_i=1\) means that step used the reflecting branch. Group the bits by phase:
$$\alpha_i=f_{3i},\qquad \beta_i=f_{3i+1},\qquad \gamma_i=f_{3i+2}\qquad(0\le i<m).$$
The orientation change over one full three-step round is
$$w_i=\alpha_i\oplus\beta_i\oplus\gamma_i.$$
If the total parity of the whole cycle is even, returning to the same place also returns to the same orientation after one geometric lap. If it is odd, one extra lap is needed to restore orientation. Therefore the natural modulus attached to that cycle is
$$P=\begin{cases} 3m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=0,\\ 6m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=1. \end{cases}$$
Suppose the desired synchronization time has the form
$$N=3q+R,\qquad R\in\{0,1,2\}.$$
The partial phase offset \(R\) contributes its own correction word. For each \(i\), define
$$t_i^{(0)}=0,\qquad t_i^{(1)}=\alpha_i,\qquad t_i^{(2)}=\alpha_i\oplus\beta_i.$$
Then the corrected round word is
$$e_i^{(R)}=w_i\oplus t_i^{(R)}\oplus t_{i+1}^{(R)}.$$
A residue class is valid exactly when this corrected word is a cyclic rotation of \(w\) and the initial orientation parity is also consistent. The implementations find all such rotations with Knuth-Morris-Pratt on the doubled word \(w\,w\), then verify the start-parity condition with prefix xors. The result of one cycle is therefore a finite set
$$N\equiv r \pmod{P},\qquad r\in R_{\text{cycle}}.$$
Different connected components of the state graph impose independent congruence conditions on the same unknown \(N\). If one cycle allows residues \(R_1\) modulo \(P_1\) and another allows residues \(R_2\) modulo \(P_2\), then every compatible pair is merged by the generalized Chinese Remainder Theorem.
After processing all cycles, the surviving residue classes describe every synchronized time. The least positive one is exactly \(T(a,b,c)\).
Here \(c=16=4^2\), so the rational-grid branch applies. We obtain
$$D=\operatorname{lcm}(10,14,4)=140,$$
hence
$$S_0=\frac{140}{10}=14,\qquad S_1=\frac{140}{14}=10,\qquad S_2=\frac{140}{4}=35.$$
So each phase has \(140\) cells and the automaton has \(420\) states in total. In phase \(0\), cells \(0\) through \(13\) reflect to cells \(139\) down to \(126\), while cells \(14\) through \(139\) translate to cells \(0\) through \(125\). The same rule is repeated with thresholds \(10\) and \(35\) in the next two phases.
Decomposing that automaton into directed cycles, extracting the admissible congruence classes from each cycle, and merging them with CRT yields the least positive synchronization time
$$T(10,14,16)=506,$$
which matches the checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same mathematical plan. First they distinguish the square and non-square cases. In the square case they build the \(3D\)-state automaton directly from explicit cell formulas. In the non-square case they build exact breakpoint sets in quadratic-field coordinates, sort them with exact comparisons, and then form the corresponding interval automaton.
Next the implementation walks through every connected component, extracts its directed cycle, records the flip word, and converts that word into allowed residue classes by a combination of prefix-xor bookkeeping, rotation matching, and generalized CRT. The smallest positive residue surviving all cycle merges is the answer for that triple. Finally the outer loops sum these values for all \(9\le a<b<c\le n\), using arbitrary-precision integer arithmetic for the final total. The Python implementation delegates the heavy numerical work to the same compiled core, so all three languages share the same underlying algorithm.
For one triple, let \(m\) be the number of intervals per phase after discretization. The resulting automaton has \(3m\) states. Building the square-case automaton is \(O(m)\). In the non-square case, predecessor closure and exact sorting dominate, giving roughly \(O(m \log m)\) work once the breakpoint set is known. Cycle extraction is linear in the number of states, and the word analysis for a cycle of length \(\ell\) is \(O(\ell)\) because both prefix-xor processing and KMP are linear.
The CRT stage depends on how many residue classes survive after each merge; in practice those sets stay modest, so the dominant cost is constructing and scanning the automaton. Memory usage is \(O(m)\) per triple. The overall computation for the final sum is the sum of these costs over all \(\binom{n-8}{3}\) triples, and the outer parameter loop is parallelized in the compiled implementations.
Das Rätsel wird durch drei Schrittweiten bestimmt:
$$s_0=\frac{1}{a},\qquad s_1=\frac{1}{b},\qquad s_2=\frac{1}{\sqrt{c}}.$$
Diese werden zyklisch auf einen Punkt im Einheitsintervall angewendet. Für jedes Tripel \(9 \le a < b < c\) suchen wir die kleinste positive Schrittzahl \(T(a,b,c)\), nach der das vollständige Dreiphasensystem wieder synchron ist. Gesucht ist also
$$\sum_{9\le a < b < c \le n} T(a,b,c).$$
Eine direkte Simulation ist aussichtslos, weil die Synchronisationszeiten sehr groß werden können. Deshalb überführt die Lösung die stetige Dynamik in einen endlichen Automaten und löst die entstehenden Kongruenzbedingungen exakt.
Jede Phase benutzt dieselbe stückweise definierte Abbildung mit einer anderen Schrittweite. Für \(0<s<1\) setzen wir
$$\Phi_s(x)=\begin{cases} 1-x, & 0\le x < s,\\ x-s, & s\le x < 1. \end{cases}$$
Die Dynamik wendet \(\Phi_{s_0}\), dann \(\Phi_{s_1}\), dann \(\Phi_{s_2}\) an und wiederholt diesen Dreierzyklus. Jeder Schritt erhält oder spiegelt die Orientierung; deshalb trägt jeder Übergang natürlich ein Flip-Bit.
In jeder Phase sind die relevanten Trennpunkte die Unstetigkeitsstelle \(s_\phi\), der Randpunkt \(0\) und alle Rückwärtsbilder dieser Punkte unter früheren Phasen. Sind diese Trennpunkte bekannt, so verhält sich jedes offene Intervall zwischen zwei benachbarten Punkten einheitlich: Jeder Punkt darin geht in dasselbe Folgeintervall über und erfährt dieselbe Orientierungsänderung.
Ein Zustand ist daher einfach
$$\text{Zustand}=(\text{Phase},\ \text{Intervall}).$$
Jeder Zustand besitzt genau einen Nachfolger. Damit entsteht ein gerichteter Graph, dessen Zusammenhangskomponenten letztlich auf Zyklen enden. Das Problem reduziert sich also auf die Analyse dieser Zyklen und ihrer Paritätsbedingungen.
Ist \(c=k^2\), dann ist \(s_2=1/k\) rational. Alle Trennpunkte liegen dann auf dem gemeinsamen Gitter mit Nenner
$$D=\operatorname{lcm}(a,b,k).$$
Schreibe
$$S_0=\frac{D}{a},\qquad S_1=\frac{D}{b},\qquad S_2=\frac{D}{k}.$$
Jede Phase zerfällt in die \(D\) Zellen
$$I_j=\left[\frac{j}{D},\frac{j+1}{D}\right),\qquad 0\le j<D.$$
Für Phase \(\phi\) gilt dann explizit
$$I_j\longmapsto\begin{cases} I_{D-1-j}, & j<S_\phi,\\ I_{j-S_\phi}, & j\ge S_\phi. \end{cases}$$
Der erste Zweig ist eine Spiegelung und liefert das Flip-Bit \(1\), der zweite ist eine Translation mit Flip-Bit \(0\). Im Quadratfall erhalten wir also einen endlichen Automaten mit genau \(3D\) Zuständen.
Ist \(c\) kein Quadrat, dann ist \(1/\sqrt{c}\) irrational, also gibt es kein rein rationales Gitter. Stattdessen repräsentieren die Implementierungen jeden Trennpunkt exakt in der Form
$$x=\frac{P}{ab}+\frac{Q\sqrt{c}}{c}\pmod{1},\qquad P,Q\in\mathbb{Z}.$$
Das funktioniert, weil die drei Schrittweiten
$$\frac{1}{a}=\frac{b}{ab},\qquad \frac{1}{b}=\frac{a}{ab},\qquad \frac{1}{\sqrt{c}}=\frac{\sqrt{c}}{c}$$
sind und damit jedes Rückwärtsbild im selben von \(1/(ab)\) und \(\sqrt{c}/c\) erzeugten Gitter bleibt.
Für jede Phase beginnt man mit der Startmenge \(\{0,s_\phi\}\). Ist \(y\) bereits ein Trennpunkt in Phase \(\phi\), dann sind seine Urbilder unter der vorherigen Phase
$$x=y+s_{\phi-1}\qquad\text{falls } y<1-s_{\phi-1},$$
und
$$x=1-y\qquad\text{falls } y>1-s_{\phi-1}.$$
Wiederholt man diesen Urbildabschluss, bis keine neuen Punkte mehr entstehen, erhält man drei endliche Mengen von Trennpunkten. Diese werden exakt sortiert, indem man das Vorzeichen von Ausdrücken der Form
$$A+B\sqrt{c}$$
bestimmt und damit Fließkommafehler vermeidet. Benachbarte Trennpunkte definieren wieder Intervalle, also auch hier einen endlichen deterministischen Automaten.
Da die Phasen \(0\to1\to2\to0\) durchlaufen, hat jeder gerichtete Zyklus Länge \(3m\) für ein geeignetes \(m\). Entlang dieses Zyklus entsteht ein binäres Wort
$$f_0,f_1,\dots,f_{3m-1},\qquad f_i\in\{0,1\},$$
wobei \(f_i=1\) genau dann gilt, wenn in diesem Schritt der spiegelnde Zweig benutzt wurde. Nach Phasen gruppiert:
$$\alpha_i=f_{3i},\qquad \beta_i=f_{3i+1},\qquad \gamma_i=f_{3i+2}\qquad(0\le i<m).$$
Die Orientierungsänderung einer ganzen Dreierunde ist
$$w_i=\alpha_i\oplus\beta_i\oplus\gamma_i.$$
Ist die Gesamtparität des Zyklus gerade, dann genügt eine geometrische Runde. Ist sie ungerade, muss man eine weitere Runde anhängen, um auch die Orientierung zurückzusetzen. Der zum Zyklus gehörige Modul lautet daher
$$P=\begin{cases} 3m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=0,\\ 6m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=1. \end{cases}$$
Hat die gesuchte Synchronisationszeit die Form
$$N=3q+R,\qquad R\in\{0,1,2\},$$
dann steuert der partielle Phasenversatz \(R\) ein Korrekturwort bei. Definiere für jedes \(i\)
$$t_i^{(0)}=0,\qquad t_i^{(1)}=\alpha_i,\qquad t_i^{(2)}=\alpha_i\oplus\beta_i.$$
Dann ist das korrigierte Rundenwort
$$e_i^{(R)}=w_i\oplus t_i^{(R)}\oplus t_{i+1}^{(R)}.$$
Eine Restklasse ist genau dann zulässig, wenn dieses korrigierte Wort eine zyklische Rotation von \(w\) ist und zusätzlich die Anfangsparität stimmt. Die Implementierungen finden alle solchen Rotationen mit Knuth-Morris-Pratt auf dem verdoppelten Wort \(w\,w\) und prüfen die Anfangsparität per Präfix-Xor. Ein Zyklus liefert damit eine endliche Menge
$$N\equiv r \pmod{P},\qquad r\in R_{\text{Zyklus}}.$$
Verschiedene Zusammenhangskomponenten des Zustandsgraphen erzeugen unabhängige Kongruenzbedingungen für dasselbe \(N\). Lässt ein Zyklus Restklassen \(R_1\) modulo \(P_1\) zu und ein anderer \(R_2\) modulo \(P_2\), dann wird jedes kompatible Paar mit dem verallgemeinerten chinesischen Restsatz kombiniert.
Nach dem Zusammenführen aller Zyklen beschreiben die verbleibenden Restklassen genau die synchronen Zeiten. Die kleinste positive darunter ist \(T(a,b,c)\).
Hier ist \(c=16=4^2\), also gilt der rationale Gitterfall. Wir erhalten
$$D=\operatorname{lcm}(10,14,4)=140,$$
also
$$S_0=\frac{140}{10}=14,\qquad S_1=\frac{140}{14}=10,\qquad S_2=\frac{140}{4}=35.$$
Jede Phase besitzt somit \(140\) Zellen, insgesamt also \(420\) Zustände. In Phase \(0\) werden die Zellen \(0\) bis \(13\) auf \(139\) bis \(126\) gespiegelt, während die Zellen \(14\) bis \(139\) auf \(0\) bis \(125\) verschoben werden. Dasselbe Muster gilt in den nächsten beiden Phasen mit den Schwellen \(10\) und \(35\).
Zerlegt man diesen Automaten in gerichtete Zyklen, extrahiert aus jedem Zyklus die zulässigen Kongruenzklassen und führt sie per CRT zusammen, so ergibt sich die kleinste positive Synchronisationszeit
$$T(10,14,16)=506,$$
genau der Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen alle demselben mathematischen Plan. Zuerst unterscheiden sie zwischen Quadrat- und Nichtquadratfall von \(c\). Im Quadratfall wird der \(3D\)-Zustandsautomat direkt aus expliziten Zellformeln aufgebaut. Im Nichtquadratfall entstehen exakte Mengen von Trennpunkten in quadratischen Zahlkörperkoordinaten; diese werden exakt sortiert und anschließend zu einem Intervallautomaten verarbeitet.
Danach durchläuft die Implementierung jede Zusammenhangskomponente, liest ihren gerichteten Zyklus aus, speichert das Flip-Wort und erzeugt daraus mittels Präfix-Xor, Rotationssuche und verallgemeinertem CRT die zulässigen Restklassen. Die kleinste positive Restklasse nach allen Zusammenführungen ist der Wert des jeweiligen Tripels. Die äußeren Schleifen summieren diese Werte über alle \(9\le a<b<c\le n\), wobei für die Endsumme Ganzzahlen beliebiger Länge verwendet werden. Die Python-Variante delegiert die rechenintensive Arbeit an denselben kompilierten Kern, sodass alle drei Sprachen denselben Algorithmus nutzen.
Sei \(m\) für ein festes Tripel die Anzahl der Intervalle pro Phase nach der Diskretisierung. Dann besitzt der Automat \(3m\) Zustände. Im Quadratfall kostet der Aufbau \(O(m)\). Im Nichtquadratfall dominieren Urbildabschluss und exakte Sortierung, also ungefähr \(O(m\log m)\), sobald die Punktmenge feststeht. Das Extrahieren der Zyklen ist linear in der Zustandszahl, und die Wortanalyse eines Zyklus der Länge \(\ell\) kostet \(O(\ell)\), weil sowohl Präfix-Xor als auch KMP linear sind.
Die CRT-Phase hängt davon ab, wie viele Restklassen nach jedem Merge übrig bleiben; in der Praxis bleiben diese Mengen klein, sodass der Hauptaufwand im Aufbau und Durchlauf des Automaten liegt. Der Speicherbedarf ist \(O(m)\) pro Tripel. Die Gesamtrechnung für die Endsumme ist die Summe dieser Kosten über alle \(\binom{n-8}{3}\) Tripel; in den kompilierten Implementierungen ist die äußere Parameterschleife parallelisiert.
Bulmaca üç adım uzunluğu ile tanımlanır:
$$s_0=\frac{1}{a},\qquad s_1=\frac{1}{b},\qquad s_2=\frac{1}{\sqrt{c}}.$$
Bu üç dönüşüm birim aralıktaki bir noktaya döngüsel olarak uygulanır. Her \(9 \le a < b < c\) üçlüsü için, tam üç fazlı sistemin yeniden senkron olduğu en küçük pozitif adım sayısı \(T(a,b,c)\) aranır. Toplam hedef değer
$$\sum_{9\le a < b < c \le n} T(a,b,c)$$
olur. Doğrudan benzetim uygulanamaz, çünkü senkronizasyon zamanı çok büyüyebilir. Bu yüzden çözüm sürekli süreci sonlu bir otomata çevirir ve ortaya çıkan modüler kısıtları tam olarak çözer.
Her faz aynı parçalı dönüşümü farklı bir adım uzunluğuyla kullanır. \(0<s<1\) için
$$\Phi_s(x)=\begin{cases} 1-x, & 0\le x < s,\\ x-s, & s\le x < 1 \end{cases}$$
tanımını yapalım. Dinamik sırayla \(\Phi_{s_0}\), \(\Phi_{s_1}\), \(\Phi_{s_2}\) uygular ve bunu tekrarlar. Her adım ya yönü korur ya da ters çevirir; bu yüzden her geçiş doğal olarak bir flip biti taşır.
Her fazdaki kritik kırılma noktaları, süreksizlik noktası \(s_\phi\), sınır noktası \(0\) ve bunların önceki fazlar altındaki tüm geri görüntüleridir. Bu kırılma noktaları bilindiğinde, ardışık iki nokta arasındaki her açık aralık tek tip davranır: o aralıktaki her nokta aynı sonraki aralığa gider ve aynı yön değişimini yaşar.
Dolayısıyla bir durum sadece
$$\text{durum}=(\text{faz},\ \text{aralık})$$
şeklindedir. Her durumun tam bir ardılı vardır. Böylece sistem, her bağlı bileşeni sonunda bir çevrime oturan yönlü bir grafa indirgenir. Problem artık bu çevrimlerin ve parite koşullarının incelenmesine dönüşür.
Eğer \(c=k^2\) ise \(s_2=1/k\) rasyoneldir. Bu durumda tüm kırılma noktaları ortak bir ızgara üzerinde yer alır:
$$D=\operatorname{lcm}(a,b,k).$$
Şunları yazalım:
$$S_0=\frac{D}{a},\qquad S_1=\frac{D}{b},\qquad S_2=\frac{D}{k}.$$
Her faz
$$I_j=\left[\frac{j}{D},\frac{j+1}{D}\right),\qquad 0\le j<D$$
hücrelerine ayrılır. Faz \(\phi\) için geçiş açık biçimde
$$I_j\longmapsto\begin{cases} I_{D-1-j}, & j<S_\phi,\\ I_{j-S_\phi}, & j\ge S_\phi \end{cases}$$
olur. İlk dal yansıma verip flip biti \(1\), ikinci dal kaydırma verip flip biti \(0\) üretir. Böylece kare durumda tam \(3D\) durumlu sonlu bir otomat elde edilir.
\(c\) kare değilse \(1/\sqrt{c}\) irrasyoneldir; dolayısıyla basit bir rasyonel ızgara yetmez. Bunun yerine tüm kırılma noktaları tam olarak
$$x=\frac{P}{ab}+\frac{Q\sqrt{c}}{c}\pmod{1},\qquad P,Q\in\mathbb{Z}$$
şeklinde temsil edilir. Bunun nedeni, üç adım uzunluğunun
$$\frac{1}{a}=\frac{b}{ab},\qquad \frac{1}{b}=\frac{a}{ab},\qquad \frac{1}{\sqrt{c}}=\frac{\sqrt{c}}{c}$$
olması ve her geri görüntünün \(1/(ab)\) ile \(\sqrt{c}/c\) tarafından üretilen aynı kafeste kalmasıdır.
Her faz için başlangıç kümesi \(\{0,s_\phi\}\) alınır. Eğer \(y\), faz \(\phi\) içinde bilinen bir kırılma noktasıysa, önceki faz altındaki geri görüntüler
$$x=y+s_{\phi-1}\qquad\text{eğer } y<1-s_{\phi-1}$$
ve
$$x=1-y\qquad\text{eğer } y>1-s_{\phi-1}$$
şeklindedir. Hiç yeni nokta kalmayana kadar bu kapanış yinelenir. Sonra noktalar
$$A+B\sqrt{c}$$
tipindeki ifadelerin işaretleri tam olarak karşılaştırılarak sıralanır; böylece kayan nokta hataları önlenir. Komşu kırılma noktaları yine aralıkları ve dolayısıyla sonlu deterministik otomata durumlarını verir.
Fazlar \(0\to1\to2\to0\) döngüsünde ilerlediği için her yönlü çevrimin uzunluğu \(3m\) biçimindedir. Bu çevrim boyunca
$$f_0,f_1,\dots,f_{3m-1},\qquad f_i\in\{0,1\}$$
ikili sözcüğü kaydedilir; \(f_i=1\) ilgili adımın yansımalı daldan geldiğini gösterir. Fazlara göre ayırırsak
$$\alpha_i=f_{3i},\qquad \beta_i=f_{3i+1},\qquad \gamma_i=f_{3i+2}\qquad(0\le i<m).$$
Bir tam üçlü turun yön paritesi
$$w_i=\alpha_i\oplus\beta_i\oplus\gamma_i$$
olur. Çevrimin toplam paritesi çiftse tek geometrik tur yeterlidir; tekse yönü düzeltmek için bir tur daha gerekir. Bu yüzden çevrimin doğal modülü
$$P=\begin{cases} 3m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=0,\\ 6m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=1 \end{cases}$$
şeklindedir.
Aranan senkronizasyon süresi
$$N=3q+R,\qquad R\in\{0,1,2\}$$
olsun. Faz artığı \(R\), ek bir düzeltme sözcüğü üretir. Her \(i\) için
$$t_i^{(0)}=0,\qquad t_i^{(1)}=\alpha_i,\qquad t_i^{(2)}=\alpha_i\oplus\beta_i$$
tanımlanır. Düzeltilmiş tur sözcüğü
$$e_i^{(R)}=w_i\oplus t_i^{(R)}\oplus t_{i+1}^{(R)}$$
olur. Bir kalan sınıfı ancak bu düzeltilmiş sözcük \(w\)'nin döngüsel bir rotasyonuysa ve başlangıç paritesi de uyuyorsa geçerlidir. Uygulamalar tüm rotasyonları ikiye katlanmış \(w\,w\) sözcüğü üzerinde Knuth-Morris-Pratt ile bulur ve başlangıç paritesini prefix xor ile doğrular. Böylece her çevrim sonlu bir küme üretir:
$$N\equiv r \pmod{P},\qquad r\in R_{\text{çevrim}}.$$
Durum grafının farklı bağlı bileşenleri aynı \(N\) üzerinde bağımsız kongruens koşulları dayatır. Bir çevrim \(P_1\) modunda \(R_1\) sınıflarını, başka bir çevrim \(P_2\) modunda \(R_2\) sınıflarını izinliyorsa, uyumlu her çift genelleştirilmiş Çin Kalan Teoremi ile birleştirilir.
Tüm çevrimler işlendiğinde elde kalan sınıflar tam olarak senkron zamanları verir. Bunların en küçük pozitifi \(T(a,b,c)\) olur.
Burada \(c=16=4^2\) olduğundan rasyonel ızgara dalı kullanılır. Önce
$$D=\operatorname{lcm}(10,14,4)=140$$
elde edilir; dolayısıyla
$$S_0=\frac{140}{10}=14,\qquad S_1=\frac{140}{14}=10,\qquad S_2=\frac{140}{4}=35.$$
Her faz \(140\) hücre içerir; toplamda \(420\) durum vardır. Faz \(0\)'da \(0\) ile \(13\) arasındaki hücreler \(139\) ile \(126\) arasına yansır, \(14\) ile \(139\) arasındaki hücreler ise \(0\) ile \(125\) arasına kayar. Sonraki iki fazda da aynı yapı bu kez eşik değerleri \(10\) ve \(35\) ile uygulanır.
Ortaya çıkan otomata çevrimlerine ayrılıp her çevrim için uygun kongruens sınıfları çıkarıldığında ve bunlar CRT ile birleştirildiğinde en küçük pozitif senkronizasyon süresi
$$T(10,14,16)=506$$
olarak bulunur; bu da uygulamalardaki doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı matematiksel planı izler. Önce \(c\)'nin kare olup olmadığına bakılır. Kare durumda \(3D\) durumlu otomat hücre formüllerinden doğrudan kurulur. Kare olmayan durumda ikinci dereceden sayı alanı koordinatlarında tam kırılma noktaları oluşturulur, bunlar tam karşılaştırmalarla sıralanır ve ardından aralık otomata çevrilir.
Daha sonra uygulama her bağlı bileşeni dolaşır, yönlü çevrimi çıkarır, flip sözcüğünü kaydeder ve prefix xor, rotasyon eşleştirmesi ve genelleştirilmiş CRT kullanarak bu sözcükten izinli kalan sınıflarını üretir. Tüm çevrim birleşimlerinden sonra kalan en küçük pozitif sınıf o üçlünün cevabıdır. Son aşamada dış döngüler bütün \(9\le a<b<c\le n\) üçlüleri üzerinde bu değerleri toplar ve nihai toplam için keyfi uzunlukta tamsayı aritmetiği kullanır. Python uygulaması ağır sayısal işi aynı derlenmiş çekirdeğe devrettiği için üç dil de aynı algoritmayı paylaşır.
Sabit bir üçlü için, ayrıklaştırmadan sonra faz başına aralık sayısı \(m\) olsun. O zaman otomat \(3m\) durum içerir. Kare durumda kurulum maliyeti \(O(m)\)'dir. Kare olmayan durumda geri görüntü kapanışı ve tam sıralama baskındır; nokta kümesi oluştuktan sonra yaklaşık \(O(m\log m)\) iş gerekir. Çevrim çıkarımı durum sayısında doğrusaldır ve uzunluğu \(\ell\) olan bir çevrimin sözcük analizi, prefix xor ve KMP doğrusal olduğu için \(O(\ell)\) sürer.
CRT aşamasının maliyeti, her birleşimden sonra kaç kalan sınıfın yaşadığına bağlıdır; pratikte bu kümeler küçük kaldığından temel yük otomatın kurulması ve taranmasıdır. Bellek kullanımı üçlü başına \(O(m)\)'dir. Nihai toplamın maliyeti tüm \(\binom{n-8}{3}\) üçlüler üzerindeki bu maliyetlerin toplamıdır; derlenmiş uygulamalarda dış parametre döngüsü paralelleştirilmiştir.
El rompecabezas está gobernado por tres tamaños de paso:
$$s_0=\frac{1}{a},\qquad s_1=\frac{1}{b},\qquad s_2=\frac{1}{\sqrt{c}}.$$
Esos tres pasos se aplican cíclicamente a un punto del intervalo unidad. Para cada triple \(9 \le a < b < c\), se busca el menor número positivo de pasos \(T(a,b,c)\) para el cual todo el sistema de tres fases vuelve a estar sincronizado. El valor total es
$$\sum_{9\le a < b < c \le n} T(a,b,c).$$
Una simulación directa no sirve, porque el tiempo de sincronización puede ser enorme. La solución reemplaza el proceso continuo por un autómata finito y resuelve exactamente las congruencias que aparecen.
Cada fase usa la misma transformación por partes, solo cambia el tamaño de paso. Para \(0<s<1\), definimos
$$\Phi_s(x)=\begin{cases} 1-x, & 0\le x < s,\\ x-s, & s\le x < 1. \end{cases}$$
La dinámica aplica \(\Phi_{s_0}\), luego \(\Phi_{s_1}\), luego \(\Phi_{s_2}\), y repite ese ciclo. Cada transición conserva o invierte la orientación, así que cada arista del autómata lleva un bit binario de flip.
En cada fase, los puntos de ruptura relevantes son la discontinuidad \(s_\phi\), el extremo \(0\) y todas sus preimágenes bajo las fases anteriores. Una vez conocidos esos puntos, cada intervalo abierto entre dos puntos consecutivos se comporta de forma uniforme: cualquier punto del intervalo va al mismo intervalo siguiente y sufre el mismo cambio de orientación.
Por lo tanto, un estado es simplemente
$$\text{estado}=(\text{fase},\ \text{intervalo}).$$
Cada estado tiene exactamente un sucesor. Así, todo el sistema se convierte en un grafo dirigido donde cada componente termina en un ciclo. El problema pasa a ser el análisis de esos ciclos y de sus condiciones de paridad.
Si \(c=k^2\), entonces \(s_2=1/k\) es racional. En ese caso todos los puntos de ruptura están en la malla común de denominador
$$D=\operatorname{lcm}(a,b,k).$$
Escribimos
$$S_0=\frac{D}{a},\qquad S_1=\frac{D}{b},\qquad S_2=\frac{D}{k}.$$
Cada fase se divide en las \(D\) celdas
$$I_j=\left[\frac{j}{D},\frac{j+1}{D}\right),\qquad 0\le j<D.$$
Para la fase \(\phi\), la transición es
$$I_j\longmapsto\begin{cases} I_{D-1-j}, & j<S_\phi,\\ I_{j-S_\phi}, & j\ge S_\phi. \end{cases}$$
La primera rama es una reflexión y aporta bit \(1\); la segunda es una traslación y aporta bit \(0\). Así, el caso cuadrado produce un autómata finito con exactamente \(3D\) estados.
Cuando \(c\) no es cuadrado, \(1/\sqrt{c}\) es irracional, y ya no existe una malla racional simple. Las implementaciones representan entonces cada punto de ruptura exactamente como
$$x=\frac{P}{ab}+\frac{Q\sqrt{c}}{c}\pmod{1},\qquad P,Q\in\mathbb{Z}.$$
Esto funciona porque los tres tamaños de paso son
$$\frac{1}{a}=\frac{b}{ab},\qquad \frac{1}{b}=\frac{a}{ab},\qquad \frac{1}{\sqrt{c}}=\frac{\sqrt{c}}{c},$$
de modo que toda preimagen sigue perteneciendo a la misma red generada por \(1/(ab)\) y \(\sqrt{c}/c\).
En cada fase se parte del conjunto semilla \(\{0,s_\phi\}\). Si \(y\) ya es un punto de ruptura de la fase \(\phi\), sus preimágenes bajo la fase anterior son
$$x=y+s_{\phi-1}\qquad\text{si } y<1-s_{\phi-1},$$
y
$$x=1-y\qquad\text{si } y>1-s_{\phi-1}.$$
Repitiendo este cierre hasta que no aparezcan puntos nuevos, se obtienen tres conjuntos finitos de puntos de ruptura. Después se ordenan exactamente comparando el signo de expresiones del tipo
$$A+B\sqrt{c},$$
lo que evita errores de coma flotante. Los puntos consecutivos vuelven a definir intervalos, y por tanto un autómata finito determinista.
Como las fases avanzan \(0\to1\to2\to0\), todo ciclo dirigido tiene longitud \(3m\) para algún \(m\). A lo largo del ciclo se registra la palabra
$$f_0,f_1,\dots,f_{3m-1},\qquad f_i\in\{0,1\},$$
donde \(f_i=1\) indica que ese paso usó la rama reflectante. Agrupando por fase:
$$\alpha_i=f_{3i},\qquad \beta_i=f_{3i+1},\qquad \gamma_i=f_{3i+2}\qquad(0\le i<m).$$
La paridad de orientación de una ronda completa de tres pasos es
$$w_i=\alpha_i\oplus\beta_i\oplus\gamma_i.$$
Si la paridad total del ciclo es par, una vuelta geométrica basta para recuperar también la orientación. Si es impar, hace falta otra vuelta adicional. Por eso el módulo natural asociado al ciclo es
$$P=\begin{cases} 3m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=0,\\ 6m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=1. \end{cases}$$
Supongamos que el tiempo de sincronización buscado tiene la forma
$$N=3q+R,\qquad R\in\{0,1,2\}.$$
El desplazamiento parcial \(R\) aporta su propia palabra de corrección. Para cada \(i\), definimos
$$t_i^{(0)}=0,\qquad t_i^{(1)}=\alpha_i,\qquad t_i^{(2)}=\alpha_i\oplus\beta_i.$$
Entonces la palabra corregida es
$$e_i^{(R)}=w_i\oplus t_i^{(R)}\oplus t_{i+1}^{(R)}.$$
Una clase residual es válida exactamente cuando esta palabra corregida es una rotación cíclica de \(w\) y además la paridad inicial también coincide. Las implementaciones buscan todas las rotaciones con Knuth-Morris-Pratt sobre la palabra duplicada \(w\,w\), y verifican la paridad inicial con xors prefijos. Cada ciclo produce así un conjunto finito
$$N\equiv r \pmod{P},\qquad r\in R_{\text{ciclo}}.$$
Las distintas componentes conexas del grafo imponen restricciones de congruencia independientes sobre el mismo \(N\). Si un ciclo permite residuos \(R_1\) módulo \(P_1\) y otro permite residuos \(R_2\) módulo \(P_2\), cada par compatible se combina con la versión generalizada del teorema chino del resto.
Después de procesar todos los ciclos, las clases supervivientes describen exactamente todos los tiempos sincronizados. El menor positivo es \(T(a,b,c)\).
Aquí \(c=16=4^2\), así que se usa la rama racional. Se obtiene
$$D=\operatorname{lcm}(10,14,4)=140,$$
y por tanto
$$S_0=\frac{140}{10}=14,\qquad S_1=\frac{140}{14}=10,\qquad S_2=\frac{140}{4}=35.$$
Cada fase tiene \(140\) celdas, de modo que el autómata total tiene \(420\) estados. En la fase \(0\), las celdas \(0\) a \(13\) se reflejan hacia \(139\) a \(126\), mientras que las celdas \(14\) a \(139\) se trasladan hacia \(0\) a \(125\). El mismo patrón se repite en las dos fases siguientes con umbrales \(10\) y \(35\).
Al descomponer este autómata en ciclos dirigidos, extraer de cada uno sus congruencias permitidas y fusionarlas con el TCR, el menor tiempo positivo de sincronización resulta ser
$$T(10,14,16)=506,$$
exactamente el valor de comprobación usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen el mismo plan matemático. Primero distinguen si \(c\) es cuadrado o no. En el caso cuadrado construyen directamente el autómata de \(3D\) estados a partir de fórmulas explícitas para las celdas. En el caso no cuadrado construyen conjuntos exactos de puntos de ruptura en coordenadas de campo cuadrático, los ordenan con comparaciones exactas y luego forman el autómata de intervalos correspondiente.
Después la implementación recorre cada componente conexa, extrae su ciclo dirigido, registra la palabra de flips y la convierte en clases residuales permitidas mediante xors prefijos, búsqueda de rotaciones y TCR generalizado. La menor clase positiva que sobrevive a todas las fusiones es la respuesta del triple. Finalmente los bucles exteriores suman esos valores para todos los \(9\le a<b<c\le n\), usando enteros de precisión arbitraria para el total final. La implementación en Python delega el trabajo numérico pesado al mismo núcleo compilado, así que las tres versiones comparten el mismo algoritmo subyacente.
Para un triple fijo, sea \(m\) el número de intervalos por fase tras la discretización. Entonces el autómata tiene \(3m\) estados. Construir el caso cuadrado cuesta \(O(m)\). En el caso no cuadrado, el cierre por preimágenes y la ordenación exacta dominan el coste, aproximadamente \(O(m\log m)\) una vez conocido el conjunto de puntos. La extracción de ciclos es lineal en el número de estados, y el análisis de una palabra de longitud \(\ell\) cuesta \(O(\ell)\) porque tanto los xors prefijos como KMP son lineales.
La etapa de TCR depende de cuántas clases residuales sobreviven después de cada fusión; en la práctica esos conjuntos se mantienen pequeños, así que el coste dominante es construir y recorrer el autómata. La memoria usada es \(O(m)\) por triple. El cálculo total para la suma final es la suma de estos costes sobre todos los \(\binom{n-8}{3}\) triples, y en las implementaciones compiladas el bucle exterior está paralelizado.
这个题目的动力系统由三个步长控制：
$$s_0=\frac{1}{a},\qquad s_1=\frac{1}{b},\qquad s_2=\frac{1}{\sqrt{c}}.$$
它们按固定顺序循环作用在单位区间上的一个点上。对于每个满足 \(9 \le a < b < c\) 的三元组，需要求出最小正整数步数 \(T(a,b,c)\)，使得整个三阶段系统再次完全同步。最终要求的是
$$\sum_{9\le a < b < c \le n} T(a,b,c).$$
直接逐步模拟不可行，因为同步时间可能非常大。程序真正做的事情，是先把连续的区间映射离散化为有限状态自动机，再把“何时能够同步”转写为一组精确的同余条件。
三阶段过程都使用同一个分段映射，只是步长不同。对任意 \(0<s<1\)，定义
$$\Phi_s(x)=\begin{cases} 1-x, & 0\le x < s,\\ x-s, & s\le x < 1. \end{cases}$$
系统依次应用 \(\Phi_{s_0}\)、\(\Phi_{s_1}\)、\(\Phi_{s_2}\)，然后不断重复。第一支是反射，第二支是平移，因此每一步都会自然附带一个二进制翻转标记：反射记为 \(1\)，不反射记为 \(0\)。
对某一阶段来说，真正重要的是所有“断点”。它们包括本阶段的分界点 \(s_\phi\)、端点 \(0\)，以及这些点在前一阶段、前两阶段等逆像意义下不断回溯得到的所有点。一旦这些断点全部确定，相邻两个断点之间的每个开区间都会整体一致地演化：区间中的任意点都会进入同一个下一阶段区间，并且具有相同的方向变化。
因此可以把一个状态写成
$$\text{状态}=(\text{阶段},\ \text{区间}).$$
每个状态恰好只有一个后继，所以整个系统变成了一个函数图。这样的有向图每个连通分量最终都会落入某个有向环。于是问题的核心就不再是连续动力系统本身，而是这些环如何施加同步约束。
如果 \(c=k^2\)，那么第三个步长 \(s_2=1/k\) 也是有理数。此时三个步长都与同一个公共分母兼容，公共网格大小为
$$D=\operatorname{lcm}(a,b,k).$$
令
$$S_0=\frac{D}{a},\qquad S_1=\frac{D}{b},\qquad S_2=\frac{D}{k}.$$
单位区间在每个阶段都被切成 \(D\) 个等长小区间
$$I_j=\left[\frac{j}{D},\frac{j+1}{D}\right),\qquad 0\le j<D.$$
对于阶段 \(\phi\)，映射规则完全显式：
$$I_j\longmapsto\begin{cases} I_{D-1-j}, & j<S_\phi,\\ I_{j-S_\phi}, & j\ge S_\phi. \end{cases}$$
前一支对应反射，所以翻转位为 \(1\)；后一支对应平移，所以翻转位为 \(0\)。因此平方情形下自动机一共只有 \(3D\) 个状态，完全可以显式构造。
如果 \(c\) 不是平方数，那么 \(1/\sqrt{c}\) 是无理数，简单的有理网格就失效了。程序改用如下精确形式表示所有断点：
$$x=\frac{P}{ab}+\frac{Q\sqrt{c}}{c}\pmod{1},\qquad P,Q\in\mathbb{Z}.$$
这并不是偶然的选择，因为三种步长本身正好写成
$$\frac{1}{a}=\frac{b}{ab},\qquad \frac{1}{b}=\frac{a}{ab},\qquad \frac{1}{\sqrt{c}}=\frac{\sqrt{c}}{c}.$$
所以只要从这些步长和端点出发不断取逆像，所有新点都会留在由 \(1/(ab)\) 与 \(\sqrt{c}/c\) 张成的同一个离散结构里。
每个阶段一开始只放入两个种子点 \(\{0,s_\phi\}\)。如果某个点 \(y\) 已经是阶段 \(\phi\) 的断点，那么它在前一阶段的逆像由下面两种情况给出：
$$x=y+s_{\phi-1}\qquad\text{当 } y<1-s_{\phi-1},$$
以及
$$x=1-y\qquad\text{当 } y>1-s_{\phi-1}.$$
不断重复这个“逆像闭包”过程，直到再也没有新点出现，就得到三个有限断点集合。随后程序需要把这些点从小到大排序。它不是用浮点近似直接比较，而是把两个点之差改写成
$$A+B\sqrt{c}$$
的符号判断问题，再用整数算术精确比较，从而避免精度误差。排好序以后，相邻断点之间的开区间就是自动机的状态区间。
由于阶段顺序永远是 \(0\to1\to2\to0\)，所以任何有向环长度都必然是 \(3m\) 的形式。沿着这个环走一圈，可以得到一串翻转位
$$f_0,f_1,\dots,f_{3m-1},\qquad f_i\in\{0,1\}.$$
把它按三个阶段重新分组，写成
$$\alpha_i=f_{3i},\qquad \beta_i=f_{3i+1},\qquad \gamma_i=f_{3i+2}\qquad(0\le i<m).$$
那么一次完整三步循环的方向奇偶性就是
$$w_i=\alpha_i\oplus\beta_i\oplus\gamma_i.$$
如果整条环的总奇偶性是偶数，那么走完一圈之后不仅位置结构回到原样，方向也回到原样；如果总奇偶性是奇数，那么还需要再多走一整圈才能把方向也修正回来。因此，这条环对应的模数不是固定的 \(3m\)，而是
$$P=\begin{cases} 3m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=0,\\ 6m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=1. \end{cases}$$
设候选同步时间写成
$$N=3q+R,\qquad R\in\{0,1,2\}.$$
这里的 \(R\) 表示最后没有走完整轮，只额外多走了 \(0\)、\(1\) 或 \(2\) 个阶段。这会给比特结构带来一个修正项。程序定义
$$t_i^{(0)}=0,\qquad t_i^{(1)}=\alpha_i,\qquad t_i^{(2)}=\alpha_i\oplus\beta_i,$$
再构造修正后的整轮比特串
$$e_i^{(R)}=w_i\oplus t_i^{(R)}\oplus t_{i+1}^{(R)}.$$
某个同余类 \(N\equiv r\pmod P\) 合法，当且仅当这个修正后的字 \(e^{(R)}\) 正好是原字 \(w\) 的某个循环位移，并且起始方向奇偶性也一致。程序在双倍串 \(w\,w\) 上使用 Knuth-Morris-Pratt 算法寻找所有循环匹配，再用前缀 xor 验证起始奇偶性。于是每条环最终都会贡献一个有限集合
$$N\equiv r \pmod{P},\qquad r\in R_{\text{环}}.$$
自动机不同连通分量上的环，对同一个未知同步时间 \(N\) 给出彼此独立的同余限制。如果一条环允许的同余类是模 \(P_1\) 下的某些余数，而另一条环允许的同余类是模 \(P_2\) 下的某些余数，那么程序会把所有兼容的余数组合起来，用广义中国剩余定理逐步合并。
所有环都处理完之后，剩下的余数类正好描述了所有可能的同步时刻。最小的正解就是 \(T(a,b,c)\)。
这里 \(c=16=4^2\)，因此可以直接走有理网格分支。首先得到
$$D=\operatorname{lcm}(10,14,4)=140,$$
从而
$$S_0=\frac{140}{10}=14,\qquad S_1=\frac{140}{14}=10,\qquad S_2=\frac{140}{4}=35.$$
所以每个阶段都有 \(140\) 个小区间，整个自动机共有 \(420\) 个状态。在第 \(0\) 阶段，编号 \(0\) 到 \(13\) 的小区间会被反射到编号 \(139\) 到 \(126\)；编号 \(14\) 到 \(139\) 的小区间则平移到编号 \(0\) 到 \(125\)。第 \(1\) 阶段和第 \(2\) 阶段也是同样的结构，只是阈值分别变成 \(10\) 和 \(35\)。
把这个自动机拆成若干有向环，分别提取允许的同余类，再用中国剩余定理合并之后，就会得到最小正同步时间
$$T(10,14,16)=506,$$
这与实现中的检验值完全一致。
C++、Python 和 Java 实现遵循完全相同的数学流程。首先判断 \(c\) 是否为平方数。若是平方数，就直接利用显式的小区间转移公式构造 \(3D\) 状态自动机；若不是平方数，就在二次域坐标中精确构造断点集合，用精确比较完成排序，再形成对应的区间自动机。
随后，实现会遍历每个连通分量，提取其中的有向环，记录环上的翻转比特串，并通过前缀 xor、循环匹配和广义中国剩余定理把这一条环转化为允许的同余类。所有环约束合并之后，剩下的最小正余数就是该三元组的答案。外层循环再对所有 \(9\le a<b<c\le n\) 的三元组求和，最终总和使用任意精度整数保存。Python 版本把主要数值计算委托给同一个编译后的核心，因此三种语言在算法本质上是一致的。
对一个固定三元组，设离散化后每个阶段有 \(m\) 个区间，则自动机共有 \(3m\) 个状态。平方分支的构造成本是 \(O(m)\)。非平方分支中，逆像闭包和精确排序是主要代价；一旦断点集合形成，整体大致是 \(O(m\log m)\)。有向环提取与状态数线性相关，而长度为 \(\ell\) 的环在比特串分析阶段只需要 \(O(\ell)\) 时间，因为前缀 xor 和 KMP 都是线性的。
CRT 合并阶段的成本取决于每次合并之后还剩多少可行余数类；在实际数据中这些集合通常不大，因此主导成本仍然是自动机的构造与扫描。空间复杂度对每个三元组是 \(O(m)\)。最终总时间是对所有 \(\binom{n-8}{3}\) 个三元组的这些成本求和，而编译型实现会对外层参数循环进行并行化。
Задача определяется тремя длинами шага:
$$s_0=\frac{1}{a},\qquad s_1=\frac{1}{b},\qquad s_2=\frac{1}{\sqrt{c}}.$$
Они циклически применяются к точке на единичном интервале. Для каждой тройки \(9 \le a < b < c\) нужно найти наименьшее положительное число шагов \(T(a,b,c)\), после которого вся трёхфазная система снова приходит в синхронное состояние. Итоговая величина равна
$$\sum_{9\le a < b < c \le n} T(a,b,c).$$
Прямая симуляция здесь бесполезна: время синхронизации может быть очень большим. Поэтому решение сначала превращает непрерывную динамику в конечный автомат, а затем точно решает возникающие сравнения по модулю.
Во всех трёх фазах используется одна и та же кусочно заданная функция, меняется только длина шага. Для \(0<s<1\) положим
$$\Phi_s(x)=\begin{cases} 1-x, & 0\le x < s,\\ x-s, & s\le x < 1. \end{cases}$$
Динамика применяет \(\Phi_{s_0}\), затем \(\Phi_{s_1}\), затем \(\Phi_{s_2}\), после чего цикл повторяется. Первый участок отражает ориентацию, второй её сохраняет, поэтому каждому переходу естественно сопоставляется двоичный бит flip.
В каждой фазе важны точки разбиения: сама точка разрыва \(s_\phi\), граница \(0\), а также все их прообразы относительно предыдущих фаз. Когда все такие точки найдены, каждый открытый интервал между соседними точками ведёт себя однородно: любая точка из него попадает в один и тот же следующий интервал и испытывает одно и то же изменение ориентации.
Поэтому состояние имеет вид
$$\text{состояние}=(\text{фаза},\ \text{интервал}).$$
У каждого состояния есть ровно один следующий узел. Значит, вся система становится функциональным ориентированным графом, в котором каждая компонента связности в конце концов входит в цикл. Тем самым задача сводится к анализу этих циклов и накладываемых ими условий на паритет.
Пусть \(c=k^2\). Тогда \(s_2=1/k\) рационально, и все точки разбиения лежат на общей сетке с знаменателем
$$D=\operatorname{lcm}(a,b,k).$$
Обозначим
$$S_0=\frac{D}{a},\qquad S_1=\frac{D}{b},\qquad S_2=\frac{D}{k}.$$
Каждая фаза разбивается на \(D\) ячеек
$$I_j=\left[\frac{j}{D},\frac{j+1}{D}\right),\qquad 0\le j<D.$$
Для фазы \(\phi\) переходы записываются явно:
$$I_j\longmapsto\begin{cases} I_{D-1-j}, & j<S_\phi,\\ I_{j-S_\phi}, & j\ge S_\phi. \end{cases}$$
Первая ветвь соответствует отражению и даёт бит \(1\), вторая соответствует сдвигу и даёт бит \(0\). Следовательно, в квадратном случае получается конечный автомат ровно с \(3D\) состояниями.
Когда \(c\) не является квадратом, величина \(1/\sqrt{c}\) иррациональна, и простой рациональной сетки уже нет. Тогда все точки разбиения представляются точно в виде
$$x=\frac{P}{ab}+\frac{Q\sqrt{c}}{c}\pmod{1},\qquad P,Q\in\mathbb{Z}.$$
Это естественно, потому что три длины шага равны
$$\frac{1}{a}=\frac{b}{ab},\qquad \frac{1}{b}=\frac{a}{ab},\qquad \frac{1}{\sqrt{c}}=\frac{\sqrt{c}}{c},$$
и потому все прообразы остаются в той же решётке, порождённой \(1/(ab)\) и \(\sqrt{c}/c\).
Для каждой фазы стартовое множество равно \(\{0,s_\phi\}\). Если \(y\) уже является точкой разбиения фазы \(\phi\), то его прообразы относительно предыдущей фазы имеют вид
$$x=y+s_{\phi-1}\qquad\text{при } y<1-s_{\phi-1},$$
и
$$x=1-y\qquad\text{при } y>1-s_{\phi-1}.$$
Повторяя это замыкание по прообразам до стабилизации, получаем три конечных множества точек. Затем они сортируются точно через сравнение знака выражений вида
$$A+B\sqrt{c},$$
что устраняет ошибки вещественной арифметики. Соседние точки снова образуют интервалы, а значит и конечный детерминированный автомат.
Поскольку фазы всегда идут \(0\to1\to2\to0\), длина любого ориентированного цикла равна \(3m\) для некоторого \(m\). Вдоль цикла записывается двоичное слово
$$f_0,f_1,\dots,f_{3m-1},\qquad f_i\in\{0,1\},$$
где \(f_i=1\) означает, что на этом шаге использовалась отражающая ветвь. Разобьём эти биты по фазам:
$$\alpha_i=f_{3i},\qquad \beta_i=f_{3i+1},\qquad \gamma_i=f_{3i+2}\qquad(0\le i<m).$$
Паритет ориентации за одну полную тройку шагов равен
$$w_i=\alpha_i\oplus\beta_i\oplus\gamma_i.$$
Если суммарный паритет цикла чётный, то одного геометрического обхода достаточно. Если нечётный, нужен ещё один обход, чтобы вернуть и ориентацию. Поэтому естественный модуль цикла равен
$$P=\begin{cases} 3m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=0,\\ 6m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=1. \end{cases}$$
Пусть искомое время синхронизации имеет вид
$$N=3q+R,\qquad R\in\{0,1,2\}.$$
Частичный сдвиг по фазам \(R\) вносит собственное корректирующее слово. Для каждого \(i\) положим
$$t_i^{(0)}=0,\qquad t_i^{(1)}=\alpha_i,\qquad t_i^{(2)}=\alpha_i\oplus\beta_i.$$
Тогда исправленное слово полных раундов равно
$$e_i^{(R)}=w_i\oplus t_i^{(R)}\oplus t_{i+1}^{(R)}.$$
Класс вычетов допустим тогда и только тогда, когда это исправленное слово является циклическим сдвигом \(w\), а начальный паритет также согласован. Реализации ищут такие сдвиги алгоритмом Кнута-Морриса-Пратта на удвоенном слове \(w\,w\), а стартовый паритет проверяют через префиксные xor. В итоге один цикл даёт конечное множество
$$N\equiv r \pmod{P},\qquad r\in R_{\text{цикла}}.$$
Разные компоненты графа задают независимые сравнения по модулю для одного и того же \(N\). Если один цикл допускает остатки \(R_1\) по модулю \(P_1\), а другой допускает остатки \(R_2\) по модулю \(P_2\), то каждая совместимая пара объединяется обобщённой китайской теоремой об остатках.
После обработки всех циклов оставшиеся классы вычетов описывают все возможные синхронизированные времена. Наименьшее положительное значение и есть \(T(a,b,c)\).
Здесь \(c=16=4^2\), значит используется рациональная ветвь. Получаем
$$D=\operatorname{lcm}(10,14,4)=140,$$
а значит
$$S_0=\frac{140}{10}=14,\qquad S_1=\frac{140}{14}=10,\qquad S_2=\frac{140}{4}=35.$$
Следовательно, в каждой фазе по \(140\) ячеек, а всего в автомате \(420\) состояний. В фазе \(0\) ячейки с номерами от \(0\) до \(13\) отражаются в ячейки от \(139\) до \(126\), а ячейки от \(14\) до \(139\) сдвигаются в ячейки от \(0\) до \(125\). Тот же принцип повторяется в следующих фазах с порогами \(10\) и \(35\).
Если разложить этот автомат на ориентированные циклы, извлечь из каждого допустимые классы вычетов и затем объединить их через CRT, то получим минимальное положительное время синхронизации
$$T(10,14,16)=506,$$
что в точности совпадает с контрольным значением из реализаций.
Реализации на C++, Python и Java следуют одному и тому же математическому плану. Сначала они различают квадратный и неквадратный случай для \(c\). В квадратном случае автомат из \(3D\) состояний строится сразу по явным формулам для ячеек. В неквадратном случае строятся точные множества точек разбиения в координатах квадратического поля, они точно сортируются, после чего из них собирается интервальный автомат.
Далее реализация проходит по каждой компоненте связности, извлекает её ориентированный цикл, записывает слово flips и преобразует его в допустимые классы вычетов с помощью префиксных xor, поиска циклических сдвигов и обобщённой CRT. Наименьший положительный остаток, переживший все объединения, и есть ответ для данной тройки. Затем внешние циклы суммируют эти значения по всем \(9\le a<b<c\le n\), используя целые числа произвольной длины для окончательной суммы. Python-версия передаёт основную численную работу тому же скомпилированному ядру, поэтому все три языка разделяют один и тот же алгоритм.
Для фиксированной тройки пусть \(m\) обозначает число интервалов на фазу после дискретизации. Тогда автомат содержит \(3m\) состояний. В квадратном случае построение занимает \(O(m)\). В неквадратном случае основную стоимость дают замыкание по прообразам и точная сортировка, то есть примерно \(O(m\log m)\) после формирования множества точек. Выделение циклов линейно по числу состояний, а анализ слова длины \(\ell\) занимает \(O(\ell)\), потому что и префиксные xor, и KMP линейны.
Этап CRT зависит от того, сколько классов вычетов остаётся после каждого объединения; на практике эти множества невелики, поэтому основной расход идёт на построение и обход автомата. Память на одну тройку равна \(O(m)\). Полная стоимость вычисления финальной суммы есть сумма этих затрат по всем \(\binom{n-8}{3}\) тройкам, а во внешнем цикле по параметрам в компилируемых реализациях используется параллелизм.
تتحكم في اللغز ثلاث قيم للخطوة:
$$s_0=\frac{1}{a},\qquad s_1=\frac{1}{b},\qquad s_2=\frac{1}{\sqrt{c}}.$$
وتُطبَّق هذه الخطوات دوريًا على نقطة داخل الفترة الواحدة. لكل ثلاثية \(9 \le a < b < c\) نريد أصغر عدد صحيح موجب من الخطوات \(T(a,b,c)\) يعود بعده النظام ثلاثي المراحل إلى حالة تزامن كاملة. والقيمة النهائية هي
$$\sum_{9\le a < b < c \le n} T(a,b,c).$$
المحاكاة المباشرة غير عملية لأن زمن التزامن قد يكون كبيرًا جدًا. لذلك يحوّل الحل الحركة المستمرة إلى آلة حالات منتهية، ثم يحل قيود الت合同 الموافقة بدقة تامة.
تستعمل كل مرحلة التحويل القطعي نفسه مع اختلاف طول الخطوة فقط. عندما يكون \(0<s<1\) نعرّف
$$\Phi_s(x)=\begin{cases} 1-x, & 0\le x < s,\\ x-s, & s\le x < 1. \end{cases}$$
ثم يطبَّق بالتتابع \(\Phi_{s_0}\) ثم \(\Phi_{s_1}\) ثم \(\Phi_{s_2}\)، وتتكرر هذه الدورة إلى ما لا نهاية. الفرع الأول يعكس الاتجاه، والفرع الثاني يحافظ عليه، ولهذا فكل انتقال يحمل بتًّا ثنائيًا يعبّر عن وجود انعكاس أو عدمه.
في كل مرحلة، النقاط المهمة هي نقاط الانكسار: نقطة عدم الاستمرار \(s_\phi\)، والنقطة \(0\)، وجميع الصور العكسية لهاتين النقطتين تحت المراحل السابقة. بعد تحديد هذه النقاط، يصبح كل فاصل مفتوح بين نقطتين متتاليتين ذا سلوك موحّد: أي نقطة داخله تنتقل إلى الفاصل التالي نفسه وتتعرّض لتغير الاتجاه نفسه.
لذلك يمكن تمثيل الحالة على الصورة
$$\mathrm{state}=(\mathrm{phase},\ \mathrm{interval}).$$
ولأن لكل حالة تابعًا وحيدًا، فإن النظام كله يصبح مخططًا موجّهًا من نوع الدالة، وكل مركبة متصلة فيه تنتهي إلى دورة. وهكذا تنتقل المسألة من دراسة الحركة المستمرة إلى دراسة هذه الدورات وما تفرضه من شروط على التوافق.
إذا كانت \(c=k^2\) فإن \(s_2=1/k\) يكون عددًا نسبيًا. عندئذ تقع جميع نقاط الانكسار على شبكة مشتركة ذات مقام
$$D=\operatorname{lcm}(a,b,k).$$
ونكتب
$$S_0=\frac{D}{a},\qquad S_1=\frac{D}{b},\qquad S_2=\frac{D}{k}.$$
كل مرحلة تنقسم إلى \(D\) خلايا من الشكل
$$I_j=\left[\frac{j}{D},\frac{j+1}{D}\right),\qquad 0\le j<D.$$
وفي المرحلة \(\phi\) يصبح الانتقال صريحًا:
$$I_j\longmapsto\begin{cases} I_{D-1-j}, & j<S_\phi,\\ I_{j-S_\phi}, & j\ge S_\phi. \end{cases}$$
الفرع الأول انعكاس فيعطي البت \(1\)، والفرع الثاني إزاحة فيعطي البت \(0\). وهكذا تعطي حالة المربع الكامل آلة منتهية فيها بالضبط \(3D\) حالات.
عندما لا تكون \(c\) مربعًا، فإن \(1/\sqrt{c}\) غير نسبي، فلا تكفي شبكة نسبية بسيطة. لهذا تُمثَّل كل نقطة انكسار بدقة على الصورة
$$x=\frac{P}{ab}+\frac{Q\sqrt{c}}{c}\pmod{1},\qquad P,Q\in\mathbb{Z}.$$
وهذا مناسب لأن أطوال الخطوات الثلاثة نفسها تكتب على النحو
$$\frac{1}{a}=\frac{b}{ab},\qquad \frac{1}{b}=\frac{a}{ab},\qquad \frac{1}{\sqrt{c}}=\frac{\sqrt{c}}{c},$$
ومن ثم تبقى جميع الصور العكسية داخل الشبكة المولدة بواسطة \(1/(ab)\) و \(\sqrt{c}/c\).
في كل مرحلة يبدأ البناء من المجموعة \(\{0,s_\phi\}\). وإذا كانت \(y\) نقطة انكسار معروفة في المرحلة \(\phi\)، فإن صورها العكسية تحت المرحلة السابقة تكون
إذا تحقق الشرط \(y<1-s_{\phi-1}\)، فإن إحدى الصور العكسية هي
$$x=y+s_{\phi-1}.$$
أما إذا تحقق الشرط \(y>1-s_{\phi-1}\)، فإن الصورة العكسية الأخرى هي
$$x=1-y.$$
ويُكرَّر هذا الإغلاق حتى لا تظهر نقاط جديدة. بعد ذلك ترتَّب النقاط ترتيبًا دقيقًا بمقارنة إشارة تعبيرات من الشكل
$$A+B\sqrt{c},$$
بدل الاعتماد على تقريب عددي عائم. ومن النقاط المرتبة نحصل مرة أخرى على فواصل متجاورة، ومن ثم على آلة حالات منتهية.
بما أن ترتيب المراحل هو دائمًا \(0\to1\to2\to0\)، فإن طول كل دورة موجّهة يساوي \(3m\) لعدد صحيح ما \(m\). وعلى طول هذه الدورة نسجّل الكلمة الثنائية
$$f_0,f_1,\dots,f_{3m-1},\qquad f_i\in\{0,1\}.$$
ثم نعيد تجميعها حسب المراحل:
$$\alpha_i=f_{3i},\qquad \beta_i=f_{3i+1},\qquad \gamma_i=f_{3i+2}\qquad(0\le i<m).$$
فتكون مفاضلة الاتجاه خلال دورة كاملة من ثلاث خطوات
$$w_i=\alpha_i\oplus\beta_i\oplus\gamma_i.$$
إذا كانت مفاضلة الدورة كلها زوجية، فإن لفة واحدة تكفي لاستعادة الموضع والاتجاه. أما إذا كانت فردية، فلابد من لفة ثانية لإصلاح الاتجاه أيضًا. لذلك يكون المقياس الطبيعي المرتبط بالدورة هو
$$P=\begin{cases} 3m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=0,\\ 6m, & \displaystyle\bigoplus_{i=0}^{m-1} w_i=1. \end{cases}$$
لنفترض أن زمن التزامن المرشح يكتب في الصورة
$$N=3q+R,\qquad R\in\{0,1,2\}.$$
إن الإزاحة الجزئية \(R\) بين المراحل تضيف كلمة تصحيح خاصة بها. نعرّف لكل \(i\)
$$t_i^{(0)}=0,\qquad t_i^{(1)}=\alpha_i,\qquad t_i^{(2)}=\alpha_i\oplus\beta_i.$$
ثم تصبح الكلمة المصححة
$$e_i^{(R)}=w_i\oplus t_i^{(R)}\oplus t_{i+1}^{(R)}.$$
وتكون فئة البواقي صالحة إذا وفقط إذا كانت هذه الكلمة المصححة دورانًا دوريًا للكلمة \(w\)، وإذا كان توافق الاتجاه الابتدائي صحيحًا أيضًا. لذلك تستعمل التطبيقات خوارزمية Knuth-Morris-Pratt على الكلمة المضاعفة \(w\,w\) لاستخراج جميع الدورانات الممكنة، ثم تتحقق من شرط البداية باستخدام xor تراكمي. وبذلك تعطي كل دورة مجموعة منتهية
$$N\equiv r \pmod{P},\qquad r\in R_{\mathrm{cycle}}.$$
كل مركبة من مركبات المخطط تفرض قيود توافق مستقلة على الزمن نفسه \(N\). فإذا كانت دورة تسمح ببواقي \(R_1\) بترديد \(P_1\)، ودورة أخرى تسمح ببواقي \(R_2\) بترديد \(P_2\)، فإن كل زوج متوافق يُدمج باستعمال النسخة المعممة من نظرية البواقي الصينية.
وبعد معالجة جميع الدورات، تصف فئات البواقي المتبقية كل الأزمنة المتزامنة الممكنة. وأصغر حل موجب بينها هو \(T(a,b,c)\).
هنا \(c=16=4^2\)، لذلك نستخدم الفرع الشبكي النسبي. نحصل أولًا على
$$D=\operatorname{lcm}(10,14,4)=140,$$
ومن ثم
$$S_0=\frac{140}{10}=14,\qquad S_1=\frac{140}{14}=10,\qquad S_2=\frac{140}{4}=35.$$
إذًا في كل مرحلة \(140\) خلية، وفي الآلة كلها \(420\) حالة. في المرحلة \(0\) تنعكس الخلايا من \(0\) إلى \(13\) نحو الخلايا من \(139\) إلى \(126\)، بينما تُزاح الخلايا من \(14\) إلى \(139\) نحو الخلايا من \(0\) إلى \(125\). ويتكرر النمط نفسه في المرحلتين التاليتين لكن مع العتبتين \(10\) و \(35\).
وعند تفكيك هذه الآلة إلى دورات، واستخراج فئات البواقي المسموح بها من كل دورة، ثم دمجها بنظرية البواقي الصينية، نحصل على أصغر زمن موجب للتزامن:
$$T(10,14,16)=506,$$
وهو تمامًا مقدار التحقق الموجود في التطبيقات.
تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها. فهي تبدأ أولًا بالتمييز بين حالة كون \(c\) مربعًا وحالة كونه غير مربع. في الحالة المربعة تُبنى آلة الحالات ذات \(3D\) حالة مباشرة من صيغ الخلايا الصريحة. وفي الحالة غير المربعة تُبنى مجموعات نقاط الانكسار بدقة داخل إحداثيات حقل تربيعي، ثم ترتب بمقارنات دقيقة، وبعدها تُنشأ آلة الفواصل المناظرة.
بعد ذلك تمرّ الشيفرة على كل مركبة متصلة، وتستخرج دورتها الموجّهة، وتجمع كلمة بتات الانعكاس، ثم تحوّل هذه الكلمة إلى فئات بواقي مسموح بها باستخدام xor تراكمي، ومطابقة دورانية، ونسخة معممة من CRT. أصغر باقٍ موجب ينجو من جميع عمليات الدمج هو جواب تلك الثلاثية. وأخيرًا تجمع الحلقات الخارجية هذه القيم لكل \(9\le a<b<c\le n\)، مع استعمال حساب صحيح ذي دقة اعتباطية للمجموع النهائي. أما تطبيق Python فيفوّض الحساب العددي الثقيل إلى النواة المترجمة نفسها، ولذلك فاللغات الثلاث تشترك في الخوارزمية ذاتها.
لثلاثية ثابتة، لنفرض أن عدد الفواصل في كل مرحلة بعد التحويل المنفصل هو \(m\). عندئذ تحتوي الآلة على \(3m\) حالة. بناء الفرع المربّع يكلف \(O(m)\). وفي الفرع غير المربّع تهيمن عملية إغلاق الصور العكسية مع الترتيب الدقيق، فتكون الكلفة تقريبًا \(O(m\log m)\) بعد تكوّن مجموعة النقاط. استخراج الدورات خطي في عدد الحالات، وتحليل كلمة طولها \(\ell\) يكلف \(O(\ell)\) لأن كلًا من xor التراكمي وKMP خطي.
أما مرحلة CRT فتعتمد على عدد فئات البواقي التي تبقى بعد كل دمج؛ وعمليًا تبقى هذه المجموعات صغيرة، ولذلك يظل العبء الأساسي في بناء الآلة واجتيازها. استهلاك الذاكرة هو \(O(m)\) لكل ثلاثية. أما الكلفة الكلية للمجموع النهائي فهي مجموع هذه التكاليف على جميع الثلاثيات \(\binom{n-8}{3}\)، وتستفيد التطبيقات المترجمة من تنفيذ متوازٍ على الحلقة الخارجية.