Let \(\otimes\) denote carry-less multiplication on nonnegative integers, meaning that binary expansions are multiplied as polynomials over \(\mathbb{F}_2\), and let \(\oplus\) denote bitwise XOR. The quadratic form in the problem is
$$f(a,b)=a\otimes a \oplus \left(2\otimes a\otimes b\right)\oplus b\otimes b.$$
For given bounds \(n\) and \(m\), we must count
$$C(n,m)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2: 0\le a\le b\le n,\ f(a,b)\le m\right\}.$$
A direct enumeration would inspect about \(n^2/2\) ordered pairs, which is hopeless for the actual input. The solution instead exploits an invariant orbit structure that lets us count whole families of pairs from a small set of canonical seeds.
The key observation is that carry-less arithmetic is ordinary polynomial arithmetic over \(\mathbb{F}_2\). Once the expression is rewritten in that language, the recurrence used by the implementation becomes natural and its invariant becomes easy to verify.
Write the binary expansions of \(a\) and \(b\) as polynomials
$$A(t)=\sum_{i\ge 0} a_i t^i,\qquad B(t)=\sum_{i\ge 0} b_i t^i,$$
with coefficients in \(\mathbb{F}_2\). Under this identification, XOR is polynomial addition and carry-less multiplication is ordinary multiplication. Therefore the integer quantity \(f(a,b)\) is the binary encoding of
$$Q(A,B)=A(t)^2+tA(t)B(t)+B(t)^2.$$
The factor \(2\) becomes \(t\), because shifting left by one bit corresponds to multiplying by \(t\).
Consider the map
$$T(A,B)=\left(B,\ tB+A\right).$$
In integer language this is exactly
$$T(a,b)=\left(b,\ (2b)\oplus a\right).$$
Now compute the value of \(Q\) after one step:
$$\begin{aligned} Q(T(A,B))&=B^2+tB(tB+A)+(tB+A)^2 \\ &=B^2+t^2B^2+tAB+t^2B^2+A^2 \\ &=A^2+tAB+B^2 \\ &=Q(A,B). \end{aligned}$$
So the value \(f(a,b)\) is constant along the entire orbit generated by repeatedly applying \(T\). Each admissible pair belongs to exactly one such invariant orbit.
The inverse transformation is obtained by solving \(T(x,y)=(a,b)\). Since \(a=y\) and \(b=2y\oplus x\), the predecessor of \((a,b)\) is
$$T^{-1}(a,b)=\left(b\oplus(2a),\ a\right).$$
If this predecessor is still ordered, meaning
$$b\oplus(2a)\le a,$$
then the current pair is not the first ordered point on its orbit and must not be counted as a seed. Hence every nonzero ordered pair is a canonical seed precisely when
$$b\oplus(2a) > a.$$
This rule removes duplicates: exactly one ordered representative survives per orbit. The pair \((0,0)\) is special, because it is a fixed point and is counted directly.
If \(m>0\) has \(d\) binary digits, the implementations only scan ordered pairs with
$$0\le a\le b \lt 2^{\lceil(d+1)/2\rceil}.$$
This is a safe finite search region for seeds. Intuitively, \(f(a,b)\) is a quadratic carry-less form, so its bit-length is roughly twice the bit-length of the inputs. Once \(b\) is above this threshold, an ordered seed cannot have invariant value at most \(m\), so it can never contribute to the answer.
Starting from a canonical seed, repeatedly apply
$$ (a,b)\mapsto \left(b,\ (2b)\oplus a\right). $$
For ordered nonnegative pairs, the new second component is strictly larger than the old one: the highest bit of \(2b\) lies one position above every bit of \(a\), so it cannot be canceled by XOR with \(a\). Therefore the orbit walk is strictly increasing in \(b\), and we only need to count how many orbit points satisfy
$$b\le n.$$
No further value test is needed during that walk, because the invariant \(f(a,b)\) stays constant along the orbit.
Here \(m\) has one binary digit, so the seed scan only needs \(b \lt 2\). The ordered candidates are
$$ (0,0),\ (0,1),\ (1,1). $$
Their invariant values are
$$f(0,0)=0,\qquad f(0,1)=1,\qquad f(1,1)=2.$$
Thus only \((0,0)\) and \((0,1)\) survive the filter \(f\le 1\). The point \((0,0)\) contributes once. For \((0,1)\), the predecessor is
$$\left(1\oplus 0,\ 0\right)=(1,0),$$
which is not ordered, so \((0,1)\) is the canonical seed of its orbit. Iterating forward gives
$$ (0,1)\to(1,2)\to(2,5)\to(5,8)\to\cdots $$
Keeping only terms with second component at most \(5\), we obtain the three valid orbit points \((0,1)\), \((1,2)\), and \((2,5)\). Therefore
$$C(5,1)=1+3=4.$$
The C++, Python, and Java implementations all follow the same high-level routine. They first handle the degenerate case \(m=0\), where the only admissible pair is \((0,0)\). Otherwise they derive the power-of-two seed limit from the binary length of \(m\) and scan every ordered pair in that seed box.
For each candidate, the implementation evaluates the carry-less quadratic form and discards the pair immediately if the value exceeds \(m\). Among the survivors, \((0,0)\) is counted directly, while every other pair is checked against the predecessor condition \(b\oplus(2a)\le a\). If that inequality holds, the pair is an interior orbit point and is skipped; if it fails, the pair is the unique canonical seed of its orbit.
From each canonical seed, the implementation repeatedly applies the orbit recurrence, increments the answer once per visited state, and stops as soon as the second component becomes larger than \(n\). Because the invariant is preserved, the forward walk needs only the bound check on \(b\).
Let
$$S=2^{\lceil(d+1)/2\rceil},$$
where \(d\) is the number of binary digits of \(m\) for \(m>0\). Scanning the seed region visits all ordered pairs with \(0\le a\le b\lt S\), so this stage costs \(O(S^2)\) time. If \(T\) denotes the total number of forward orbit steps whose second component remains at most \(n\), the full running time is
$$O(S^2+T).$$
The algorithm stores only a constant number of integers while scanning and walking the orbits, so its auxiliary memory usage is
$$O(1).$$
Sei \(\otimes\) die carry-less Multiplikation nichtnegativer ganzer Zahlen, also die Multiplikation ihrer Binärdarstellungen als Polynome über \(\mathbb{F}_2\), und \(\oplus\) das bitweise XOR. Die quadratische Form der Aufgabe lautet
$$f(a,b)=a\otimes a \oplus \left(2\otimes a\otimes b\right)\oplus b\otimes b.$$
Für gegebene Schranken \(n\) und \(m\) ist zu zählen:
$$C(n,m)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2: 0\le a\le b\le n,\ f(a,b)\le m\right\}.$$
Eine direkte Enumeration würde ungefähr \(n^2/2\) geordnete Paare prüfen und ist für die echten Parameter aussichtslos. Stattdessen nutzt die Lösung eine Orbitstruktur mit Invariante und zählt pro Orbit nur einen kanonischen Startpunkt.
Der entscheidende Schritt ist die Interpretation der Binärzahlen als Polynome über \(\mathbb{F}_2\). In dieser Sicht wird die in den Implementierungen verwendete Rekurrenz transparent, und die Erhaltung der quadratischen Form lässt sich direkt nachrechnen.
Schreibe die Binärdarstellungen von \(a\) und \(b\) als
$$A(t)=\sum_{i\ge 0} a_i t^i,\qquad B(t)=\sum_{i\ge 0} b_i t^i,$$
wobei die Koeffizienten in \(\mathbb{F}_2\) liegen. Dann entspricht XOR der Polynomaddition und carry-less Multiplikation der gewöhnlichen Polynommultiplikation. Damit ist \(f(a,b)\) die Binärkodierung von
$$Q(A,B)=A(t)^2+tA(t)B(t)+B(t)^2.$$
Der Faktor \(2\) der Ganzzahlformel wird zu \(t\), weil eine Linksverschiebung um ein Bit genau der Multiplikation mit \(t\) entspricht.
Betrachte die Abbildung
$$T(A,B)=\left(B,\ tB+A\right).$$
In Ganzzahlschreibweise ist das
$$T(a,b)=\left(b,\ (2b)\oplus a\right).$$
Setzt man dies in die quadratische Form ein, erhält man
$$\begin{aligned} Q(T(A,B))&=B^2+tB(tB+A)+(tB+A)^2 \\ &=B^2+t^2B^2+tAB+t^2B^2+A^2 \\ &=A^2+tAB+B^2 \\ &=Q(A,B). \end{aligned}$$
Der Wert \(f(a,b)\) bleibt also entlang der gesamten durch \(T\) erzeugten Bahn konstant. Jedes zulässige Paar liegt auf genau einem solchen invarianten Orbit.
Die inverse Abbildung folgt aus \(T(x,y)=(a,b)\). Da \(a=y\) und \(b=2y\oplus x\), ist der Vorgänger von \((a,b)\)
$$T^{-1}(a,b)=\left(b\oplus(2a),\ a\right).$$
Ist dieser Vorgänger noch geordnet, also
$$b\oplus(2a)\le a,$$
dann ist \((a,b)\) nicht der erste geordnete Punkt seines Orbits und darf nicht als Seed gezählt werden. Ein nichtverschwindendes geordnetes Paar ist daher genau dann ein kanonischer Startpunkt, wenn
$$b\oplus(2a) > a.$$
Damit verschwindet die Mehrfachzählung: Pro Orbit bleibt genau ein geordneter Repräsentant übrig. Das Paar \((0,0)\) ist ein Sonderfall, weil es ein Fixpunkt ist und direkt gezählt wird.
Hat \(m>0\) genau \(d\) Binärstellen, dann durchsuchen die Implementierungen nur geordnete Paare mit
$$0\le a\le b \lt 2^{\lceil(d+1)/2\rceil}.$$
Das ist ein sicherer endlicher Suchraum für Seeds. Intuitiv ist \(f(a,b)\) eine quadratische carry-less Form, deren Bitlänge ungefähr doppelt so groß ist wie die Bitlänge der Eingabeskala. Liegt \(b\) oberhalb dieser Schwelle, kann ein geordneter Seed keinen Invariantenwert \(\le m\) mehr besitzen und also nicht zum Ergebnis beitragen.
Von einem kanonischen Seed aus wird wiederholt
$$ (a,b)\mapsto \left(b,\ (2b)\oplus a\right) $$
angewendet. Für geordnete nichtnegative Paare ist die neue zweite Komponente strikt größer als die alte: Das höchste Bit von \(2b\) liegt eine Position über allen Bits von \(a\) und kann daher durch XOR mit \(a\) nicht verschwinden. Die Bahn wächst also streng in \(b\), und wir müssen nur zählen, wie viele Orbitpunkte
$$b\le n$$
erfüllen. Eine erneute Prüfung von \(f(a,b)\) ist während dieses Laufes nicht nötig, weil die Invariante konstant bleibt.
Hier hat \(m\) genau eine Binärstelle, also genügt die Seedsuche mit \(b \lt 2\). Die geordneten Kandidaten sind
$$ (0,0),\ (0,1),\ (1,1). $$
Ihre Invariantenwerte lauten
$$f(0,0)=0,\qquad f(0,1)=1,\qquad f(1,1)=2.$$
Damit bestehen nur \((0,0)\) und \((0,1)\) die Bedingung \(f\le 1\). Der Punkt \((0,0)\) zählt einmal. Für \((0,1)\) ist der Vorgänger
$$\left(1\oplus 0,\ 0\right)=(1,0),$$
also nicht geordnet; folglich ist \((0,1)\) der kanonische Seed seines Orbits. Vorwärts iteriert man
$$ (0,1)\to(1,2)\to(2,5)\to(5,8)\to\cdots $$
Unter der Bedingung, dass die zweite Komponente höchstens \(5\) sein darf, bleiben die drei gültigen Orbitpunkte \((0,1)\), \((1,2)\) und \((2,5)\). Daher gilt
$$C(5,1)=1+3=4.$$
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Grundstruktur. Zuerst behandeln sie den degenerierten Fall \(m=0\), in dem nur \((0,0)\) zulässig ist. Andernfalls wird aus der Binärlänge von \(m\) die Zweierpotenz als Seedgrenze bestimmt und jedes geordnete Paar in diesem Seedkasten durchlaufen.
Für jeden Kandidaten berechnet die Implementierung den Wert der carry-less quadratischen Form und verwirft das Paar sofort, falls der Wert größer als \(m\) ist. Unter den verbleibenden Kandidaten wird \((0,0)\) direkt gezählt, während jedes andere Paar mit der Vorgängerbedingung \(b\oplus(2a)\le a\) geprüft wird. Gilt sie, dann liegt ein innerer Orbitpunkt vor; gilt sie nicht, dann ist das Paar der eindeutige kanonische Seed seines Orbits.
Von jedem kanonischen Seed aus wird die Orbit-Rekurrenz wiederholt angewendet, der Zähler pro erreichtem Zustand um eins erhöht und abgebrochen, sobald die zweite Komponente größer als \(n\) wird. Da die Invariante erhalten bleibt, ist in dieser Vorwärtsphase nur noch die Schranke für \(b\) relevant.
Sei
$$S=2^{\lceil(d+1)/2\rceil},$$
wobei \(d\) die Anzahl der Binärstellen von \(m\) für \(m>0\) ist. Das Durchmustern des Seedbereichs besucht alle geordneten Paare mit \(0\le a\le b\lt S\) und kostet daher \(O(S^2)\) Zeit. Bezeichnet \(T\) die Gesamtzahl der Vorwärtsschritte auf Orbits, deren zweite Komponente höchstens \(n\) bleibt, so beträgt die gesamte Laufzeit
$$O(S^2+T).$$
Während der Suche und des Orbitlaufs werden nur konstant viele Ganzzahlen gehalten; der zusätzliche Speicherbedarf ist also
$$O(1).$$
\(\otimes\) işlemi, negatif olmayan tamsayıların ikili açılımlarını \(\mathbb{F}_2\) üzerindeki polinomlar gibi çarparak tanımlanan carry-less çarpımdır; \(\oplus\) ise bit düzeyinde XOR işlemidir. Sorudaki kuadratik form
$$f(a,b)=a\otimes a \oplus \left(2\otimes a\otimes b\right)\oplus b\otimes b$$
şeklindedir. Verilen \(n\) ve \(m\) için istenen sayı
$$C(n,m)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2: 0\le a\le b\le n,\ f(a,b)\le m\right\}.$$
Doğrudan sayım yaklaşık \(n^2/2\) adet sıralı çift gerektirir ve gerçek girişte uygulanamaz. Çözüm bunun yerine çiftleri sabit bir değişmeze sahip orbitlere ayırır ve her orbiti tek bir kanonik tohum üzerinden sayar.
Temel fikir, ikili tamsayıları \(\mathbb{F}_2\) üzerinde polinom gibi okumaktır. Bu bakış açısı altında carry-less çarpım sıradan polinom çarpımına dönüşür; böylece kullanılan reküransın neden doğru olduğu açık hale gelir.
\(a\) ve \(b\) sayılarının ikili açılımlarını
$$A(t)=\sum_{i\ge 0} a_i t^i,\qquad B(t)=\sum_{i\ge 0} b_i t^i$$
şeklinde düşünelim. Burada katsayılar \(\mathbb{F}_2\) içindedir. Bu durumda XOR, polinom toplaması; carry-less çarpım ise normal polinom çarpımı olur. Dolayısıyla \(f(a,b)\), aslında şu polinomun ikili kodlanmış halidir:
$$Q(A,B)=A(t)^2+tA(t)B(t)+B(t)^2.$$
Tamsayı formülündeki \(2\) katsayısı burada \(t\)'ye karşılık gelir; çünkü sola bir bit kaydırmak, polinomu \(t\) ile çarpmaktır.
Şu dönüşümü ele alalım:
$$T(A,B)=\left(B,\ tB+A\right).$$
Bunun tamsayı karşılığı tam olarak
$$T(a,b)=\left(b,\ (2b)\oplus a\right)$$
olur. Bu dönüşümden sonra kuadratik formun değeri
$$\begin{aligned} Q(T(A,B))&=B^2+tB(tB+A)+(tB+A)^2 \\ &=B^2+t^2B^2+tAB+t^2B^2+A^2 \\ &=A^2+tAB+B^2 \\ &=Q(A,B) \end{aligned}$$
şeklinde aynı kalır. Yani \(f(a,b)\) değeri, \(T\) uygulanarak oluşan tüm orbit boyunca sabittir. Her uygun çift, tek bir değişmez orbitin üzerindedir.
Ters dönüşüm, \(T(x,y)=(a,b)\) denklemi çözülerek bulunur. \(a=y\) ve \(b=2y\oplus x\) olduğundan, \((a,b)\) çiftinin bir önceki noktası
$$T^{-1}(a,b)=\left(b\oplus(2a),\ a\right)$$
olur. Eğer bu önceki nokta da sıralıysa, yani
$$b\oplus(2a)\le a,$$
o zaman \((a,b)\) aynı orbitte daha önce gelen bir sıralı noktanın devamıdır; dolayısıyla tohum değildir. Bu yüzden sıfırdan farklı bir sıralı çift ancak şu koşulda kanonik tohum kabul edilir:
$$b\oplus(2a) > a.$$
Böylece her orbitten tam bir tane sıralı temsilci kalır. \((0,0)\) çifti ayrı ele alınır; çünkü sabit noktadır ve doğrudan bir katkı yapar.
Eğer \(m>0\) sayısının ikili gösteriminde \(d\) bit varsa, uygulamalar yalnızca
$$0\le a\le b \lt 2^{\lceil(d+1)/2\rceil}$$
koşulunu sağlayan sıralı çiftleri tarar. Bu, tohumlar için güvenli sonlu aralıktır. Sezgi şudur: \(f(a,b)\) carry-less anlamda kuadratik bir ifadedir; dolayısıyla bit uzunluğu, girişlerin bit uzunluğunun yaklaşık iki katı mertebesindedir. \(b\) bu eşikten büyüdüğünde, sıralı bir tohumun değişmez değeri artık \(m\)'yi aşar.
Kanonik bir tohumdan başlanıp tekrar tekrar
$$ (a,b)\mapsto \left(b,\ (2b)\oplus a\right) $$
uygulanır. Sıralı ve negatif olmayan çiftlerde yeni ikinci bileşen her zaman eskisinden büyüktür; çünkü \(2b\)'nin en yüksek biti, \(a\)'nın bütün bitlerinden bir konum daha yukarıdadır ve XOR ile yok edilemez. Bu nedenle orbit boyunca \(b\) değeri sıkı biçimde artar ve yapılacak iş,
$$b\le n$$
koşulunu sağlayan orbit noktalarının sayısını toplamaktır. Orbit içinde \(f(a,b)\) sabit kaldığı için ileri yürüyüşte ayrıca değer testi gerekmez.
Burada \(m\) yalnızca bir bit uzunluğundadır; dolayısıyla tohum taraması için \(b \lt 2\) yeterlidir. Sıralı adaylar
$$ (0,0),\ (0,1),\ (1,1) $$
çiftleridir. Bunların değişmez değerleri
$$f(0,0)=0,\qquad f(0,1)=1,\qquad f(1,1)=2$$
olur. Böylece yalnızca \((0,0)\) ve \((0,1)\) filtreden geçer. \((0,0)\) bir kez sayılır. \((0,1)\) için geri adım
$$\left(1\oplus 0,\ 0\right)=(1,0)$$
olur; bu çift sıralı olmadığı için \((0,1)\) kendi orbitinin kanonik tohumudur. İleri doğru gidersek
$$ (0,1)\to(1,2)\to(2,5)\to(5,8)\to\cdots $$
elde edilir. İkinci bileşeni en fazla \(5\) olan noktalar \((0,1)\), \((1,2)\) ve \((2,5)\) olduğundan sonuç
$$C(5,1)=1+3=4$$
çıkar.
C++, Python ve Java uygulamaları aynı ana akışı izler. Önce \(m=0\) özel durumu ele alınır; bu durumda tek geçerli çift \((0,0)\)'dır. Aksi halde \(m\)'nin bit uzunluğundan iki kuvveti biçimindeki tohum sınırı üretilir ve bu kutu içindeki tüm sıralı çiftler taranır.
Her aday için carry-less kuadratik form hesaplanır; değer \(m\)'den büyükse çift anında elenir. Kalan adaylarda \((0,0)\) doğrudan sayılır. Diğer tüm çiftlerde ise \(b\oplus(2a)\le a\) öncül testi uygulanır. Bu koşul doğruysa nokta orbitin iç kısmındadır ve atlanır; yanlışsa o çift kendi orbitinin tek kanonik tohumu olur.
Her kanonik tohumdan başlayarak orbit reküransı art arda uygulanır, her geçerli durumda sayaç bir artırılır ve ikinci bileşen \(n\)'yi aşınca yürüyüş durur. Değişmez korunduğu için bu aşamada yalnızca \(b\) üst sınırını kontrol etmek yeterlidir.
Şunu tanımlayalım:
$$S=2^{\lceil(d+1)/2\rceil},$$
burada \(d\), \(m>0\) için \(m\)'nin bit uzunluğudur. Tohum bölgesinin taranması, \(0\le a\le b\lt S\) olan tüm sıralı çiftleri ziyaret ettiği için \(O(S^2)\) zaman alır. Eğer ikinci bileşeni \(n\)'yi aşmayan toplam ileri orbit adımı sayısı \(T\) ise toplam çalışma süresi
$$O(S^2+T)$$
olur. Algoritma tarama ve orbit yürüyüşü sırasında yalnızca sabit sayıda tamsayı tuttuğu için yardımcı bellek kullanımı
$$O(1)$$
düzeyindedir.
Sea \(\otimes\) la multiplicación carry-less sobre enteros no negativos, es decir, la multiplicación de sus expansiones binarias como polinomios sobre \(\mathbb{F}_2\), y sea \(\oplus\) el XOR bit a bit. La forma cuadrática del problema es
$$f(a,b)=a\otimes a \oplus \left(2\otimes a\otimes b\right)\oplus b\otimes b.$$
Dados \(n\) y \(m\), debemos contar
$$C(n,m)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2: 0\le a\le b\le n,\ f(a,b)\le m\right\}.$$
Una búsqueda directa revisaría del orden de \(n^2/2\) pares ordenados, algo inviable para el caso real. La solución agrupa los pares en órbitas con el mismo invariante y cuenta cada órbita una sola vez a partir de una semilla canónica.
La idea central es reinterpretar los enteros binarios como polinomios sobre \(\mathbb{F}_2\). En ese lenguaje, la multiplicación carry-less se vuelve multiplicación ordinaria de polinomios y la recurrencia usada por la implementación aparece de forma natural.
Escribimos las expansiones binarias de \(a\) y \(b\) como
$$A(t)=\sum_{i\ge 0} a_i t^i,\qquad B(t)=\sum_{i\ge 0} b_i t^i,$$
con coeficientes en \(\mathbb{F}_2\). Bajo esta identificación, XOR es suma de polinomios y la multiplicación carry-less es multiplicación ordinaria. Por tanto, la cantidad entera \(f(a,b)\) codifica el polinomio
$$Q(A,B)=A(t)^2+tA(t)B(t)+B(t)^2.$$
El factor \(2\) pasa a ser \(t\), porque desplazar un número binario una posición a la izquierda equivale a multiplicar su polinomio por \(t\).
Consideremos la aplicación
$$T(A,B)=\left(B,\ tB+A\right).$$
En enteros, esto es exactamente
$$T(a,b)=\left(b,\ (2b)\oplus a\right).$$
Al sustituir en la forma cuadrática obtenemos
$$\begin{aligned} Q(T(A,B))&=B^2+tB(tB+A)+(tB+A)^2 \\ &=B^2+t^2B^2+tAB+t^2B^2+A^2 \\ &=A^2+tAB+B^2 \\ &=Q(A,B). \end{aligned}$$
Así, el valor \(f(a,b)\) permanece constante a lo largo de toda la órbita generada por \(T\). Cada par admisible pertenece a una única órbita de nivel fijo.
La transformación inversa se obtiene resolviendo \(T(x,y)=(a,b)\). Como \(a=y\) y \(b=2y\oplus x\), el predecesor de \((a,b)\) es
$$T^{-1}(a,b)=\left(b\oplus(2a),\ a\right).$$
Si ese predecesor sigue siendo ordenado, es decir, si
$$b\oplus(2a)\le a,$$
entonces \((a,b)\) no es el primer punto ordenado de su órbita y no debe contarse como semilla. Por lo tanto, un par ordenado no nulo es una semilla canónica exactamente cuando
$$b\oplus(2a) > a.$$
Esta regla elimina el doble conteo: sobrevive un único representante ordenado por órbita. El caso \((0,0)\) se trata aparte porque es un punto fijo.
Si \(m>0\) tiene \(d\) dígitos binarios, las implementaciones solo recorren pares ordenados con
$$0\le a\le b \lt 2^{\lceil(d+1)/2\rceil}.$$
Ese es un dominio finito seguro para las semillas. La intuición es que \(f(a,b)\) es una forma cuadrática carry-less, así que su longitud binaria crece aproximadamente como el doble de la longitud binaria de la escala de entrada. Cuando \(b\) supera ese umbral, una semilla ordenada ya no puede producir un valor invariante menor o igual que \(m\).
Desde una semilla canónica se aplica repetidamente
$$ (a,b)\mapsto \left(b,\ (2b)\oplus a\right). $$
Para pares ordenados no negativos, la nueva segunda componente es estrictamente mayor que la anterior: el bit más alto de \(2b\) está una posición por encima de cualquier bit de \(a\), de modo que el XOR con \(a\) no puede cancelarlo. Por eso la caminata por la órbita crece estrictamente en \(b\), y solo hay que contar cuántos estados cumplen
$$b\le n.$$
No hace falta volver a comprobar \(f(a,b)\) durante este avance, porque el invariante permanece constante.
Aquí \(m\) tiene un único dígito binario, así que basta con explorar semillas con \(b \lt 2\). Los candidatos ordenados son
$$ (0,0),\ (0,1),\ (1,1). $$
Sus valores invariantes son
$$f(0,0)=0,\qquad f(0,1)=1,\qquad f(1,1)=2.$$
Por tanto, solo \((0,0)\) y \((0,1)\) pasan el filtro \(f\le 1\). El punto \((0,0)\) aporta una unidad. Para \((0,1)\), el predecesor es
$$\left(1\oplus 0,\ 0\right)=(1,0),$$
que no está ordenado, así que \((0,1)\) es la semilla canónica de su órbita. Al iterar hacia adelante obtenemos
$$ (0,1)\to(1,2)\to(2,5)\to(5,8)\to\cdots $$
Manteniendo solo los términos con segunda componente a lo sumo \(5\), contamos \((0,1)\), \((1,2)\) y \((2,5)\). En consecuencia,
$$C(5,1)=1+3=4.$$
Las implementaciones en C++, Python y Java siguen la misma estructura general. Primero resuelven el caso degenerado \(m=0\), donde únicamente \((0,0)\) es válido. En caso contrario, calculan un límite de búsqueda, potencia de dos, a partir de la longitud binaria de \(m\), y recorren todos los pares ordenados del cuadro de semillas.
Para cada candidato, la implementación evalúa la forma cuadrática carry-less y descarta de inmediato el par si su valor supera \(m\). Entre los supervivientes, \((0,0)\) se suma directamente. Cada otro par se somete a la prueba del predecesor \(b\oplus(2a)\le a\). Si la desigualdad se cumple, el punto ya pertenece al interior de una órbita que empezó antes; si falla, el par es la única semilla canónica de su órbita.
Desde cada semilla canónica, la implementación avanza con la recurrencia de la órbita, incrementa la respuesta una vez por cada estado visitado y se detiene cuando la segunda componente supera \(n\). Como el invariante se conserva, durante ese recorrido solo hay que controlar la cota de \(b\).
Sea
$$S=2^{\lceil(d+1)/2\rceil},$$
donde \(d\) es el número de dígitos binarios de \(m\) cuando \(m>0\). El recorrido de la región de semillas visita todos los pares ordenados con \(0\le a\le b\lt S\), por lo que cuesta \(O(S^2)\) tiempo. Si \(T\) denota el número total de pasos hacia adelante en las órbitas cuya segunda componente permanece como mucho en \(n\), el tiempo total es
$$O(S^2+T).$$
El algoritmo mantiene solo una cantidad constante de enteros durante el barrido y el avance por las órbitas, así que el uso de memoria auxiliar es
$$O(1).$$
记 \(\otimes\) 为非负整数上的 carry-less 乘法，也就是把二进制展开看成 \(\mathbb{F}_2\) 上的多项式后做普通乘法；记 \(\oplus\) 为按位 XOR。题目中的二次型为
$$f(a,b)=a\otimes a \oplus \left(2\otimes a\otimes b\right)\oplus b\otimes b.$$
给定 \(n\) 与 \(m\)，要求统计
$$C(n,m)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2: 0\le a\le b\le n,\ f(a,b)\le m\right\}.$$
如果直接枚举，需要检查大约 \(n^2/2\) 个满足 \(a\le b\) 的整数对，在真实参数下完全不可行。实现采用的方法是把所有点按照同一个不变量分成若干轨道，然后每条轨道只从一个规范种子出发计数。
这道题最重要的观察是：carry-less 算术本质上就是 \(\mathbb{F}_2\) 上的多项式算术。一旦把整数改写成多项式，轨道递推的来源、为何能保持不变量、以及为什么只需要枚举很小的种子区域，都会变得清楚。
把 \(a\) 和 \(b\) 的二进制表示写成
$$A(t)=\sum_{i\ge 0} a_i t^i,\qquad B(t)=\sum_{i\ge 0} b_i t^i,$$
其中系数都属于 \(\mathbb{F}_2\)。在这个对应下，XOR 就是多项式加法，carry-less 乘法就是普通多项式乘法。因此，整数值 \(f(a,b)\) 对应的其实是下面这个多项式的二进制编码：
$$Q(A,B)=A(t)^2+tA(t)B(t)+B(t)^2.$$
整数公式中的系数 \(2\) 之所以变成 \(t\)，是因为二进制左移一位等价于多项式乘以 \(t\)。
考虑映射
$$T(A,B)=\left(B,\ tB+A\right).$$
对应到整数后，它正是
$$T(a,b)=\left(b,\ (2b)\oplus a\right).$$
把这个变换代入二次型，可以直接算出
$$\begin{aligned} Q(T(A,B))&=B^2+tB(tB+A)+(tB+A)^2 \\ &=B^2+t^2B^2+tAB+t^2B^2+A^2 \\ &=A^2+tAB+B^2 \\ &=Q(A,B). \end{aligned}$$
也就是说，沿着同一条轨道不断应用 \(T\) 时，\(f(a,b)\) 的值始终不变。于是原问题可以理解为：先找出所有不变量不超过 \(m\) 的规范轨道起点，再统计这些轨道在 \(b\le n\) 范围内有多少个点。
要求当前点 \((a,b)\) 的前驱，只需解方程 \(T(x,y)=(a,b)\)。由于 \(a=y\) 且 \(b=2y\oplus x\)，所以前驱是
$$T^{-1}(a,b)=\left(b\oplus(2a),\ a\right).$$
如果这个前驱仍然满足有序条件，也就是
$$b\oplus(2a)\le a,$$
那么当前点就不是该轨道上第一个满足 \(0\le a\le b\) 的点，不能作为种子保留。于是，一个非零有序点恰好在下面这个条件成立时才是规范种子：
$$b\oplus(2a) > a.$$
这样做的结果是，每条轨道只保留一个有序代表点。至于 \((0,0)\)，它本身就是不动点，需要单独直接计数。
如果 \(m>0\) 的二进制长度为 \(d\)，那么实现只扫描满足
$$0\le a\le b \lt 2^{\lceil(d+1)/2\rceil}$$
的有序整数对。这是一个安全的有限种子区域。直观地说，\(f(a,b)\) 是一个 carry-less 二次型，它产生的结果位数大约是输入位数的两倍量级。因此，当 \(b\) 超过这个阈值后，一个有序种子的轨道不变量就不可能还小于等于 \(m\) 了。
从任意一个规范种子出发，反复应用
$$ (a,b)\mapsto \left(b,\ (2b)\oplus a\right). $$
对于有序非负整数对，新得到的第二个分量一定严格大于旧的第二个分量。原因是 \(2b\) 的最高位比 \(a\) 的任何一位都高一层，因此与 \(a\) 做 XOR 时不可能被消掉。这样一来，沿轨道前进时 \(b\) 会严格递增，我们只需数清楚有多少个轨道点满足
$$b\le n.$$
由于 \(f(a,b)\) 沿轨道保持不变，所以在前向推进阶段不必重复计算是否仍然满足 \(f(a,b)\le m\)。
这里 \(m\) 的二进制长度是 \(1\)，所以只需要扫描 \(b \lt 2\) 的种子。所有有序候选点是
$$ (0,0),\ (0,1),\ (1,1). $$
它们对应的不变量分别为
$$f(0,0)=0,\qquad f(0,1)=1,\qquad f(1,1)=2.$$
因此只有 \((0,0)\) 与 \((0,1)\) 通过 \(f\le 1\) 的筛选。\((0,0)\) 贡献 \(1\) 个解。对 \((0,1)\) 来说，它的前驱是
$$\left(1\oplus 0,\ 0\right)=(1,0),$$
这不满足有序条件，所以 \((0,1)\) 正是该轨道的规范种子。继续向前迭代可得
$$ (0,1)\to(1,2)\to(2,5)\to(5,8)\to\cdots $$
其中第二个分量不超过 \(5\) 的点只有 \((0,1)\)、\((1,2)\)、\((2,5)\)。因此
$$C(5,1)=1+3=4.$$
C++、Python 和 Java 三个实现遵循同一套流程。首先单独处理 \(m=0\) 的退化情况，因为这时唯一可行的点就是 \((0,0)\)。如果 \(m>0\)，实现就根据 \(m\) 的二进制位数构造一个二的幂边界，只在这个种子方框内枚举所有满足 \(0\le a\le b\) 的候选对。
对每个候选点，程序先计算 carry-less 二次型的值；若该值大于 \(m\)，立即丢弃。剩下的点里，\((0,0)\) 直接加入答案，其余点都要做一次前驱判定 \(b\oplus(2a)\le a\)。如果不等式成立，说明当前点只是某条轨道中的中间点，之前已经有更早的有序点；如果不成立，当前点就是这条轨道唯一的规范种子。
一旦确定了规范种子，实现就不断应用轨道递推，每访问一个满足范围条件的状态就把答案加一，并在第二个分量超过 \(n\) 时停止。因为轨道上的不变量完全相同，所以前向推进时只需要检查 \(b\) 的上界，不需要重新做 \(f(a,b)\le m\) 的判断。
设
$$S=2^{\lceil(d+1)/2\rceil},$$
其中 \(d\) 是 \(m>0\) 时 \(m\) 的二进制位数。种子区域的枚举会访问所有满足 \(0\le a\le b\lt S\) 的有序点，因此这一部分的时间复杂度是 \(O(S^2)\)。如果把所有轨道前向推进中满足第二个分量不超过 \(n\) 的状态总数记为 \(T\)，那么整体时间复杂度就是
$$O(S^2+T).$$
在整个过程中，算法只维护常数个整数状态，所以辅助空间复杂度为
$$O(1).$$
Пусть \(\otimes\) обозначает carry-less умножение неотрицательных целых чисел, то есть умножение их двоичных записей как многочленов над \(\mathbb{F}_2\), а \(\oplus\) обозначает побитовый XOR. Квадратичная форма в задаче имеет вид
$$f(a,b)=a\otimes a \oplus \left(2\otimes a\otimes b\right)\oplus b\otimes b.$$
Для заданных границ \(n\) и \(m\) нужно подсчитать
$$C(n,m)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2: 0\le a\le b\le n,\ f(a,b)\le m\right\}.$$
Прямой перебор потребовал бы проверки примерно \(n^2/2\) упорядоченных пар, что для реального входа недопустимо. Поэтому решение разбивает все точки на орбиты с общим инвариантом и считает каждую орбиту только один раз, начиная с канонического зерна.
Главное наблюдение состоит в том, что carry-less арифметика является обычной арифметикой многочленов над \(\mathbb{F}_2\). После такого переписывания сразу становится понятна рекуррентная формула из реализации и легко проверяется сохраняемый инвариант.
Пусть двоичные записи \(a\) и \(b\) соответствуют многочленам
$$A(t)=\sum_{i\ge 0} a_i t^i,\qquad B(t)=\sum_{i\ge 0} b_i t^i,$$
где коэффициенты лежат в \(\mathbb{F}_2\). Тогда XOR превращается в сложение многочленов, а carry-less умножение совпадает с обычным умножением. Следовательно, целочисленная величина \(f(a,b)\) кодирует многочлен
$$Q(A,B)=A(t)^2+tA(t)B(t)+B(t)^2.$$
Коэффициент \(2\) из целочисленной записи становится множителем \(t\), потому что сдвиг влево на один бит равносилен умножению многочлена на \(t\).
Рассмотрим преобразование
$$T(A,B)=\left(B,\ tB+A\right).$$
В терминах целых чисел оно выглядит как
$$T(a,b)=\left(b,\ (2b)\oplus a\right).$$
Подстановка в квадратичную форму даёт
$$\begin{aligned} Q(T(A,B))&=B^2+tB(tB+A)+(tB+A)^2 \\ &=B^2+t^2B^2+tAB+t^2B^2+A^2 \\ &=A^2+tAB+B^2 \\ &=Q(A,B). \end{aligned}$$
То есть значение \(f(a,b)\) постоянно на всей орбите, получаемой повторным применением \(T\). Каждая допустимая пара лежит ровно на одной такой орбите инварианта.
Обратное преобразование получается из уравнения \(T(x,y)=(a,b)\). Поскольку \(a=y\) и \(b=2y\oplus x\), предшественник точки \((a,b)\) равен
$$T^{-1}(a,b)=\left(b\oplus(2a),\ a\right).$$
Если этот предшественник всё ещё упорядочен, то есть выполняется
$$b\oplus(2a)\le a,$$
значит, текущая точка не является первой упорядоченной точкой своей орбиты и не должна выступать стартом. Поэтому ненулевая упорядоченная пара является каноническим зерном тогда и только тогда, когда
$$b\oplus(2a) > a.$$
Это полностью убирает повторный счёт: для каждой орбиты остаётся ровно один упорядоченный представитель. Пара \((0,0)\) рассматривается отдельно, поскольку это неподвижная точка.
Если \(m>0\) имеет \(d\) двоичных цифр, реализации просматривают только упорядоченные пары, удовлетворяющие
$$0\le a\le b \lt 2^{\lceil(d+1)/2\rceil}.$$
Это безопасная конечная область поиска зерен. Интуитивно \(f(a,b)\) является carry-less квадратичной формой, поэтому длина её двоичной записи примерно вдвое больше длины двоичной записи входного масштаба. Как только \(b\) выходит за этот порог, упорядоченное зерно уже не может иметь инвариант не больше \(m\).
От канонического зерна повторно применяется переход
$$ (a,b)\mapsto \left(b,\ (2b)\oplus a\right). $$
Для упорядоченных неотрицательных пар новая вторая компонента строго больше старой: старший бит числа \(2b\) находится на одну позицию выше всех битов числа \(a\), поэтому XOR с \(a\) не может его уничтожить. Значит, при движении по орбите значение \(b\) строго растёт, и остаётся лишь подсчитать число состояний, для которых
$$b\le n.$$
Повторная проверка условия \(f(a,b)\le m\) больше не нужна, поскольку инвариант на орбите сохраняется.
Здесь число \(m\) имеет одну двоичную цифру, поэтому достаточно просканировать зерна с \(b \lt 2\). Упорядоченные кандидаты таковы:
$$ (0,0),\ (0,1),\ (1,1). $$
Их значения инварианта равны
$$f(0,0)=0,\qquad f(0,1)=1,\qquad f(1,1)=2.$$
Следовательно, фильтр \(f\le 1\) проходят только \((0,0)\) и \((0,1)\). Точка \((0,0)\) даёт один вклад. Для \((0,1)\) предшественник равен
$$\left(1\oplus 0,\ 0\right)=(1,0),$$
а это уже неупорядоченная пара, значит \((0,1)\) и есть каноническое зерно своей орбиты. Дальнейшая итерация даёт
$$ (0,1)\to(1,2)\to(2,5)\to(5,8)\to\cdots $$
Среди этих точек условию на вторую компоненту не больше \(5\) соответствуют \((0,1)\), \((1,2)\) и \((2,5)\). Поэтому
$$C(5,1)=1+3=4.$$
Реализации на C++, Python и Java используют одну и ту же схему. Сначала отдельно обрабатывается случай \(m=0\), когда допустима только пара \((0,0)\). В противном случае из двоичной длины числа \(m\) выводится степенная граница для зерен, и затем просматриваются все упорядоченные пары внутри этого прямоугольника.
Для каждого кандидата вычисляется значение carry-less квадратичной формы. Если оно больше \(m\), пара сразу отбрасывается. Среди оставшихся \((0,0)\) учитывается непосредственно, а каждая другая пара проходит проверку предшественника \(b\oplus(2a)\le a\). Если неравенство верно, то точка лежит внутри орбиты и уже была представлена раньше; если неверно, то это единственное каноническое зерно соответствующей орбиты.
От каждого канонического зерна код многократно применяет орбитальную рекурсию, увеличивает ответ на единицу для каждого достигнутого состояния и останавливается, как только вторая компонента становится больше \(n\). Поскольку инвариант сохраняется, на этой стадии нужен только контроль границы по \(b\).
Пусть
$$S=2^{\lceil(d+1)/2\rceil},$$
где \(d\) — число двоичных цифр числа \(m\) при \(m>0\). Просмотр области зерен посещает все упорядоченные пары с \(0\le a\le b\lt S\), поэтому эта часть стоит \(O(S^2)\) времени. Если обозначить через \(T\) суммарное число шагов вперёд по орбитам, для которых вторая компонента не превосходит \(n\), то полное время работы равно
$$O(S^2+T).$$
Алгоритм хранит лишь константное число целых значений при сканировании и движении по орбитам, поэтому дополнительная память составляет
$$O(1).$$
ليكن \(\otimes\) هو الضرب carry-less على الأعداد الصحيحة غير السالبة، أي ضرب التمثيل الثنائي كما لو كان كثيرات حدود فوق \(\mathbb{F}_2\)، وليكن \(\oplus\) هو XOR على مستوى البتات. الصيغة التربيعية في المسألة هي
$$f(a,b)=a\otimes a \oplus \left(2\otimes a\otimes b\right)\oplus b\otimes b.$$
لحدَّين معطيين \(n\) و\(m\)، نريد حساب
$$C(n,m)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2: 0\le a\le b\le n,\ f(a,b)\le m\right\}.$$
العد المباشر يحتاج إلى فحص ما يقارب \(n^2/2\) من الأزواج المرتبة، وهذا غير عملي تمامًا عند القيم الحقيقية. لذلك تعتمد الفكرة على تقسيم الأزواج إلى مدارات لها نفس الثابت، ثم عد كل مدار مرة واحدة فقط انطلاقًا من بذرة قانونية.
الملاحظة الأساسية هي أن حساب carry-less ليس إلا حساب كثيرات حدود فوق \(\mathbb{F}_2\). بعد هذا التحويل تصبح العلاقة التكرارية المستخدمة طبيعية، كما يصبح من السهل إثبات أن قيمة معينة تبقى ثابتة على طول المدار.
لنكتب التمثيل الثنائي للعددين \(a\) و\(b\) على صورة
$$A(t)=\sum_{i\ge 0} a_i t^i,\qquad B(t)=\sum_{i\ge 0} b_i t^i,$$
حيث المعاملات من \(\mathbb{F}_2\). تحت هذا التفسير يصبح XOR هو جمع كثيرات الحدود، ويصبح الضرب carry-less هو الضرب العادي. لذلك فإن القيمة الصحيحة \(f(a,b)\) هي الترميز الثنائي لكثير الحدود
$$Q(A,B)=A(t)^2+tA(t)B(t)+B(t)^2.$$
أما العامل \(2\) في الصيغة العددية فيتحول إلى \(t\)، لأن الإزاحة إلى اليسار بمقدار بت واحد تكافئ الضرب في \(t\).
لنأخذ التحويل
$$T(A,B)=\left(B,\ tB+A\right).$$
وبلغة الأعداد الصحيحة يصبح هذا بالضبط
$$T(a,b)=\left(b,\ (2b)\oplus a\right).$$
وعند التعويض في الصيغة التربيعية نحصل على
$$\begin{aligned} Q(T(A,B))&=B^2+tB(tB+A)+(tB+A)^2 \\ &=B^2+t^2B^2+tAB+t^2B^2+A^2 \\ &=A^2+tAB+B^2 \\ &=Q(A,B). \end{aligned}$$
إذن تبقى قيمة \(f(a,b)\) ثابتة على طول المدار الناتج عن تكرار \(T\). وهذا يعني أن كل زوج مقبول يقع على مدار واحد فقط ذي قيمة ثابتة للمقدار \(f\).
يمكن إيجاد التحويل العكسي بحل المعادلة \(T(x,y)=(a,b)\). بما أن \(a=y\) و\(b=2y\oplus x\)، فإن السلف للزوج \((a,b)\) هو
$$T^{-1}(a,b)=\left(b\oplus(2a),\ a\right).$$
إذا كان هذا السلف ما يزال مرتبًا، أي إذا تحقق
$$b\oplus(2a)\le a,$$
فإن الزوج الحالي ليس أول نقطة مرتبة في مداره، ولذلك لا يجوز اعتباره بذرة. ومن ثم فإن أي زوج مرتب غير صفري يكون بذرة قانونية إذا وفقط إذا تحقق
$$b\oplus(2a) > a.$$
هذه القاعدة تمنع العد المكرر، إذ يبقى ممثل مرتب واحد فقط لكل مدار. أما \((0,0)\) فهو حالة خاصة لأنه نقطة ثابتة ويُعد مباشرة.
إذا كان \(m>0\) يملك \(d\) خانات ثنائية، فإن التطبيقات لا تمسح إلا الأزواج المرتبة التي تحقق
$$0\le a\le b \lt 2^{\lceil(d+1)/2\rceil}.$$
هذا مجال منتهٍ وآمن للبذور. الفكرة الحدسية هي أن \(f(a,b)\) صيغة تربيعية carry-less، ولذلك فإن طولها الثنائي ينمو تقريبًا بضعف طول المدخلات. وبمجرد أن يصبح \(b\) أكبر من هذا الحد، لا يعود ممكنًا أن ينتج زوج مرتب قيمة ثابتة لا تتجاوز \(m\).
انطلاقًا من أي بذرة قانونية نطبق مرارًا
$$ (a,b)\mapsto \left(b,\ (2b)\oplus a\right). $$
بالنسبة إلى الأزواج المرتبة غير السالبة، يكون الحد الثاني الجديد أكبر قطعًا من الحد الثاني القديم، لأن أعلى بت في \(2b\) يقع فوق جميع بتات \(a\) ولا يمكن لـ XOR مع \(a\) أن يلغيه. لذلك يزداد \(b\) زيادة صارمة على طول المدار، ويكفي أن نحصي عدد الحالات التي تحقق
$$b\le n.$$
ولا حاجة إلى إعادة اختبار الشرط \(f(a,b)\le m\) أثناء هذا التقدم، لأن قيمة الثابت لا تتغير على المدار.
هنا يملك \(m\) خانة ثنائية واحدة فقط، ولذلك يكفي مسح البذور ذات \(b \lt 2\). الأزواج المرتبة المرشحة هي
$$ (0,0),\ (0,1),\ (1,1). $$
وقيم الثابت المقابلة لها هي
$$f(0,0)=0,\qquad f(0,1)=1,\qquad f(1,1)=2.$$
إذن لا يمر من الشرط \(f\le 1\) إلا الزوجان \((0,0)\) و\((0,1)\). الزوج \((0,0)\) يعطي مساهمة واحدة. أما \((0,1)\) فسلفه هو
$$\left(1\oplus 0,\ 0\right)=(1,0),$$
وهذا ليس زوجًا مرتبًا، لذلك يكون \((0,1)\) هو البذرة القانونية لمداره. وبالتقدم إلى الأمام نحصل على
$$ (0,1)\to(1,2)\to(2,5)\to(5,8)\to\cdots $$
ومع شرط أن يكون الحد الثاني على الأكثر \(5\)، تبقى النقاط \((0,1)\) و\((1,2)\) و\((2,5)\). وبالتالي
$$C(5,1)=1+3=4.$$
تتبع تطبيقات C++ وPython وJava البنية نفسها. في البداية تُعالَج الحالة الخاصة \(m=0\)، حيث لا يكون مقبولًا إلا الزوج \((0,0)\). وإذا كان \(m>0\)، فيُستخرج من طول \(m\) الثنائي حد بحث على شكل قوة للعدد \(2\)، ثم تُفحص جميع الأزواج المرتبة داخل صندوق البذور هذا.
لكل زوج مرشح، تحسب البنية التنفيذية قيمة الصيغة التربيعية carry-less، ويُهمَل الزوج فورًا إذا تجاوزت القيمة \(m\). بعد ذلك يُعد \((0,0)\) مباشرة، بينما تخضع بقية الأزواج لاختبار السلف \(b\oplus(2a)\le a\). إذا تحقق هذا الشرط كان الزوج نقطة داخلية في مدار سبق أن بدأ من قبل؛ وإذا لم يتحقق كان الزوج هو البذرة القانونية الوحيدة لذلك المدار.
ومن كل بذرة قانونية، يكرر التنفيذ علاقة المدار، ويزيد الجواب مرة لكل حالة مزارة، ثم يتوقف عندما يصبح الحد الثاني أكبر من \(n\). وبما أن الثابت محفوظ، فالفحص الوحيد اللازم أثناء هذا السير هو حد \(b\).
لنعرّف
$$S=2^{\lceil(d+1)/2\rceil},$$
حيث \(d\) هو عدد الخانات الثنائية لـ \(m\) عندما \(m>0\). إن مسح منطقة البذور يزور كل زوج مرتب يحقق \(0\le a\le b\lt S\)، ولذلك تكلفته الزمنية \(O(S^2)\). وإذا رمزنا بـ \(T\) إلى العدد الكلي لخطوات التقدم على المدارات التي يبقى فيها الحد الثاني في المجال حتى \(n\)، فإن الزمن الكلي يساوي
$$O(S^2+T).$$
ولا تحتفظ الخوارزمية إلا بعدد ثابت من القيم الصحيحة أثناء المسح والتحرك على المدارات، لذا يكون استهلاك الذاكرة الإضافية
$$O(1).$$