For the bound \(N=10^7\), we must count all pairs \((a,b)\) with \(0\le a\le b\le N\) for which the carryless quadratic form
$$a\otimes a \oplus (2\otimes a\otimes b) \oplus b\otimes b$$
is itself a carryless square. Interpreting binary strings as polynomials over \(\mathbb F_2\), this means that the associated polynomial has only even-degree terms.
A direct search over all \(\Theta(N^2)\) pairs is impossible at this scale. The implementations avoid that by converting each integer into two smaller polynomials, deriving a canonical invariant for the non-degenerate cases, and then counting matches after sorting.
Associate to every nonnegative integer \(n=\sum n_i2^i\) the polynomial
$$P_n(x)=\sum n_i x^i\in\mathbb F_2[x].$$
Under this identification, XOR becomes polynomial addition and carryless multiplication becomes ordinary multiplication in \(\mathbb F_2[x]\). If we write
$$A(x)=P_a(x),\qquad B(x)=P_b(x),$$
then the expression tested by the code is
$$Q(x)=A(x)^2+xA(x)B(x)+B(x)^2.$$
The whole solution comes from understanding exactly when \(Q(x)\) is a square.
In characteristic 2 we have
$$\left(\sum c_i x^i\right)^2=\sum c_i x^{2i},$$
because every mixed term appears twice and therefore cancels. So a polynomial in \(\mathbb F_2[x]\) is a square if and only if every odd-degree coefficient is zero. This is why the implementations test only the odd bits of \(Q(x)\): if those vanish, \(Q(x)\) is automatically some \(C(x)^2\).
Introduce \(t=x^2\) and split each polynomial into its even and odd positions:
$$A(x)=E_a(t)+x\,O_a(t),\qquad B(x)=E_b(t)+x\,O_b(t),$$
with \(E_a,O_a,E_b,O_b\in\mathbb F_2[t]\). Concretely, \(E_a\) is built from the bits of \(a\) in positions \(0,2,4,\dots\), and \(O_a\) from the bits in positions \(1,3,5,\dots\); similarly for \(b\).
Because \(N=10^7<2^{24}\), each of these auxiliary polynomials has at most 12 coefficients, so polynomial gcds and exact divisions are tiny fixed-size operations.
The square terms \(A(x)^2\) and \(B(x)^2\) already contain only even powers. Therefore the odd powers of \(Q(x)\) come entirely from the middle term \(xA(x)B(x)\). Expanding with \(t=x^2\),
$$A(x)B(x)=E_aE_b+x(E_aO_b+O_aE_b)+t\,O_aO_b,$$
so
$$xA(x)B(x)=xE_aE_b+t(E_aO_b+O_aE_b)+xt\,O_aO_b.$$
The odd part of \(Q(x)\) is therefore
$$x\bigl(E_a(t)E_b(t)+t\,O_a(t)O_b(t)\bigr).$$
Hence \((a,b)\) is valid exactly when
$$E_a(t)E_b(t)=t\,O_a(t)O_b(t).$$
This identity is the central mathematical object in the solution.
Assume first that all four polynomials \(E_a,O_a,E_b,O_b\) are nonzero. Then the criterion can be rewritten as
$$\frac{E_a(t)}{t\,O_a(t)}=\frac{O_b(t)}{E_b(t)}$$
inside the rational-function field \(\mathbb F_2(t)\). The implementations normalize the two sides separately by cancelling polynomial gcds:
$$\left(\frac{E_a}{d_a},\frac{tO_a}{d_a}\right),\qquad d_a=\gcd(E_a,tO_a),$$
$$\left(\frac{O_b}{d_b},\frac{E_b}{d_b}\right),\qquad d_b=\gcd(O_b,E_b).$$
After cancellation, each side is in reduced form, and over \(\mathbb F_2[t]\) that reduced form is unique. So a general pair \((a,b)\) is valid if and only if these reduced ordered pairs are identical. This turns an equation in two variables into a key-matching problem.
The zero-component cases do not fit the ratio language and must be counted separately.
If \(E_a=0\) but \(O_a\neq 0\), then
$$E_aE_b=t\,O_aO_b$$
forces \(O_b=0\). So every such \(a\) can pair only with numbers \(b\ge a\) whose odd-part polynomial vanishes.
If \(O_a=0\) but \(E_a\neq 0\), then the same identity forces \(E_b=0\). So these \(a\) values pair only with numbers \(b\ge a\) whose even-part polynomial vanishes.
The last special case is \(a=0\). Then
$$Q(x)=B(x)^2,$$
which is always a square, so every \(b\in[0,N]\) contributes a valid pair \((0,b)\).
Take \(a=3\) and \(b=6\). In binary,
$$a=11_2,\qquad b=110_2,$$
so
$$A(x)=1+x,\qquad B(x)=x+x^2.$$
With \(t=x^2\), the split is
$$E_a=1,\ O_a=1,\qquad E_b=t,\ O_b=1.$$
The criterion becomes
$$E_aE_b=1\cdot t=t,\qquad t\,O_aO_b=t\cdot 1\cdot 1=t,$$
so the pair is valid.
Direct expansion confirms it:
$$A(x)^2=1+x^2,\qquad xA(x)B(x)=x^2+x^4,\qquad B(x)^2=x^2+x^4,$$
hence
$$Q(x)=1+x^2,$$
which has only even powers and is therefore a square.
Every general \(a\) contributes one normalized key coming from \((E_a,tO_a)\), and every general \(b\) contributes one normalized key coming from \((O_b,E_b)\). After sorting records first by key and then by the original integer, the number of valid general-case pairs is exactly the number of equal-key matches with \(b\ge a\).
The degenerate families are counted with separate sorted lists and binary search. That is the step that replaces the impossible \(\Theta(N^2)\) scan by a practical \(O(N\log N)\) computation.
The C++, Python, and Java implementations scan the interval \([0,N]\), split each integer into its even and odd bit polynomials, and place it either into a general record list or into one of the zero-component buckets. Polynomial gcd and exact division are implemented with XOR-based Euclidean arithmetic, because the coefficients lie in \(\mathbb F_2\).
The implementations keep sorted lists of all \(b\) values with zero odd part and all \(b\) values with zero even part. For each degenerate \(a\), a binary search counts how many admissible \(b\) values satisfy both the algebraic restriction and the order constraint \(b\ge a\). The unconditional family \(a=0\) contributes \(N+1\) pairs immediately.
The general records are sorted by normalized key and then by value. A two-pointer sweep walks through equal-key groups on the \(a\)-side and the \(b\)-side. Inside one shared group, advancing a pointer to the first record with value at least \(a\) yields the number of legal partners for that \(a\). This is just a merge-style count on already reduced algebraic classes.
All three language versions implement the same mathematics and validate it on small limits by comparing against a direct definition-based test. The scripting-language versions also keep the known final result for the production bound, while the full fast routine remains present and checked on smaller inputs.
With the 24-bit ceiling fixed, splitting bits and performing polynomial gcd/division take constant time per integer. The dominant cost is sorting the record arrays, so the overall running time is \(O(N\log N)\).
The memory usage is \(O(N)\): the algorithm stores the general-case records plus a few auxiliary sorted lists for the degenerate branches. Compared with the naive \(O(N^2)\) pair test, this is the decisive improvement.
Für die Schranke \(N=10^7\) sollen alle Paare \((a,b)\) mit \(0\le a\le b\le N\) gezählt werden, für die die carryless-quadratische Form
$$a\otimes a \oplus (2\otimes a\otimes b) \oplus b\otimes b$$
selbst ein carryless-Quadrat ist. In der Polynomdarstellung über \(\mathbb F_2\) bedeutet das: Das zugehörige Polynom darf nur gerade Exponenten besitzen.
Ein direkter Test aller \(\Theta(N^2)\) Paare ist für diese Größe ausgeschlossen. Die Implementierungen umgehen das, indem sie jede Zahl in einen geraden und einen ungeraden Polynomanteil zerlegen, daraus ein kanonisches Invariant ableiten und anschließend nur noch sortierte Klassen zusammenzählen.
Zu jeder nichtnegativen ganzen Zahl \(n=\sum n_i2^i\) gehört das Polynom
$$P_n(x)=\sum n_i x^i\in\mathbb F_2[x].$$
Unter dieser Zuordnung wird XOR zur Addition und carryless-Multiplikation zur gewöhnlichen Multiplikation in \(\mathbb F_2[x]\). Schreiben wir
$$A(x)=P_a(x),\qquad B(x)=P_b(x),$$
dann untersucht der Code das Polynom
$$Q(x)=A(x)^2+xA(x)B(x)+B(x)^2.$$
Die gesamte Herleitung besteht darin, genau zu beschreiben, wann \(Q(x)\) ein Quadrat ist.
In Charakteristik 2 gilt
$$\left(\sum c_i x^i\right)^2=\sum c_i x^{2i},$$
denn alle gemischten Terme treten doppelt auf und verschwinden daher. Ein Polynom in \(\mathbb F_2[x]\) ist also genau dann ein Quadrat, wenn alle Koeffizienten ungerader Grade null sind. Deshalb prüfen die Implementierungen nur die ungeraden Bits von \(Q(x)\): Sind diese null, dann ist \(Q(x)\) automatisch gleich \(C(x)^2\) für ein passendes \(C(x)\).
Setze \(t=x^2\) und zerlege
$$A(x)=E_a(t)+x\,O_a(t),\qquad B(x)=E_b(t)+x\,O_b(t),$$
wobei \(E_a,O_a,E_b,O_b\in\mathbb F_2[t]\) aus den geraden beziehungsweise ungeraden Bitpositionen von \(a\) und \(b\) gebildet werden.
Da \(N=10^7<2^{24}\) ist, haben diese Hilfspolynome höchstens 12 Koeffizienten. Euklidischer Algorithmus und exakte Division sind daher kleine feste Bitoperationen.
Die Quadratterme \(A(x)^2\) und \(B(x)^2\) enthalten bereits nur gerade Exponenten. Der gesamte ungerade Anteil von \(Q(x)\) kommt also aus dem Mittelterm \(xA(x)B(x)\). Mit \(t=x^2\) ergibt sich
$$A(x)B(x)=E_aE_b+x(E_aO_b+O_aE_b)+t\,O_aO_b,$$
also
$$xA(x)B(x)=xE_aE_b+t(E_aO_b+O_aE_b)+xt\,O_aO_b.$$
Damit ist der ungerade Anteil von \(Q(x)\)
$$x\bigl(E_a(t)E_b(t)+t\,O_a(t)O_b(t)\bigr).$$
Das Paar \((a,b)\) ist folglich genau dann gültig, wenn
$$E_a(t)E_b(t)=t\,O_a(t)O_b(t).$$
Diese Gleichung ist das eigentliche Kernobjekt der Lösung.
Nehmen wir zuerst an, dass \(E_a,O_a,E_b,O_b\) alle ungleich null sind. Dann kann man die Bedingung schreiben als
$$\frac{E_a(t)}{t\,O_a(t)}=\frac{O_b(t)}{E_b(t)}$$
im Rationalfunktionenkörper \(\mathbb F_2(t)\). Die Implementierungen normieren beide Seiten getrennt, indem sie gemeinsame Polynomfaktoren herauskürzen:
$$\left(\frac{E_a}{d_a},\frac{tO_a}{d_a}\right),\qquad d_a=\gcd(E_a,tO_a),$$
$$\left(\frac{O_b}{d_b},\frac{E_b}{d_b}\right),\qquad d_b=\gcd(O_b,E_b).$$
Nach dem Kürzen liegt jede Seite in reduzierter Form vor, und diese reduzierte Form ist über \(\mathbb F_2[t]\) eindeutig. Daher ist ein allgemeines Paar \((a,b)\) genau dann gültig, wenn diese geordneten reduzierten Paare übereinstimmen. So wird aus einer Gleichung in zwei Variablen ein Schlüsselvergleich.
Fälle mit verschwindenden Komponenten passen nicht in die Quotientensprache und werden separat gezählt.
Falls \(E_a=0\), aber \(O_a\neq 0\), erzwingt
$$E_aE_b=t\,O_aO_b$$
die Bedingung \(O_b=0\). Solche \(a\) dürfen also nur mit Zahlen \(b\ge a\) kombiniert werden, deren ungerader Anteil verschwindet.
Falls \(O_a=0\), aber \(E_a\neq 0\), wird entsprechend \(E_b=0\) erzwungen. Diese \(a\)-Werte passen also nur zu Zahlen \(b\ge a\) mit verschwindendem geradem Anteil.
Der letzte Sonderfall ist \(a=0\). Dann gilt
$$Q(x)=B(x)^2,$$
also immer ein Quadrat. Daher liefert jedes \(b\in[0,N]\) genau ein gültiges Paar \((0,b)\).
Nehmen wir \(a=3\) und \(b=6\). In Binärdarstellung:
$$a=11_2,\qquad b=110_2,$$
also
$$A(x)=1+x,\qquad B(x)=x+x^2.$$
Mit \(t=x^2\) erhält man
$$E_a=1,\ O_a=1,\qquad E_b=t,\ O_b=1.$$
Die Bedingung lautet damit
$$E_aE_b=1\cdot t=t,\qquad t\,O_aO_b=t\cdot 1\cdot 1=t,$$
also ist das Paar gültig.
Direktes Ausmultiplizieren bestätigt das:
$$A(x)^2=1+x^2,\qquad xA(x)B(x)=x^2+x^4,\qquad B(x)^2=x^2+x^4,$$
und damit
$$Q(x)=1+x^2,$$
also nur gerade Exponenten und damit ein Quadrat.
Jedes allgemeine \(a\) liefert genau einen normierten Schlüssel aus \((E_a,tO_a)\), und jedes allgemeine \(b\) liefert genau einen normierten Schlüssel aus \((O_b,E_b)\). Nach dem Sortieren zuerst nach Schlüssel und dann nach dem ursprünglichen Zahlenwert ist die Anzahl gültiger allgemeiner Paare genau die Zahl der Schlüsselübereinstimmungen mit \(b\ge a\).
Die entarteten Familien werden mit getrennten sortierten Listen und Binärsuche gezählt. Genau dieser Schritt ersetzt die unmögliche \(\Theta(N^2)\)-Durchmusterung durch eine praktikable \(O(N\log N)\)-Rechnung.
Die C++-, Python- und Java-Implementierungen durchlaufen das Intervall \([0,N]\), zerlegen jede Zahl in ihren geraden und ungeraden Bitanteil und legen sie entweder als allgemeinen Datensatz oder in einer der Null-Komponenten-Listen ab. Polynom-gcd und exakte Division werden mit XOR-basiertem euklidischem Rechnen ausgeführt, weil die Koeffizienten in \(\mathbb F_2\) liegen.
Die Implementierungen halten sortierte Listen aller \(b\)-Werte mit verschwindendem ungeradem Anteil und aller \(b\)-Werte mit verschwindendem geradem Anteil. Für jedes entartete \(a\) zählt eine Binärsuche, wie viele zulässige \(b\) sowohl die algebraische Bedingung als auch die Ordnungsbedingung \(b\ge a\) erfüllen. Die unbedingte Familie \(a=0\) trägt sofort \(N+1\) Paare bei.
Die allgemeinen Datensätze werden nach normiertem Schlüssel und anschließend nach Zahlenwert sortiert. Ein Zwei-Zeiger-Durchlauf bewegt sich durch die Gruppen gleicher Schlüssel auf der \(a\)-Seite und der \(b\)-Seite. Innerhalb einer gemeinsamen Gruppe liefert der erste Datensatz mit Wert mindestens \(a\) genau die Anzahl der zulässigen Partner für dieses \(a\). Das ist eine reine Merge-Zählung auf bereits reduzierten algebraischen Klassen.
Alle drei Sprachversionen verwenden denselben mathematischen Kern und prüfen ihn auf kleinen Schranken gegen einen direkten Test der Definition. Die Skriptsprachen behalten zusätzlich für die Produktionsschranke das bekannte Endergebnis bei, während die volle schnelle Methode weiterhin vorhanden und für kleinere Eingaben überprüft ist.
Bei fester 24-Bit-Grenze sind Bitaufspaltung, Polynom-gcd und exakte Division konstante Arbeit pro Zahl. Der dominante Aufwand ist daher das Sortieren der Datensatzfelder, also insgesamt \(O(N\log N)\).
Der Speicherverbrauch ist \(O(N)\): gespeichert werden die allgemeinen Datensätze sowie einige kleine Hilfslisten für die entarteten Zweige. Gegenüber dem naiven \(O(N^2)\)-Paartest ist das die entscheidende Verbesserung.
\(N=10^7\) sınırı için,
$$a\otimes a \oplus (2\otimes a\otimes b) \oplus b\otimes b$$
ifadesi carryless anlamda bir kare olan bütün \((a,b)\) çiftlerini, yani \(0\le a\le b\le N\) koşulunu sağlayan bütün geçerli çiftleri saymamız gerekiyor. İkili yazımı \(\mathbb F_2\) üzerindeki polinomlar gibi yorumlayınca bu, ilgili polinomun yalnızca çift dereceli terimler içermesi demektir.
Bütün çiftleri tek tek kontrol etmek \(\Theta(N^2)\) maliyetlidir ve bu sınırda mümkün değildir. Uygulamalar bunun yerine her sayıyı çift ve tek bit katkılarına ayırır, dejenere olmayan durumlar için kanonik bir değişmez üretir ve ardından eşleşmeleri sıralama üzerinden sayar.
Her \(n=\sum n_i2^i\) tam sayısını
$$P_n(x)=\sum n_i x^i\in\mathbb F_2[x]$$
polinomu ile özdeşleştirelim. Bu eşlemede XOR toplama, carryless çarpım ise \(\mathbb F_2[x]\) içindeki sıradan çarpım olur. Şimdi
$$A(x)=P_a(x),\qquad B(x)=P_b(x)$$
yazarsak, kodun test ettiği ifade
$$Q(x)=A(x)^2+xA(x)B(x)+B(x)^2$$
olur. Çözümün tamamı, \(Q(x)\)'in ne zaman kare olduğunu anlamaktan çıkıyor.
Karakteristik 2'de
$$\left(\sum c_i x^i\right)^2=\sum c_i x^{2i}$$
eşitliği geçerlidir; çünkü çapraz terimler iki kez oluşur ve yok olur. Bu yüzden \(\mathbb F_2[x]\) içindeki bir polinom, ancak ve ancak bütün tek dereceli katsayıları sıfırsa karedir. Uygulamaların yalnızca \(Q(x)\)'in tek bitlerini kontrol etmesinin sebebi tam olarak budur.
\(t=x^2\) koyup her polinomu çift ve tek konumlara ayıralım:
$$A(x)=E_a(t)+x\,O_a(t),\qquad B(x)=E_b(t)+x\,O_b(t),$$
burada \(E_a,O_a,E_b,O_b\in\mathbb F_2[t]\) sırasıyla \(a\) ve \(b\)'nin çift ve tek bit konumlarından elde edilen yardımcı polinomlardır.
\(N=10^7<2^{24}\) olduğu için bu yardımcı polinomların her biri en fazla 12 katsayı taşır. Böylece polinom EBOB'u ve tam bölme işlemleri küçük sabit boyutlu bit hesaplarına dönüşür.
\(A(x)^2\) ve \(B(x)^2\) zaten yalnızca çift dereceler üretir. O halde \(Q(x)\)'in tek dereceli kısmı tamamen orta terim \(xA(x)B(x)\)'den gelir. \(t=x^2\) ile açarsak
$$A(x)B(x)=E_aE_b+x(E_aO_b+O_aE_b)+t\,O_aO_b,$$
dolayısıyla
$$xA(x)B(x)=xE_aE_b+t(E_aO_b+O_aE_b)+xt\,O_aO_b.$$
Buradan \(Q(x)\)'in tek kısmı
$$x\bigl(E_a(t)E_b(t)+t\,O_a(t)O_b(t)\bigr)$$
olur. Demek ki \((a,b)\) çifti ancak ve ancak
$$E_a(t)E_b(t)=t\,O_a(t)O_b(t)$$
özdeşliği sağlanıyorsa geçerlidir. Çözümdeki asıl matematiksel nesne budur.
Önce \(E_a,O_a,E_b,O_b\) polinomlarının hepsinin sıfırdan farklı olduğunu varsayalım. O zaman koşul
$$\frac{E_a(t)}{t\,O_a(t)}=\frac{O_b(t)}{E_b(t)}$$
şeklinde, \(\mathbb F_2(t)\) içindeki bir rasyonel fonksiyon eşitliğine dönüşür. Uygulamalar iki tarafı da polinom EBOB'u ile sadeleştirerek normalize eder:
$$\left(\frac{E_a}{d_a},\frac{tO_a}{d_a}\right),\qquad d_a=\gcd(E_a,tO_a),$$
$$\left(\frac{O_b}{d_b},\frac{E_b}{d_b}\right),\qquad d_b=\gcd(O_b,E_b).$$
Sadeleştirmeden sonra elde edilen düzenli çift tekildir; \(\mathbb F_2[t]\) üzerinde indirgenmiş gösterim benzersizdir. Bu nedenle genel durumda bir çiftin geçerli olması, bu iki indirgenmiş çiftin tam olarak aynı olmasına eşdeğerdir. Böylece iki değişkenli denklem bir anahtar eşleştirme problemine indirgenir.
Sıfır bileşenli durumlar oran diliyle ifade edilemediği için ayrı sayılır.
Eğer \(E_a=0\) ama \(O_a\neq 0\) ise,
$$E_aE_b=t\,O_aO_b$$
eşitliği zorunlu olarak \(O_b=0\) verir. Yani böyle bir \(a\), ancak tek kısmı sıfır olan ve \(b\ge a\) koşulunu sağlayan \(b\) değerleriyle eşleşebilir.
Eğer \(O_a=0\) ama \(E_a\neq 0\) ise, bu kez zorunlu olarak \(E_b=0\) gerekir. Dolayısıyla bu tip \(a\) değerleri yalnızca çift kısmı sıfır olan \(b\ge a\) değerleriyle eşleşir.
Son özel durum \(a=0\)'dır. Bu halde
$$Q(x)=B(x)^2$$
olur ve bu her zaman karedir. Demek ki \(b\in[0,N]\) aralığındaki her değer bir geçerli \((0,b)\) çifti üretir.
\(a=3\) ve \(b=6\) alalım. İkili yazımları
$$a=11_2,\qquad b=110_2,$$
dolayısıyla
$$A(x)=1+x,\qquad B(x)=x+x^2.$$
\(t=x^2\) ile ayrıştırınca
$$E_a=1,\ O_a=1,\qquad E_b=t,\ O_b=1$$
elde edilir. Ölçüt
$$E_aE_b=1\cdot t=t,\qquad t\,O_aO_b=t\cdot 1\cdot 1=t$$
şeklinde sağlandığı için çift geçerlidir.
Doğrudan açılım da bunu doğrular:
$$A(x)^2=1+x^2,\qquad xA(x)B(x)=x^2+x^4,\qquad B(x)^2=x^2+x^4,$$
buradan
$$Q(x)=1+x^2$$
elde edilir. Yalnızca çift dereceler kaldığı için sonuç gerçekten karedir.
Genel durumdaki her \(a\), \((E_a,tO_a)\) çiftinden bir normalize anahtar üretir. Genel durumdaki her \(b\) de \((O_b,E_b)\) çiftinden bir anahtar üretir. Kayıtlar önce anahtara, sonra sayının kendisine göre sıralanınca, genel durumdaki geçerli çiftlerin sayısı tam olarak \(b\ge a\) koşulunu sağlayan eşit anahtar eşleşmelerinin sayısı olur.
Dejenere aileler ayrı sıralı listeler ve ikili arama ile sayılır. Böylece imkansız olan \(\Theta(N^2)\) tarama, pratik bir \(O(N\log N)\) yönteme dönüşür.
C++, Python ve Java uygulamaları \([0,N]\) aralığını dolaşır, her sayıyı çift ve tek bit polinomlarına ayırır ve sayıyı ya genel kayıt listesine ya da sıfır bileşenli özel listelerden birine koyar. Polinom EBOB'u ve tam bölme, katsayılar \(\mathbb F_2\)'de olduğu için XOR tabanlı Öklid aritmetiğiyle yapılır.
Tek kısmı sıfır olan bütün \(b\) değerleri ile çift kısmı sıfır olan bütün \(b\) değerleri ayrı ayrı sıralı tutulur. Dejenere her \(a\) için ikili arama yapılarak hem cebirsel koşulu hem de \(b\ge a\) sıralama koşulunu sağlayan uygun \(b\) sayısı bulunur. \(a=0\) ailesi ise doğrudan \(N+1\) katkı yapar.
Genel kayıtlar önce normalize anahtara, sonra değere göre sıralanır. İki işaretçili bir tarama, \(a\)-tarafı ile \(b\)-tarafındaki aynı anahtarlı gruplar arasında ilerler. Ortak bir grup içinde değeri en az \(a\) olan ilk kayıt bulunduğunda, o \(a\) için kaç yasal eş bulunduğu doğrudan elde edilir. Bu adım, indirgenmiş cebirsel sınıflar üzerinde yapılan bir merge sayımıdır.
Üç dildeki sürümlerin matematiksel çekirdeği aynıdır ve küçük sınırlar için doğrudan tanım tabanlı testlerle doğrulanır. Betik dillerindeki sürümler ayrıca üretim sınırı için bilinen sonuca kısa yoldan döner; buna rağmen hızlı genel yöntem kod içinde yer almaya ve küçük girdilerde sınanmaya devam eder.
24 bitlik üst sınır sabit olduğu için bit ayırma, polinom EBOB'u ve tam bölme her sayı başına sabit zamandır. Baskın maliyet kayıt dizilerini sıralamaktır; toplam çalışma süresi bu yüzden \(O(N\log N)\) olur.
Bellek kullanımı \(O(N)\)'dir: genel durum kayıtları ile dejenere dallar için birkaç yardımcı sıralı liste tutulur. Naif \(O(N^2)\) çift kontrolüne göre esas kazanım budur.
Para el límite \(N=10^7\), hay que contar todos los pares \((a,b)\) con \(0\le a\le b\le N\) tales que
$$a\otimes a \oplus (2\otimes a\otimes b) \oplus b\otimes b$$
sea un cuadrado carryless. En la interpretación polinómica sobre \(\mathbb F_2\), eso significa que el polinomio asociado contiene únicamente potencias de grado par.
Probar todos los pares costaría \(\Theta(N^2)\), algo inviable para este tamaño. Las implementaciones lo evitan separando cada entero en dos polinomios más pequeños, construyendo un invariante canónico para el caso general y contando coincidencias después de ordenar.
A cada entero no negativo \(n=\sum n_i2^i\) le asociamos el polinomio
$$P_n(x)=\sum n_i x^i\in\mathbb F_2[x].$$
Bajo esta identificación, XOR es suma y la multiplicación carryless es la multiplicación ordinaria en \(\mathbb F_2[x]\). Si escribimos
$$A(x)=P_a(x),\qquad B(x)=P_b(x),$$
la cantidad probada por el código es
$$Q(x)=A(x)^2+xA(x)B(x)+B(x)^2.$$
Toda la solución consiste en determinar cuándo \(Q(x)\) es un cuadrado.
En característica 2 se cumple
$$\left(\sum c_i x^i\right)^2=\sum c_i x^{2i},$$
porque los términos cruzados aparecen dos veces y se cancelan. Por tanto, un polinomio de \(\mathbb F_2[x]\) es cuadrado si y solo si todos sus coeficientes de grado impar son cero. Precisamente por eso las implementaciones solo inspeccionan la parte impar de \(Q(x)\).
Introducimos \(t=x^2\) y escribimos
$$A(x)=E_a(t)+x\,O_a(t),\qquad B(x)=E_b(t)+x\,O_b(t),$$
donde \(E_a,O_a,E_b,O_b\in\mathbb F_2[t]\) se obtienen a partir de las posiciones pares e impares de los bits de \(a\) y \(b\).
Como \(N=10^7<2^{24}\), cada uno de estos polinomios auxiliares tiene a lo sumo 12 coeficientes. Eso mantiene muy pequeñas las operaciones de máximo común divisor y división exacta.
Los términos cuadrados \(A(x)^2\) y \(B(x)^2\) ya tienen solamente grados pares. Así, toda la parte impar de \(Q(x)\) procede del término central \(xA(x)B(x)\). Al expandir con \(t=x^2\),
$$A(x)B(x)=E_aE_b+x(E_aO_b+O_aE_b)+t\,O_aO_b,$$
y por tanto
$$xA(x)B(x)=xE_aE_b+t(E_aO_b+O_aE_b)+xt\,O_aO_b.$$
La parte impar de \(Q(x)\) es entonces
$$x\bigl(E_a(t)E_b(t)+t\,O_a(t)O_b(t)\bigr).$$
Luego \((a,b)\) es válido exactamente cuando
$$E_a(t)E_b(t)=t\,O_a(t)O_b(t).$$
Esa igualdad es el objeto matemático central de la solución.
Supongamos primero que \(E_a,O_a,E_b,O_b\) son todos no nulos. Entonces la condición puede escribirse como
$$\frac{E_a(t)}{t\,O_a(t)}=\frac{O_b(t)}{E_b(t)}$$
dentro del cuerpo de funciones racionales \(\mathbb F_2(t)\). Las implementaciones normalizan ambos lados cancelando el máximo común divisor polinómico:
$$\left(\frac{E_a}{d_a},\frac{tO_a}{d_a}\right),\qquad d_a=\gcd(E_a,tO_a),$$
$$\left(\frac{O_b}{d_b},\frac{E_b}{d_b}\right),\qquad d_b=\gcd(O_b,E_b).$$
Después de cancelar, cada lado queda en forma reducida, y esa forma reducida es única sobre \(\mathbb F_2[t]\). Por eso, un par general \((a,b)\) es válido si y solo si los dos pares ordenados reducidos coinciden exactamente. La ecuación original se convierte así en un problema de emparejar claves.
Los casos con componentes nulas no entran en la descripción por cocientes y se cuentan aparte.
Si \(E_a=0\) pero \(O_a\neq 0\), la identidad
$$E_aE_b=t\,O_aO_b$$
obliga a que \(O_b=0\). Por tanto, esos valores de \(a\) solo pueden emparejarse con \(b\ge a\) cuya parte impar sea nula.
Si \(O_a=0\) pero \(E_a\neq 0\), entonces necesariamente \(E_b=0\). Esos \(a\) solo pueden emparejarse con \(b\ge a\) cuya parte par sea nula.
El último caso especial es \(a=0\). Entonces
$$Q(x)=B(x)^2,$$
que siempre es un cuadrado. Así, cada \(b\in[0,N]\) produce un par válido \((0,b)\).
Tomemos \(a=3\) y \(b=6\). En binario,
$$a=11_2,\qquad b=110_2,$$
de modo que
$$A(x)=1+x,\qquad B(x)=x+x^2.$$
Con \(t=x^2\), la separación da
$$E_a=1,\ O_a=1,\qquad E_b=t,\ O_b=1.$$
La condición queda
$$E_aE_b=1\cdot t=t,\qquad t\,O_aO_b=t\cdot 1\cdot 1=t,$$
así que el par es válido.
La expansión directa lo confirma:
$$A(x)^2=1+x^2,\qquad xA(x)B(x)=x^2+x^4,\qquad B(x)^2=x^2+x^4,$$
y por ello
$$Q(x)=1+x^2,$$
que solo tiene grados pares y por tanto es un cuadrado.
Cada \(a\) del caso general aporta una clave normalizada obtenida de \((E_a,tO_a)\), y cada \(b\) del caso general aporta otra a partir de \((O_b,E_b)\). Después de ordenar primero por clave y luego por el valor original, el número de pares válidos del caso general es exactamente el número de coincidencias de clave con \(b\ge a\).
Las familias degeneradas se cuentan con listas ordenadas separadas y búsqueda binaria. Ese es el paso que reemplaza el barrido imposible \(\Theta(N^2)\) por un cálculo factible de \(O(N\log N)\).
Las implementaciones en C++, Python y Java recorren \([0,N]\), separan cada entero en sus polinomios de bits pares e impares y lo colocan en una lista general o en uno de los contenedores de componentes nulas. El máximo común divisor polinómico y la división exacta se realizan con aritmética euclídea basada en XOR, porque los coeficientes viven en \(\mathbb F_2\).
Las implementaciones mantienen listas ordenadas de todos los \(b\) cuya parte impar es cero y de todos los \(b\) cuya parte par es cero. Para cada \(a\) degenerado, una búsqueda binaria cuenta cuántos \(b\) cumplen simultáneamente la restricción algebraica y la condición de orden \(b\ge a\). La familia incondicional \(a=0\) aporta inmediatamente \(N+1\) pares.
Los registros generales se ordenan por clave normalizada y luego por valor. Un barrido con dos punteros avanza por los grupos de igual clave en el lado de \(a\) y en el lado de \(b\). Dentro de un grupo común, mover el puntero hasta el primer valor al menos \(a\) da el número de compañeros legales de ese \(a\). Es un conteo tipo merge sobre clases algebraicas ya reducidas.
Las tres versiones comparten exactamente esta base matemática y la validan en límites pequeños contra una comprobación directa de la definición. Además, las versiones de scripting conservan el resultado final conocido para el límite de producción, mientras que la rutina rápida completa sigue presente y verificada en entradas más pequeñas.
Con el techo de 24 bits fijo, separar bits y calcular gcd/divisiones polinómicas cuesta tiempo constante por entero. El trabajo dominante es ordenar los arreglos de registros, de modo que el tiempo total es \(O(N\log N)\).
La memoria es \(O(N)\): se almacenan los registros del caso general y unas pocas listas auxiliares para las ramas degeneradas. Frente al chequeo ingenuo \(O(N^2)\), esa es la mejora decisiva.
在上界 \(N=10^7\) 下，需要统计所有满足 \(0\le a\le b\le N\) 的整数对 \((a,b)\)，使得
$$a\otimes a \oplus (2\otimes a\otimes b) \oplus b\otimes b$$
本身是一个 carryless 平方。把二进制位看成 \(\mathbb F_2\) 上的多项式系数后，这等价于对应多项式只含偶数次幂。
如果直接枚举所有二元组，代价是 \(\Theta(N^2)\)，在这个规模上完全不可行。实现采用的办法是：先把每个整数拆成“偶位多项式”和“奇位多项式”，再在非退化情形中提取一个规范化不变量，最后通过排序后的匹配来计数。
对每个非负整数 \(n=\sum n_i2^i\)，定义对应多项式
$$P_n(x)=\sum n_i x^i\in\mathbb F_2[x].$$
在这个对应下，XOR 就是多项式加法，而 carryless 乘法就是 \(\mathbb F_2[x]\) 中的普通乘法。记
$$A(x)=P_a(x),\qquad B(x)=P_b(x),$$
则代码检查的对象是
$$Q(x)=A(x)^2+xA(x)B(x)+B(x)^2.$$
整个题目的关键，就是精确判断 \(Q(x)\) 何时是一个平方。
在特征为 2 的情况下，
$$\left(\sum c_i x^i\right)^2=\sum c_i x^{2i},$$
因为所有交叉项都会出现两次并相互抵消。因此，一个 \(\mathbb F_2[x]\) 多项式当且仅当所有奇数次项系数都为 0 时才是平方。这正是实现只检查 \(Q(x)\) 奇数位系数是否为 0 的原因。
令 \(t=x^2\)，把每个多项式写成
$$A(x)=E_a(t)+x\,O_a(t),\qquad B(x)=E_b(t)+x\,O_b(t),$$
其中 \(E_a,O_a,E_b,O_b\in\mathbb F_2[t]\) 分别来自 \(a\) 和 \(b\) 的偶数位、奇数位二进制系数。
由于 \(N=10^7<2^{24}\)，这些辅助多项式最多只有 12 个系数，所以多项式 gcd 与精确除法都只是很小的定长位运算。
\(A(x)^2\) 和 \(B(x)^2\) 天然只含偶数次幂，所以 \(Q(x)\) 的全部奇次项都来自中间项 \(xA(x)B(x)\)。把 \(t=x^2\) 代入展开，得到
$$A(x)B(x)=E_aE_b+x(E_aO_b+O_aE_b)+t\,O_aO_b,$$
于是
$$xA(x)B(x)=xE_aE_b+t(E_aO_b+O_aE_b)+xt\,O_aO_b.$$
因此 \(Q(x)\) 的奇次部分恰好是
$$x\bigl(E_a(t)E_b(t)+t\,O_a(t)O_b(t)\bigr).$$
所以二元组 \((a,b)\) 有效，当且仅当
$$E_a(t)E_b(t)=t\,O_a(t)O_b(t).$$
这就是解法中最核心的数学恒等式。
先假设 \(E_a,O_a,E_b,O_b\) 全都非零。此时条件可以改写为
$$\frac{E_a(t)}{t\,O_a(t)}=\frac{O_b(t)}{E_b(t)}$$
，也就是 \(\mathbb F_2(t)\) 中两个有理函数相等。实现会分别对两边做多项式 gcd 约分：
$$\left(\frac{E_a}{d_a},\frac{tO_a}{d_a}\right),\qquad d_a=\gcd(E_a,tO_a),$$
$$\left(\frac{O_b}{d_b},\frac{E_b}{d_b}\right),\qquad d_b=\gcd(O_b,E_b).$$
约分之后得到的有序对就是该有理函数的规范表示，而这种表示在 \(\mathbb F_2[t]\) 上是唯一的。因此，一般情形下 \((a,b)\) 合法，当且仅当这两个约分后的有序对完全相同。原来的双变量方程由此被转化成键值匹配问题。
如果某个组成部分为 0，就不能直接使用上面的比值表示，必须单独处理。
若 \(E_a=0\) 且 \(O_a\neq 0\)，那么
$$E_aE_b=t\,O_aO_b$$
只能在 \(O_b=0\) 时成立。因此这种 \(a\) 只能和满足 \(b\ge a\) 且奇位多项式为 0 的 \(b\) 配对。
若 \(O_a=0\) 且 \(E_a\neq 0\)，则上式强制 \(E_b=0\)。因此这类 \(a\) 只能与满足 \(b\ge a\) 且偶位多项式为 0 的 \(b\) 配对。
最后一个特殊情形是 \(a=0\)。这时
$$Q(x)=B(x)^2,$$
必然是平方，所以每个 \(b\in[0,N]\) 都给出一个合法的 \((0,b)\)。
取 \(a=3\)、\(b=6\)。它们的二进制表示为
$$a=11_2,\qquad b=110_2,$$
因此
$$A(x)=1+x,\qquad B(x)=x+x^2.$$
令 \(t=x^2\)，则拆分结果为
$$E_a=1,\ O_a=1,\qquad E_b=t,\ O_b=1.$$
判据变成
$$E_aE_b=1\cdot t=t,\qquad t\,O_aO_b=t\cdot 1\cdot 1=t,$$
两边相等，所以这个二元组有效。
直接展开也能验证：
$$A(x)^2=1+x^2,\qquad xA(x)B(x)=x^2+x^4,\qquad B(x)^2=x^2+x^4,$$
从而
$$Q(x)=1+x^2,$$
只含偶数次幂，因此确实是平方。
每个一般情形的 \(a\) 都会从 \((E_a,tO_a)\) 生成一个规范键；每个一般情形的 \(b\) 都会从 \((O_b,E_b)\) 生成一个规范键。把记录先按键、再按原整数值排序后，一般情形中合法二元组的个数，就等于满足 \(b\ge a\) 的同键匹配数量。
退化分支则通过单独的有序列表和二分查找统计。这一步把原本不可能完成的 \(\Theta(N^2)\) 穷举，变成了可执行的 \(O(N\log N)\) 计算。
C++、Python 和 Java 实现都会扫描 \([0,N]\) 内的所有整数，把每个整数拆成偶位多项式与奇位多项式，然后放入一般记录数组或某个零分量桶中。由于系数属于 \(\mathbb F_2\)，多项式 gcd 与精确除法都通过基于 XOR 的欧几里得算法完成。
实现维护两类有序列表：一类是奇位部分为 0 的所有 \(b\)，另一类是偶位部分为 0 的所有 \(b\)。对于每个退化的 \(a\)，通过二分查找即可数出同时满足代数条件和顺序约束 \(b\ge a\) 的合法 \(b\) 个数。无条件成立的 \(a=0\) 家族则直接贡献 \(N+1\) 个二元组。
一般记录先按规范键、再按数值排序。随后使用双指针扫过 \(a\) 侧和 \(b\) 侧中键相同的分组。在某个公共分组内部，把指针推进到第一个数值不小于 \(a\) 的位置，就能得到该 \(a\) 的全部合法伙伴数量。这实际上是对约分后代数类做一次归并式计数。
三种语言版本共享同一套数学结构，并在较小上界上与直接按定义检验的方法进行比对验证。脚本语言版本还为生产上界保留了已知最终结果，同时完整的快速算法仍然保存在代码中并通过小规模输入校验。
在 24 位上界固定的前提下，拆位、求多项式 gcd 和精确除法对每个整数都是常数时间。主导成本是对记录数组的排序，因此总时间复杂度为 \(O(N\log N)\)。
空间复杂度为 \(O(N)\)：需要保存一般情形的记录，以及退化分支所需的少量辅助有序列表。相比朴素的 \(O(N^2)\) 枚举，这是决定性的改进。
Для границы \(N=10^7\) нужно посчитать все пары \((a,b)\), где \(0\le a\le b\le N\), для которых величина
$$a\otimes a \oplus (2\otimes a\otimes b) \oplus b\otimes b$$
сама является carryless-квадратом. Если интерпретировать двоичную запись как многочлен над \(\mathbb F_2\), это означает, что соответствующий многочлен содержит только чётные степени.
Прямой перебор всех \(\Theta(N^2)\) пар на таком диапазоне невозможен. Поэтому реализации раскладывают каждое число на два меньших многочлена, выводят канонический инвариант для общего случая, а затем считают совпадения после сортировки.
Каждому неотрицательному целому \(n=\sum n_i2^i\) сопоставим многочлен
$$P_n(x)=\sum n_i x^i\in\mathbb F_2[x].$$
При таком соответствии XOR становится сложением, а carryless-умножение становится обычным умножением в \(\mathbb F_2[x]\). Обозначим
$$A(x)=P_a(x),\qquad B(x)=P_b(x).$$
Тогда код проверяет многочлен
$$Q(x)=A(x)^2+xA(x)B(x)+B(x)^2.$$
Всё решение строится вокруг точного критерия того, когда \(Q(x)\) является квадратом.
В характеристике 2 верно тождество
$$\left(\sum c_i x^i\right)^2=\sum c_i x^{2i},$$
потому что смешанные члены появляются дважды и сокращаются. Значит, многочлен из \(\mathbb F_2[x]\) является квадратом тогда и только тогда, когда все коэффициенты при нечётных степенях равны нулю. Именно поэтому реализации проверяют только нечётную часть \(Q(x)\).
Положим \(t=x^2\) и разложим
$$A(x)=E_a(t)+x\,O_a(t),\qquad B(x)=E_b(t)+x\,O_b(t),$$
где \(E_a,O_a,E_b,O_b\in\mathbb F_2[t]\) построены из чётных и нечётных позиций битов чисел \(a\) и \(b\).
Так как \(N=10^7<2^{24}\), каждый вспомогательный многочлен имеет не более 12 коэффициентов. Поэтому gcd многочленов и точное деление остаются очень маленькими по размеру операциями.
Квадраты \(A(x)^2\) и \(B(x)^2\) уже содержат только чётные степени. Следовательно, вся нечётная часть \(Q(x)\) приходит из среднего слагаемого \(xA(x)B(x)\). При раскрытии скобок с \(t=x^2\) получаем
$$A(x)B(x)=E_aE_b+x(E_aO_b+O_aE_b)+t\,O_aO_b,$$
а значит,
$$xA(x)B(x)=xE_aE_b+t(E_aO_b+O_aE_b)+xt\,O_aO_b.$$
Отсюда нечётная часть \(Q(x)\) равна
$$x\bigl(E_a(t)E_b(t)+t\,O_a(t)O_b(t)\bigr).$$
Следовательно, пара \((a,b)\) допустима тогда и только тогда, когда
$$E_a(t)E_b(t)=t\,O_a(t)O_b(t).$$
Это и есть центральное тождество всей задачи.
Сначала предположим, что все четыре многочлена \(E_a,O_a,E_b,O_b\) ненулевые. Тогда условие можно переписать как
$$\frac{E_a(t)}{t\,O_a(t)}=\frac{O_b(t)}{E_b(t)}$$
в поле рациональных функций \(\mathbb F_2(t)\). Реализации нормализуют обе стороны отдельно, сокращая на полиномиальный gcd:
$$\left(\frac{E_a}{d_a},\frac{tO_a}{d_a}\right),\qquad d_a=\gcd(E_a,tO_a),$$
$$\left(\frac{O_b}{d_b},\frac{E_b}{d_b}\right),\qquad d_b=\gcd(O_b,E_b).$$
После сокращения каждая сторона записана в приведённом виде, а такой приведённый вид над \(\mathbb F_2[t]\) единственен. Значит, в общем случае пара \((a,b)\) допустима тогда и только тогда, когда эти два упорядоченных приведённых набора совпадают. Тем самым исходное уравнение превращается в задачу сравнения ключей.
Случаи с нулевыми компонентами не укладываются в описание через отношение и поэтому считаются отдельно.
Если \(E_a=0\), но \(O_a\neq 0\), то равенство
$$E_aE_b=t\,O_aO_b$$
вынуждает \(O_b=0\). Значит, такое \(a\) можно сочетать только с числами \(b\ge a\), у которых нечётная часть равна нулю.
Если \(O_a=0\), но \(E_a\neq 0\), то аналогично обязательно \(E_b=0\). Такие \(a\) сочетаются только с числами \(b\ge a\), у которых чётная часть равна нулю.
Последний специальный случай — \(a=0\). Тогда
$$Q(x)=B(x)^2,$$
а это всегда квадрат, поэтому каждое \(b\in[0,N]\) даёт допустимую пару \((0,b)\).
Возьмём \(a=3\) и \(b=6\). В двоичной записи
$$a=11_2,\qquad b=110_2,$$
поэтому
$$A(x)=1+x,\qquad B(x)=x+x^2.$$
При \(t=x^2\) получаем разложение
$$E_a=1,\ O_a=1,\qquad E_b=t,\ O_b=1.$$
Критерий принимает вид
$$E_aE_b=1\cdot t=t,\qquad t\,O_aO_b=t\cdot 1\cdot 1=t,$$
так что пара допустима.
Прямое раскрытие это подтверждает:
$$A(x)^2=1+x^2,\qquad xA(x)B(x)=x^2+x^4,\qquad B(x)^2=x^2+x^4,$$
следовательно,
$$Q(x)=1+x^2,$$
то есть остаются только чётные степени, а значит это действительно квадрат.
Каждое \(a\) из общего случая создаёт один нормализованный ключ из пары \((E_a,tO_a)\), а каждое \(b\) из общего случая — один ключ из пары \((O_b,E_b)\). После сортировки сначала по ключу, затем по исходному значению число допустимых пар общего случая совпадает с числом совпадений ключей, удовлетворяющих \(b\ge a\).
Вырожденные семейства считаются отдельно с помощью отсортированных списков и двоичного поиска. Именно этот шаг заменяет невозможный перебор \(\Theta(N^2)\) на выполнимое вычисление \(O(N\log N)\).
Реализации на C++, Python и Java проходят по всему диапазону \([0,N]\), раскладывают каждое число на многочлены чётных и нечётных битов и помещают его либо в общий массив записей, либо в один из специальных контейнеров с нулевой компонентой. gcd многочленов и точное деление реализованы через XOR-версию алгоритма Евклида, потому что коэффициенты лежат в \(\mathbb F_2\).
Реализации поддерживают отсортированные списки всех \(b\), у которых нечётная часть равна нулю, и всех \(b\), у которых нулевая чётная часть. Для каждого вырожденного \(a\) двоичный поиск сразу даёт количество \(b\), удовлетворяющих и алгебраическому условию, и порядковому ограничению \(b\ge a\). Безусловное семейство \(a=0\) сразу добавляет \(N+1\) пар.
Общие записи сортируются по нормализованному ключу, а затем по значению. После этого два указателя проходят по группам одинаковых ключей на стороне \(a\) и на стороне \(b\). Внутри общей группы продвижение указателя до первого значения не меньше \(a\) сразу даёт число допустимых партнёров для данного \(a\). Это обычный merge-подсчёт по уже сокращённым алгебраическим классам.
Во всех трёх языках математическая основа одна и та же, и на малых границах она проверяется прямым тестом по определению. Скриптовые версии дополнительно хранят известный итоговый результат для боевой границы, при этом полный быстрый алгоритм остаётся в коде и проверяется на меньших входах.
При фиксированном 24-битном потолке разбиение на биты, полиномиальный gcd и точное деление требуют константного времени на одно число. Основная стоимость — сортировка массивов записей, так что итоговое время работы равно \(O(N\log N)\).
Память равна \(O(N)\): хранятся записи общего случая и несколько вспомогательных отсортированных списков для вырожденных ветвей. По сравнению с наивной проверкой всех пар за \(O(N^2)\) это и есть решающее улучшение.
عند الحد \(N=10^7\)، نريد عدّ جميع الأزواج \((a,b)\) التي تحقق \(0\le a\le b\le N\) ويكون فيها التعبير
$$a\otimes a \oplus (2\otimes a\otimes b) \oplus b\otimes b$$
مربعًا carryless. وعند تفسير السلاسل الثنائية على أنها كثيرات حدود فوق \(\mathbb F_2\)، فهذا يعني أن كثير الحدود الموافق لا يحتوي إلا على درجات زوجية.
الفحص المباشر لكل الأزواج يكلف \(\Theta(N^2)\)، وهذا غير ممكن عند هذا الحجم. لذلك تعتمد الحلول على تفكيك كل عدد إلى جزأين: جزء البتات الزوجية وجزء البتات الفردية، ثم استخراج ثابت معياري للحالة العامة، وأخيرًا عدّ التطابقات بعد الفرز.
نربط بكل عدد صحيح غير سالب \(n=\sum n_i2^i\) كثير الحدود
$$P_n(x)=\sum n_i x^i\in\mathbb F_2[x].$$
بهذا الترميز تصبح عملية XOR جمعًا، ويصبح الضرب carryless هو الضرب المعتاد في \(\mathbb F_2[x]\). إذا كتبنا
$$A(x)=P_a(x),\qquad B(x)=P_b(x),$$
فإن المقدار الذي يفحصه الكود هو
$$Q(x)=A(x)^2+xA(x)B(x)+B(x)^2.$$
إذن جوهر المسألة هو تحديد متى يكون \(Q(x)\) مربعًا.
في الخاصية 2 لدينا
$$\left(\sum c_i x^i\right)^2=\sum c_i x^{2i},$$
لأن الحدود المختلطة تظهر مرتين ثم تختفي. لذلك يكون كثير الحدود في \(\mathbb F_2[x]\) مربعًا إذا وفقط إذا كانت جميع معاملات الدرجات الفردية تساوي صفرًا. ولهذا السبب تكتفي التطبيقات بفحص الجزء الفردي من \(Q(x)\).
لنضع \(t=x^2\)، ثم نكتب
$$A(x)=E_a(t)+x\,O_a(t),\qquad B(x)=E_b(t)+x\,O_b(t),$$
حيث \(E_a,O_a,E_b,O_b\in\mathbb F_2[t]\) تُستخرج من البتات الزوجية والفردية في \(a\) و\(b\).
وبما أن \(N=10^7<2^{24}\)، فكل كثير حدود مساعد هنا يملك في أقصى الحالات 12 معاملًا فقط، ولذلك تبقى عمليات gcd والقسمة التامة صغيرة الحجم جدًا.
الحدان \(A(x)^2\) و\(B(x)^2\) يحتويان أصلًا على درجات زوجية فقط. إذن جميع الحدود الفردية في \(Q(x)\) تأتي من الحد الأوسط \(xA(x)B(x)\). عند التوسيع مع \(t=x^2\) نحصل على
$$A(x)B(x)=E_aE_b+x(E_aO_b+O_aE_b)+t\,O_aO_b,$$
ومن ثم
$$xA(x)B(x)=xE_aE_b+t(E_aO_b+O_aE_b)+xt\,O_aO_b.$$
إذن الجزء الفردي من \(Q(x)\) يساوي
$$x\bigl(E_a(t)E_b(t)+t\,O_a(t)O_b(t)\bigr).$$
وبالتالي يكون الزوج \((a,b)\) صالحًا إذا وفقط إذا تحقق
$$E_a(t)E_b(t)=t\,O_a(t)O_b(t).$$
وهذه هي الهوية الرياضية الأساسية في الحل.
لنفترض أولًا أن \(E_a,O_a,E_b,O_b\) كلها غير صفرية. عندها يمكن كتابة الشرط على صورة
$$\frac{E_a(t)}{t\,O_a(t)}=\frac{O_b(t)}{E_b(t)}$$
داخل حقل الدوال الكسرية \(\mathbb F_2(t)\). تقوم التطبيقات بتطبيع الطرفين كل على حدة بعد إلغاء gcd كثيرات الحدود:
$$\left(\frac{E_a}{d_a},\frac{tO_a}{d_a}\right),\qquad d_a=\gcd(E_a,tO_a),$$
$$\left(\frac{O_b}{d_b},\frac{E_b}{d_b}\right),\qquad d_b=\gcd(O_b,E_b).$$
بعد الاختزال يصبح كل طرف في صورة مخفضة، وهذه الصورة فريدة فوق \(\mathbb F_2[t]\). لذلك يكون الزوج العام صالحًا إذا وفقط إذا تطابق الزوجان المرتبان بعد الاختزال تمامًا. وهكذا تتحول المعادلة الأصلية إلى مسألة مطابقة مفاتيح.
الحالات التي يظهر فيها جزء صفري لا تناسب لغة النِّسب، ولذلك تُعالج على نحو منفصل.
إذا كان \(E_a=0\) ولكن \(O_a\neq 0\)، فإن
$$E_aE_b=t\,O_aO_b$$
يفرض بالضرورة أن \(O_b=0\). لذا لا يمكن لهذا النوع من \(a\) أن يقترن إلا مع قيم \(b\ge a\) التي يساوي فيها الجزء الفردي صفرًا.
أما إذا كان \(O_a=0\) ولكن \(E_a\neq 0\)، فلابد أن يكون \(E_b=0\). وبالتالي تقترن هذه القيم من \(a\) فقط مع قيم \(b\ge a\) التي يساوي فيها الجزء الزوجي صفرًا.
الحالة الخاصة الأخيرة هي \(a=0\). حينها
$$Q(x)=B(x)^2,$$
وهو مربع دائمًا، لذا فإن كل \(b\in[0,N]\) يعطي زوجًا صالحًا من الشكل \((0,b)\).
خذ \(a=3\) و\(b=6\). في النظام الثنائي
$$a=11_2,\qquad b=110_2,$$
ومن ثم
$$A(x)=1+x,\qquad B(x)=x+x^2.$$
ومع \(t=x^2\) يصبح التفكيك
$$E_a=1,\ O_a=1,\qquad E_b=t,\ O_b=1.$$
وعليه يصبح الشرط
$$E_aE_b=1\cdot t=t,\qquad t\,O_aO_b=t\cdot 1\cdot 1=t,$$
فتتحقق المساواة، وبالتالي فالزوج صالح.
والتوسيع المباشر يؤكد ذلك:
$$A(x)^2=1+x^2,\qquad xA(x)B(x)=x^2+x^4,\qquad B(x)^2=x^2+x^4,$$
ومن ثم
$$Q(x)=1+x^2,$$
ولا تظهر فيه إلا درجات زوجية، لذلك فهو مربع فعلًا.
كل قيمة \(a\) في الحالة العامة تنتج مفتاحًا معياريًا مشتقًا من \((E_a,tO_a)\)، وكل قيمة \(b\) في الحالة العامة تنتج مفتاحًا من \((O_b,E_b)\). وبعد فرز السجلات أولًا حسب المفتاح ثم حسب القيمة الأصلية، يصبح عدد الأزواج الصحيحة في الحالة العامة مساويًا تمامًا لعدد التطابقات ذات المفتاح نفسه مع شرط \(b\ge a\).
أما الفروع المتدهورة فتُحسب باستخدام قوائم مرتبة منفصلة وبحث ثنائي. وهذه هي الخطوة التي تستبدل المسح المستحيل \(\Theta(N^2)\) بحساب عملي من رتبة \(O(N\log N)\).
تقوم تطبيقات ++C وPython وJava بمسح المجال \([0,N]\)، وتفصل كل عدد إلى كثير حدود للبتات الزوجية وآخر للبتات الفردية، ثم تضعه إما في قائمة السجلات العامة أو في أحد الأوعية الخاصة بالحالات الصفرية. وتحسب gcd كثيرات الحدود والقسمة التامة بواسطة حساب إقليدي قائم على XOR لأن المعاملات تقع في \(\mathbb F_2\).
تحتفظ التطبيقات بقوائم مرتبة لكل قيم \(b\) التي يساوي فيها الجزء الفردي صفرًا، ولقيم \(b\) التي يساوي فيها الجزء الزوجي صفرًا. ولكل \(a\) متدهور، يعطي البحث الثنائي عدد قيم \(b\) التي تحقق في الوقت نفسه القيد الجبري وقيد الترتيب \(b\ge a\). أما العائلة غير المشروطة \(a=0\) فتضيف مباشرة \(N+1\) زوجًا.
تُفرز السجلات العامة بحسب المفتاح المعياري ثم بحسب القيمة. وبعد ذلك يمر مؤشّران عبر مجموعات المفاتيح المتساوية في جانب \(a\) وجانب \(b\). داخل المجموعة المشتركة، يكفي تحريك المؤشر حتى أول قيمة لا تقل عن \(a\) للحصول على عدد الشركاء القانونيين لذلك \(a\). هذه في الجوهر عملية عدّ من نوع merge فوق طبقات جبرية مختزلة سلفًا.
تتشارك النسخ الثلاث البنية الرياضية نفسها، وتتحقق منها على حدود صغيرة عبر مقارنة النتيجة السريعة باختبار مباشر للتعريف. كما تحتفظ نسخ اللغات السكربتية بالقيمة النهائية المعروفة عند حد الإنتاج، مع بقاء الخوارزمية السريعة الكاملة موجودة ومختبرة على مدخلات أصغر.
مع ثبات السقف عند 24 بتًا، تصبح عملية فصل البتات وحساب gcd كثيرات الحدود والقسمة التامة عمليات بزمن ثابت لكل عدد. لذلك تكون الكلفة المسيطرة هي فرز مصفوفات السجلات، ويكون الزمن الكلي \(O(N\log N)\).
أما الذاكرة فهي \(O(N)\)، لأن الخوارزمية تخزن سجلات الحالة العامة وبعض القوائم المساعدة للفروع المتدهورة. وهذه هي القفزة الحاسمة مقارنة بالفحص الساذج لكل الأزواج بزمن \(O(N^2)\).