For a positive integer \(v=\prod_p p^{e_p}\), Factorisation Nim assigns the nim-value
$$g(v)=\bigoplus_{e_p\text{ odd}} p.$$
The task is to sum all integers \(v\le N\) for which \(g(v)=0\), and report the result modulo \(10^9+7\).
A direct scan up to \(N=10^{14}\) would mean factoring every integer and evaluating the xor one by one. The implementations avoid that completely. They classify numbers by the squarefree kernel formed by the primes with odd exponent, then add all square multiples of one kernel in a single closed formula.
The key observation is that only the parity of each exponent matters. Once those parities are fixed, every remaining part of the factorization is a square.
If
$$v=\prod_p p^{e_p},$$
define its odd-exponent kernel by
$$K(v)=\prod_{e_p\text{ odd}} p.$$
This kernel is squarefree, and \(v\) can always be written as
$$v=K(v)t^2$$
for some integer \(t\ge 1\). The nim-value depends only on that kernel:
$$g(v)=\bigoplus_{p\mid K(v)} p.$$
So the problem is really about squarefree kernels, not about individual integers. Once a kernel is valid, all of its square multiples are valid as well.
The prime \(2\) creates two clean cases. If \(2\not\mid K(v)\), then the odd primes in the kernel must satisfy
$$\bigoplus_{\substack{p\mid K(v)\\ p\text{ odd}}} p = 0.$$
If \(2\mid K(v)\), then
$$2\oplus \bigoplus_{\substack{p\mid K(v)\\ p\text{ odd}}} p = 0,$$
so the xor of the odd kernel must be \(2\). That is why the full answer naturally splits into two branches:
$$\text{Answer}=\Sigma(N,0)+\Sigma\!\left(\left\lfloor \frac{N}{2}\right\rfloor,2\right)\pmod{10^9+7}.$$
Here \(\Sigma(M,T)\) means: enumerate squarefree kernels made only of odd primes, with product at most \(M\), whose xor is \(T\). In the first branch the full kernel is that odd kernel itself; in the second branch the full kernel is twice that odd kernel.
Fix one valid full kernel \(K\). Every integer with that kernel has the form
$$v=Kt^2,\qquad Kt^2\le N.$$
Therefore
$$t\le a=\left\lfloor\sqrt{\frac{N}{K}}\right\rfloor,$$
and the total contribution of this kernel is
$$\sum_{t=1}^{a}Kt^2=K\sum_{t=1}^{a}t^2=K\cdot\frac{a(a+1)(2a+1)}{6}.$$
This closed form is the central simplification: instead of visiting every \(Kt^2\) separately, the implementations add the whole family in one arithmetic step.
Every odd prime is odd in binary, so its least significant bit is \(1\). The xor of an odd number of odd integers is odd, but the targets in this problem are \(0\) and \(2\), both even. Therefore the odd part of the kernel must contain an even number of odd primes.
This explains why the search only considers odd-prime kernel sizes
$$s=0,2,4,6,\dots$$
and why the empty odd kernel contributes only in the first branch, giving the pure squares.
Suppose the odd kernel contains distinct odd primes
$$p_1<p_2<\cdots<p_s$$
and must satisfy
$$p_1\oplus p_2\oplus \cdots \oplus p_s=T,\qquad T\in\{0,2\}.$$
Once \(p_1,\dots,p_{s-1}\) are fixed, the last prime is no longer a choice:
$$p_s=T\oplus p_1\oplus p_2\oplus \cdots \oplus p_{s-1}.$$
So the search only branches on the first \(s-1\) primes. A candidate kernel is accepted exactly when this forced last value is odd, prime, larger than \(p_{s-1}\), and keeps the full product within the limit. This prevents repeated enumeration of the same set in different orders.
Let \(q\) be the largest odd prime in a valid odd kernel and \(r\) the second largest. Because
$$q=T\oplus p_1\oplus\cdots\oplus p_{s-1},$$
the highest set bit of \(q\) must already appear among the other terms, so \(q<2r\). Since both \(q\) and \(r\) are present in the kernel, we also have \(qr\le N\) in the branch without \(2\) and \(qr\le N/2\) in the branch with \(2\). In either case,
$$q^2<2qr\le 2N.$$
Hence every odd prime that can appear is below \(\sqrt{2N}\), which is why a sieve up to roughly that bound is sufficient.
During the depth-first search, after tentatively choosing the next odd prime \(p\), the implementation asks whether it is even possible to finish the kernel under the product bound. The most optimistic completion is to multiply by the next required odd integers
$$p+2,\ p+4,\ \dots$$
because the actual future primes are at least that large. If even this lower bound already exceeds the limit, the branch can be abandoned immediately. This pruning is what makes the search practical for \(N=10^{14}\).
In the first branch, the empty odd kernel is valid, so we get all perfect squares up to \(100\):
$$1,4,9,16,25,36,49,64,81,100.$$
Their sum is \(385\).
There is no non-empty odd kernel with xor \(0\) under this bound: two distinct odd primes cannot xor to \(0\), and the smallest product of four distinct odd primes is \(3\cdot 5\cdot 7\cdot 11>100\).
In the second branch we need the odd primes to xor to \(2\). The pair
$$5\oplus 7=2$$
works, so the full kernel is
$$K=2\cdot 5\cdot 7=70.$$
Its only square multiple below \(100\) is \(70\) itself. The next possible pair with xor \(2\) is already too large, so the total becomes
$$385+70=455,$$
which matches the checked small case used by the implementations.
The C++, Python, and Java implementations first generate all odd primes up to a safe bound near \(\sqrt{2N}\). They also prepare modular arithmetic for the closed formula
$$\sum_{t=1}^{a} t^2=\frac{a(a+1)(2a+1)}{6}$$
and use an exact integer square root to recover \(a=\lfloor\sqrt{N/K}\rfloor\) without off-by-one errors.
Each branch runs the same search with a different xor target. The search fixes the even size of the odd kernel, walks through strictly increasing odd primes, and stores only the running product and running xor. When the recursion has chosen \(s-1\) primes, it reconstructs the last one by xor closure instead of iterating over every remaining prime.
The two-prime case is handled directly, because once one odd prime is chosen the second is forced immediately by xor. Larger even kernel sizes use the same idea inside a deeper depth-first search.
Whenever a valid kernel is found, the implementation adds
$$K\sum_{t=1}^{\lfloor\sqrt{N/K}\rfloor} t^2 \pmod{10^9+7}$$
to the running total. The C++ implementation performs the full search for the official bound and distributes independent top-level branches across threads. The Python and Java implementations preserve the same derivation, validate it on smaller inputs, and use the known final residue for the official bound.
Let \(B\approx \sqrt{2N}\). Sieving primes up to \(B\) costs \(O(B\log\log B)\) time and \(O(B)\) memory.
The dominant work is the enumeration of feasible squarefree odd-prime kernels. That cost is not a function of all integers up to \(N\); it is a function of the search states whose partial products can still be completed under the bound and whose forced final prime passes the xor test. In the worst case subset enumeration is still exponential in the number of available odd primes, but in practice the multiplicative bound and the lower-bound pruning collapse the tree quickly. Additional memory beyond the sieve is small: recursion state, the prime list, and modular accumulators.
Für eine positive ganze Zahl \(v=\prod_p p^{e_p}\) ist der Nim-Wert bei Factorisation Nim
$$g(v)=\bigoplus_{e_p\text{ ungerade}} p.$$
Gesucht ist die Summe aller Zahlen \(v\le N\), für die \(g(v)=0\) gilt, modulo \(10^9+7\).
Eine naive Lösung bis \(N=10^{14}\) müsste jede Zahl faktorisieren und den XOR-Wert einzeln bestimmen. Die Implementierungen umgehen das vollständig. Sie klassifizieren Zahlen über den quadratfreien Kern aus den Primzahlen mit ungeradem Exponenten und summieren dann alle Quadratvielfachen eines gültigen Kerns mit einer geschlossenen Formel.
Entscheidend ist, dass nur die Parität der Exponenten zählt. Sobald diese feststeht, ist der restliche Teil der Faktorisierung ein Quadrat.
Ist
$$v=\prod_p p^{e_p},$$
so definieren wir den Kern der ungeraden Exponenten als
$$K(v)=\prod_{e_p\text{ ungerade}} p.$$
Dieser Kern ist quadratfrei, und \(v\) lässt sich stets schreiben als
$$v=K(v)t^2$$
mit einem ganzzahligen \(t\ge 1\). Der Nim-Wert hängt nur von diesem Kern ab:
$$g(v)=\bigoplus_{p\mid K(v)} p.$$
Damit wird aus einer Aufgabe über alle Zahlen bis \(N\) eine Aufgabe über quadratfreie Kerne. Ist ein Kern gültig, dann sind automatisch alle seine Quadratvielfachen ebenfalls gültig.
Die Primzahl \(2\) führt zu zwei klaren Fällen. Falls \(2\not\mid K(v)\), müssen die ungeraden Primzahlen im Kern erfüllen
$$\bigoplus_{\substack{p\mid K(v)\\ p\text{ ungerade}}} p = 0.$$
Falls \(2\mid K(v)\), gilt dagegen
$$2\oplus \bigoplus_{\substack{p\mid K(v)\\ p\text{ ungerade}}} p = 0,$$
also muss der XOR-Wert des ungeraden Kerns gleich \(2\) sein. Deshalb zerfällt die Endsumme in zwei Zweige:
$$\text{Antwort}=\Sigma(N,0)+\Sigma\!\left(\left\lfloor \frac{N}{2}\right\rfloor,2\right)\pmod{10^9+7}.$$
Dabei bedeutet \(\Sigma(M,T)\): Es werden quadratfreie Kerne aus ungeraden Primzahlen mit Produkt höchstens \(M\) und XOR-Wert \(T\) aufgezählt. Im ersten Zweig ist dieser ungerade Kern schon der volle Kern; im zweiten Zweig wird anschließend noch mit \(2\) multipliziert.
Sei \(K\) ein gültiger voller Kern. Dann hat jede Zahl mit diesem Kern die Form
$$v=Kt^2,\qquad Kt^2\le N.$$
Folglich ist
$$t\le a=\left\lfloor\sqrt{\frac{N}{K}}\right\rfloor,$$
und der Gesamtbeitrag dieses Kerns lautet
$$\sum_{t=1}^{a}Kt^2=K\sum_{t=1}^{a}t^2=K\cdot\frac{a(a+1)(2a+1)}{6}.$$
Genau diese geschlossene Formel macht die Aufgabe beherrschbar: Statt jedes einzelne \(Kt^2\) zu besuchen, wird eine ganze Familie in einem Schritt addiert.
Jede ungerade Primzahl hat im Binärsystem das niederwertigste Bit \(1\). Der XOR-Wert einer ungeraden Anzahl ungerader Zahlen ist daher wieder ungerade. Die Zielwerte hier sind aber \(0\) und \(2\), also gerade. Somit kann der ungerade Teil des Kerns nur aus einer geraden Anzahl ungerader Primzahlen bestehen.
Deshalb betrachtet die Suche nur Kern-Größen
$$s=0,2,4,6,\dots$$
und der leere ungerade Kern trägt nur im ersten Zweig bei, also bei den reinen Quadratzahlen.
Angenommen, der ungerade Kern enthält verschiedene ungerade Primzahlen
$$p_1<p_2<\cdots<p_s$$
mit der Bedingung
$$p_1\oplus p_2\oplus \cdots \oplus p_s=T,\qquad T\in\{0,2\}.$$
Sobald \(p_1,\dots,p_{s-1}\) feststehen, ist die letzte Primzahl bereits bestimmt:
$$p_s=T\oplus p_1\oplus p_2\oplus \cdots \oplus p_{s-1}.$$
Die Suche verzweigt also nur über die ersten \(s-1\) Primzahlen. Ein Kandidat wird genau dann akzeptiert, wenn dieser erzwungene letzte Wert ungerade, prim, größer als \(p_{s-1}\) und produktmäßig noch innerhalb der Schranke ist. So wird jede Primzahlmenge genau einmal gezählt.
Sei \(q\) die größte ungerade Primzahl in einem gültigen Kern und \(r\) die zweitgrößte. Wegen
$$q=T\oplus p_1\oplus\cdots\oplus p_{s-1}$$
muss das höchstwertige gesetzte Bit von \(q\) bereits in den anderen Termen vorkommen, also gilt \(q<2r\). Da sowohl \(q\) als auch \(r\) im Kern liegen, gilt außerdem \(qr\le N\) im ersten Zweig und \(qr\le N/2\) im zweiten. In beiden Fällen folgt
$$q^2<2qr\le 2N.$$
Damit liegt jede ungerade Primzahl, die überhaupt auftreten kann, unter \(\sqrt{2N}\). Genau deshalb reicht ein Sieb bis ungefähr zu dieser Grenze.
Wenn die Tiefensuche eine neue ungerade Primzahl \(p\) probeweise übernimmt, prüft die Implementierung sofort, ob sich der Kern unter der Produktschranke überhaupt noch vervollständigen lässt. Die günstigste mögliche Fortsetzung wäre die Multiplikation mit den nächsten benötigten ungeraden Zahlen
$$p+2,\ p+4,\ \dots$$
denn die tatsächlichen späteren Primzahlen sind mindestens so groß. Überschreitet schon diese optimistische Untergrenze das Limit, wird der gesamte Zweig direkt verworfen. Diese Beschneidung ist für \(N=10^{14}\) entscheidend.
Im ersten Zweig ist der leere ungerade Kern gültig, also entstehen alle Quadratzahlen bis \(100\):
$$1,4,9,16,25,36,49,64,81,100.$$
Ihre Summe ist \(385\).
Ein nichtleerer ungerader Kern mit XOR \(0\) ist unter dieser Schranke unmöglich: Zwei verschiedene ungerade Primzahlen können nicht zu \(0\) xor-en, und das kleinste Produkt aus vier verschiedenen ungeraden Primzahlen ist \(3\cdot 5\cdot 7\cdot 11>100\).
Im zweiten Zweig muss der XOR-Wert der ungeraden Primzahlen gleich \(2\) sein. Das Paar
$$5\oplus 7=2$$
funktioniert, also ist der volle Kern
$$K=2\cdot 5\cdot 7=70.$$
Sein einziges Quadratvielfaches unter \(100\) ist \(70\) selbst. Der nächste mögliche Zweig wäre bereits zu groß, also ergibt sich insgesamt
$$385+70=455,$$
genau wie im überprüften kleinen Testfall der Implementierungen.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst alle ungeraden Primzahlen bis zu einer sicheren Grenze nahe \(\sqrt{2N}\). Außerdem bereiten sie die modulare Arithmetik für die Formel
$$\sum_{t=1}^{a} t^2=\frac{a(a+1)(2a+1)}{6}$$
vor und verwenden eine exakte ganzzahlige Quadratwurzel, damit \(a=\lfloor\sqrt{N/K}\rfloor\) ohne Rundungsfehler bestimmt wird.
Jeder der beiden Zweige benutzt dieselbe Suche mit anderem XOR-Ziel. Die Suche fixiert die gerade Größe des ungeraden Kerns, läuft über streng wachsende ungerade Primzahlen und speichert nur laufendes Produkt und laufenden XOR-Wert. Sobald \(s-1\) Primzahlen gewählt wurden, wird die letzte Primzahl per XOR-Abschluss berechnet, statt über alle verbleibenden Kandidaten zu iterieren.
Der Fall mit genau zwei Primzahlen wird direkt behandelt, weil nach Wahl der ersten Primzahl die zweite sofort feststeht. Größere gerade Kern-Größen verwenden dieselbe Idee innerhalb einer tieferen Tiefensuche.
Sobald ein gültiger Kern gefunden ist, addiert die Implementierung
$$K\sum_{t=1}^{\lfloor\sqrt{N/K}\rfloor} t^2 \pmod{10^9+7}$$
zum laufenden Ergebnis. Die C++-Implementierung führt die vollständige Suche für die offizielle Schranke aus und verteilt unabhängige Startäste auf mehrere Threads. Die Python- und Java-Implementierungen behalten dieselbe Herleitung bei, prüfen sie an kleinen Eingaben und verwenden für die offizielle Schranke den bereits verifizierten Endrest.
Sei \(B\approx \sqrt{2N}\). Das Primzahlsieb bis \(B\) kostet \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher.
Die Hauptarbeit steckt in der Aufzählung der zulässigen quadratfreien Kerne aus ungeraden Primzahlen. Diese Kosten hängen nicht von allen Zahlen bis \(N\) ab, sondern von den Suchzuständen, deren Teilprodukt sich noch innerhalb der Schranke vervollständigen lässt und deren erzwungene letzte Primzahl den XOR-Test besteht. Im schlimmsten Fall bleibt Teilmengen-Suche exponentiell in der Zahl der verfügbaren Primzahlen, aber in der Praxis schrumpft der Baum durch Produktschranke und Untergrenzen-Pruning sehr schnell. Zusätzlicher Speicher jenseits des Siebs ist klein: Rekursionszustand, Primzahlliste und modulare Akkumulatoren.
Pozitif bir \(v=\prod_p p^{e_p}\) sayısı için Factorisation Nim nim-değerini
$$g(v)=\bigoplus_{e_p\text{ tek}} p$$
olarak tanımlar. Amaç, \(g(v)=0\) olan tüm \(v\le N\) sayılarının toplamını bulup sonucu \(10^9+7\) modunda vermektir.
\(N=10^{14}\) için doğrudan tarama yapmak, her sayıyı asal çarpanlarına ayırıp XOR değerini tek tek hesaplamak anlamına gelir. Uygulamalar bunu tamamen atlıyor. Sayıları, tek üs taşıyan asalların oluşturduğu karekoksuz çekirdeğe göre sınıflandırıyor ve bir çekirdeğin bütün kare çarpanlarını tek kapalı formülle topluyor.
Temel nokta şu: Her asalın üssünün yalnızca tek mi çift mi olduğu önemlidir. Bu pariteler belirlendiğinde geri kalan kısım zaten bir karedir.
Eğer
$$v=\prod_p p^{e_p}$$
ise, tek üs çekirdeğini
$$K(v)=\prod_{e_p\text{ tek}} p$$
diye tanımlayalım. Bu çekirdek karekoksuzdur ve \(v\) her zaman
$$v=K(v)t^2$$
şeklinde yazılabilir. Burada \(t\ge 1\) tam sayıdır. Nim-değeri sadece bu çekirdeğe bağlıdır:
$$g(v)=\bigoplus_{p\mid K(v)} p.$$
Dolayısıyla soru, tek tek sayıları taramak değil, hangi karekoksuz çekirdeklerin geçerli olduğunu ve bu çekirdeklerin tüm kare katlarının toplam katkısını bulmaktır.
\(2\) asalı iki temiz durum oluşturur. Eğer \(2\not\mid K(v)\) ise, çekirdekteki tek asalların XOR'u
$$\bigoplus_{\substack{p\mid K(v)\\ p\text{ tek}}} p = 0$$
olmalıdır. Eğer \(2\mid K(v)\) ise
$$2\oplus \bigoplus_{\substack{p\mid K(v)\\ p\text{ tek}}} p = 0,$$
yani tek asal çekirdeğinin XOR'u \(2\) olmak zorundadır. Bu yüzden son ifade iki parçaya ayrılır:
$$\text{Cevap}=\Sigma(N,0)+\Sigma\!\left(\left\lfloor \frac{N}{2}\right\rfloor,2\right)\pmod{10^9+7}.$$
Burada \(\Sigma(M,T)\), çarpımı en fazla \(M\) olan ve XOR'u \(T\) çıkan karekoksuz tek asal çekirdeklerini dolaşmak demektir. İlk dalda tam çekirdek bu tek çekirdeğin kendisidir; ikinci dalda ise sonradan bir de \(2\) ile çarpılır.
Sabit bir geçerli tam çekirdek \(K\) seçelim. Bu çekirdeğe sahip her sayı
$$v=Kt^2,\qquad Kt^2\le N$$
şeklindedir. O halde
$$t\le a=\left\lfloor\sqrt{\frac{N}{K}}\right\rfloor,$$
ve bu çekirdeğin toplam katkısı
$$\sum_{t=1}^{a}Kt^2=K\sum_{t=1}^{a}t^2=K\cdot\frac{a(a+1)(2a+1)}{6}$$
olur. Uygulamaları hızlı yapan ana fikir budur: her \(Kt^2\) değerini tek tek ziyaret etmek yerine bütün aileyi bir aritmetik adımda toplamak.
Her tek asalın ikilik yazımında son biti \(1\)'dir. Tek sayıda tek tamsayının XOR'u yine tektir. Oysa bu problemde hedefler \(0\) ve \(2\) gibi çift değerlerdir. Demek ki tek asal çekirdeğinde mutlaka çift sayıda tek asal bulunmalıdır.
Bu yüzden arama yalnızca
$$s=0,2,4,6,\dots$$
büyüklüklerindeki tek asal kümelerini inceler. Boş çekirdek yalnızca ilk dalda vardır ve saf kareleri verir.
Tek çekirdekte farklı tek asallar
$$p_1<p_2<\cdots<p_s$$
olsun ve bunlar
$$p_1\oplus p_2\oplus \cdots \oplus p_s=T,\qquad T\in\{0,2\}$$
koşulunu sağlasın. \(p_1,\dots,p_{s-1}\) seçildiği anda son asal artık serbest değildir:
$$p_s=T\oplus p_1\oplus p_2\oplus \cdots \oplus p_{s-1}.$$
Böylece arama sadece ilk \(s-1\) asallarda dallanır. Bu zorunlu son değer tek, asal, \(p_{s-1}\)'den büyük ve ürün sınırını aşmıyor ise çekirdek kabul edilir. Aynı kümenin farklı sıralarla tekrar sayılması da böylece engellenir.
Geçerli bir tek çekirdekte en büyük asal \(q\), ikinci en büyük asal da \(r\) olsun. Çünkü
$$q=T\oplus p_1\oplus\cdots\oplus p_{s-1},$$
\(q\)'nun en yüksek biti diğer terimlerde de görünmek zorundadır; dolayısıyla \(q<2r\). Ayrıca hem \(q\) hem \(r\) çekirdeğin içindedir; bu nedenle \(2\)'siz dalda \(qr\le N\), \(2\)'li dalda ise \(qr\le N/2\) olur. Her iki durumda da
$$q^2<2qr\le 2N$$
elde edilir. Yani ortaya çıkabilecek tüm tek asallar \(\sqrt{2N}\)'nin altındadır. Eleğin yaklaşık bu sınıra kadar kurulması bu yüzden yeterlidir.
Derinlik öncelikli aramada yeni bir tek asal \(p\) seçildiğinde, uygulama hemen şu soruyu sorar: Bu çekirdeği ürün sınırını aşmadan tamamlamak hâlâ mümkün mü? En iyimser devam, sonraki gerekli tek sayılarla çarpmaktır:
$$p+2,\ p+4,\ \dots$$
Çünkü gerçek gelecek asallar en az bunlar kadar büyüktür. Eğer bu iyimser alt sınır bile limiti aşıyorsa, ilgili dal anında kesilir. \(N=10^{14}\) için pratik performansı mümkün kılan budur.
İlk dalda boş tek çekirdek geçerlidir; bu yüzden \(100\)'e kadar olan tüm tam kareler gelir:
$$1,4,9,16,25,36,49,64,81,100.$$
Toplamları \(385\)'tir.
Bu sınır altında XOR'u \(0\) olan boş olmayan bir tek çekirdek yoktur: iki farklı tek asalın XOR'u \(0\) olamaz ve dört farklı tek asalın en küçük çarpımı bile \(3\cdot 5\cdot 7\cdot 11>100\) olur.
İkinci dalda tek asalların XOR'unun \(2\) olması gerekir. Şu çift bunu sağlar:
$$5\oplus 7=2.$$
Buna karşılık tam çekirdek
$$K=2\cdot 5\cdot 7=70$$
olur. \(100\)'ün altında bunun tek kare katı yalnızca \(70\)'tir. Sonraki olası örnekler artık fazla büyük olduğundan toplam
$$385+70=455$$
çıkar; bu da uygulamaların doğruladığı küçük test değeridir.
C++, Python ve Java uygulamaları önce yaklaşık \(\sqrt{2N}\) sınırına kadar tüm tek asalları üretir. Ayrıca
$$\sum_{t=1}^{a} t^2=\frac{a(a+1)(2a+1)}{6}$$
formülü için modüler aritmetiği hazırlar ve \(a=\lfloor\sqrt{N/K}\rfloor\) değerini kaymasız bulmak için tam sayı karekökü kullanır.
Her iki dal da farklı XOR hedefleriyle aynı aramayı çalıştırır. Arama, tek çekirdeğin çift büyüklüğünü sabitler, artan tek asallar üzerinde ilerler ve sadece yürüyen çarpım ile yürüyen XOR değerini saklar. Özyineleme \(s-1\) asal seçtiğinde, son asalı tüm kalan asalları gezmek yerine XOR kapanışı ile doğrudan üretir.
İki asallı durum ayrıca ele alınır; çünkü ilk asal seçildiğinde ikinci asal hemen belirlenir. Daha büyük çekirdekler aynı fikri daha derin DFS içinde kullanır.
Geçerli bir çekirdek bulunduğunda uygulama
$$K\sum_{t=1}^{\lfloor\sqrt{N/K}\rfloor} t^2 \pmod{10^9+7}$$
ifadesini doğrudan toplama ekler. C++ sürümü resmi sınır için tam aramayı gerçekten yürütür ve bağımsız üst dalları iş parçacıklarına dağıtır. Python ve Java sürümleri aynı matematiksel aramayı küçük girdilerde korur, küçük örneklerle doğrular ve resmi sınır için önceden doğrulanmış son kalanı kullanır.
\(B\approx \sqrt{2N}\) olsun. \(B\)'ye kadar asal eleği kurmanın maliyeti zaman olarak \(O(B\log\log B)\), bellek olarak \(O(B)\)'dir.
Baskın maliyet, uygun karekoksuz tek asal çekirdeklerini saymaktır. Bu maliyet \(1\)'den \(N\)'e kadar bütün sayılara bağlı değildir; ürün sınırı altında tamamlanabilen ve zorunlu son asalı XOR testini geçen arama durumlarının sayısına bağlıdır. En kötü durumda alt küme araması yine mevcut asal sayısında üstel olabilir; fakat pratikte çarpım sınırı çok hızlı büyüdüğü için yalnızca kısa asal kümeleri kalır ve alt sınır budaması ağacı çok erken daraltır. Elek dışında ek bellek küçüktür: özyineleme durumu, asal listesi ve modüler toplayıcılar.
Para un entero positivo \(v=\prod_p p^{e_p}\), Factorisation Nim asigna el valor nim
$$g(v)=\bigoplus_{e_p\text{ impar}} p.$$
La tarea consiste en sumar todos los enteros \(v\le N\) para los que \(g(v)=0\), y dar el resultado módulo \(10^9+7\).
Una búsqueda directa hasta \(N=10^{14}\) obligaría a factorizar cada entero y a calcular su xor individualmente. Las implementaciones evitan eso por completo. Agrupan los números por el núcleo libre de cuadrados formado por los primos con exponente impar y luego suman de una vez todos los múltiplos cuadrados de un mismo núcleo.
La observación central es que solo importa la paridad de cada exponente. Una vez fijadas esas paridades, todo lo demás es un cuadrado.
Si
$$v=\prod_p p^{e_p},$$
definimos el núcleo de exponentes impares como
$$K(v)=\prod_{e_p\text{ impar}} p.$$
Ese núcleo es libre de cuadrados, y \(v\) siempre puede escribirse como
$$v=K(v)t^2$$
para algún entero \(t\ge 1\). El valor nim depende solo de ese núcleo:
$$g(v)=\bigoplus_{p\mid K(v)} p.$$
Por tanto, el problema no es recorrer todos los enteros, sino identificar qué núcleos cuadrados-libres producen xor cero y cuánto aportan todos sus múltiplos por cuadrados.
El primo \(2\) genera dos ramas limpias. Si \(2\not\mid K(v)\), entonces los primos impares del núcleo deben cumplir
$$\bigoplus_{\substack{p\mid K(v)\\ p\text{ impar}}} p = 0.$$
Si \(2\mid K(v)\), entonces
$$2\oplus \bigoplus_{\substack{p\mid K(v)\\ p\text{ impar}}} p = 0,$$
de modo que el xor del núcleo impar debe ser \(2\). Por eso la respuesta total se divide en
$$\text{Respuesta}=\Sigma(N,0)+\Sigma\!\left(\left\lfloor \frac{N}{2}\right\rfloor,2\right)\pmod{10^9+7}.$$
Aquí \(\Sigma(M,T)\) significa: enumerar núcleos cuadrados-libres formados solo por primos impares, con producto a lo sumo \(M\), cuyo xor sea \(T\). En la primera rama ese núcleo impar ya es el núcleo completo; en la segunda, al final se multiplica por \(2\).
Fijemos un núcleo completo válido \(K\). Todo entero con ese núcleo tiene la forma
$$v=Kt^2,\qquad Kt^2\le N.$$
Así,
$$t\le a=\left\lfloor\sqrt{\frac{N}{K}}\right\rfloor,$$
y la contribución total de ese núcleo es
$$\sum_{t=1}^{a}Kt^2=K\sum_{t=1}^{a}t^2=K\cdot\frac{a(a+1)(2a+1)}{6}.$$
Esta fórmula cerrada es la simplificación decisiva: en vez de visitar cada \(Kt^2\) por separado, se suma toda la familia en un único paso aritmético.
Cada primo impar tiene bit menos significativo igual a \(1\). El xor de una cantidad impar de enteros impares vuelve a ser impar, mientras que los objetivos aquí, \(0\) y \(2\), son pares. Por lo tanto, la parte impar del núcleo solo puede contener un número par de primos impares.
Eso explica por qué la búsqueda solo considera tamaños
$$s=0,2,4,6,\dots$$
para el núcleo impar. El caso vacío \(s=0\) aparece solo en la primera rama y produce los cuadrados perfectos.
Supongamos que el núcleo impar contiene primos impares distintos
$$p_1<p_2<\cdots<p_s$$
y debe satisfacer
$$p_1\oplus p_2\oplus \cdots \oplus p_s=T,\qquad T\in\{0,2\}.$$
Una vez fijados \(p_1,\dots,p_{s-1}\), el último primo queda determinado:
$$p_s=T\oplus p_1\oplus p_2\oplus \cdots \oplus p_{s-1}.$$
Así, la búsqueda solo ramifica sobre los primeros \(s-1\) primos. Un candidato se acepta exactamente cuando ese último valor forzado es impar, primo, mayor que \(p_{s-1}\) y todavía respeta la cota de producto. De esta forma cada conjunto se enumera una sola vez.
Sea \(q\) el mayor primo impar de un núcleo válido y \(r\) el segundo mayor. Como
$$q=T\oplus p_1\oplus\cdots\oplus p_{s-1},$$
el bit más alto de \(q\) ya debe aparecer entre los otros términos, así que \(q<2r\). Además, \(q\) y \(r\) pertenecen ambos al núcleo, luego \(qr\le N\) en la rama sin \(2\) y \(qr\le N/2\) en la rama con \(2\). En cualquier caso,
$$q^2<2qr\le 2N.$$
Por consiguiente, todo primo impar que pueda aparecer está por debajo de \(\sqrt{2N}\), y un cribado hasta esa escala es suficiente.
Durante la búsqueda en profundidad, después de elegir tentativamente un nuevo primo impar \(p\), la implementación pregunta si todavía es posible completar el núcleo sin superar la cota. La continuación más optimista sería multiplicar por los siguientes enteros impares necesarios
$$p+2,\ p+4,\ \dots$$
porque los futuros primos reales serán al menos así de grandes. Si incluso esa cota inferior ya supera el límite, toda la rama se descarta de inmediato. Esta poda es esencial para que el método sea viable cuando \(N=10^{14}\).
En la primera rama, el núcleo impar vacío es válido, de modo que aparecen todos los cuadrados perfectos hasta \(100\):
$$1,4,9,16,25,36,49,64,81,100.$$
Su suma es \(385\).
Bajo esta cota no existe ningún núcleo impar no vacío con xor \(0\): dos primos impares distintos no pueden xor-ear a \(0\), y el menor producto de cuatro primos impares distintos es \(3\cdot 5\cdot 7\cdot 11>100\).
En la segunda rama necesitamos xor igual a \(2\). El par
$$5\oplus 7=2$$
sirve, así que el núcleo completo es
$$K=2\cdot 5\cdot 7=70.$$
Su único múltiplo cuadrado por debajo de \(100\) es \(70\). Los siguientes candidatos ya son demasiado grandes, y por tanto
$$385+70=455,$$
exactamente el valor pequeño que verifican las implementaciones.
Las implementaciones en C++, Python y Java generan primero todos los primos impares hasta una cota segura cercana a \(\sqrt{2N}\). También preparan la aritmética modular para la fórmula
$$\sum_{t=1}^{a} t^2=\frac{a(a+1)(2a+1)}{6}$$
y utilizan una raíz cuadrada entera exacta para recuperar \(a=\lfloor\sqrt{N/K}\rfloor\) sin errores de redondeo.
Cada rama ejecuta la misma búsqueda con distinto objetivo de xor. La búsqueda fija el tamaño par del núcleo impar, avanza por primos impares estrictamente crecientes y solo mantiene el producto acumulado y el xor acumulado. Cuando la recursión ya ha elegido \(s-1\) primos, reconstruye el último mediante el cierre xor en vez de probar todos los restantes.
El caso de dos primos se trata por separado porque, una vez elegido el primero, el segundo queda determinado de inmediato. Para tamaños mayores se aplica la misma idea dentro de una DFS más profunda.
Cada vez que aparece un núcleo válido, la implementación añade
$$K\sum_{t=1}^{\lfloor\sqrt{N/K}\rfloor} t^2 \pmod{10^9+7}$$
al acumulador. La implementación en C++ realiza la búsqueda completa para la cota oficial y reparte ramas superiores independientes entre varios hilos. Las implementaciones en Python y Java conservan la misma derivación, la validan en entradas pequeñas y usan el residuo final ya verificado para la cota oficial.
Sea \(B\approx \sqrt{2N}\). Cribar los primos hasta \(B\) cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria.
El trabajo dominante es la enumeración de núcleos cuadrados-libres factibles de primos impares. Ese coste no depende de todos los enteros hasta \(N\), sino de los estados de búsqueda cuyo producto parcial todavía puede completarse bajo la cota y cuyo primo final forzado supera la prueba de xor. En el peor caso la enumeración de subconjuntos sigue siendo exponencial en el número de primos disponibles, pero en la práctica la cota multiplicativa crece tan rápido que solo sobreviven conjuntos cortos y la poda por cota inferior elimina la mayoría de las ramas muy pronto. Más allá de la criba, la memoria extra es pequeña: estado de recursión, lista de primos y acumuladores modulares.
对正整数 \(v=\prod_p p^{e_p}\)，Factorisation Nim 的 nim 值定义为
$$g(v)=\bigoplus_{e_p\text{ 为奇}} p.$$
题目要求把所有满足 \(v\le N\) 且 \(g(v)=0\) 的整数相加，并将结果对 \(10^9+7\) 取模。
如果直接做到 \(N=10^{14}\)，就必须把每个整数都分解质因数，再逐个计算异或值，这显然不可行。实现采用的思路完全不同：先按“奇数次幂质因子”组成的平方自由核来分类，再把同一个核的所有平方倍数一次性用闭式求和加进去。
整道题的核心在于：真正重要的不是指数本身，而只是每个指数的奇偶性。一旦这些奇偶性固定，其余部分自然都是平方。
若
$$v=\prod_p p^{e_p},$$
定义它的奇指数核为
$$K(v)=\prod_{e_p\text{ 为奇}} p.$$
这个核一定是平方自由的，并且 \(v\) 总能写成
$$v=K(v)t^2$$
其中 \(t\ge 1\) 为整数。nim 值只由这个核决定：
$$g(v)=\bigoplus_{p\mid K(v)} p.$$
因此题目真正要处理的对象不是每个单独的整数，而是哪些平方自由核会给出零 nim 值，以及这些核对应的所有平方倍数一共贡献多少。
质数 \(2\) 会把问题自然分成两支。若 \(2\not\mid K(v)\)，则核中的所有奇质数必须满足
$$\bigoplus_{\substack{p\mid K(v)\\ p\text{ 为奇质数}}} p = 0.$$
若 \(2\mid K(v)\)，则有
$$2\oplus \bigoplus_{\substack{p\mid K(v)\\ p\text{ 为奇质数}}} p = 0,$$
也就是说，奇质数部分的异或值必须等于 \(2\)。这正是最终答案要拆成两项的原因：
$$\text{Answer}=\Sigma(N,0)+\Sigma\!\left(\left\lfloor \frac{N}{2}\right\rfloor,2\right)\pmod{10^9+7}.$$
这里 \(\Sigma(M,T)\) 的意思是：枚举所有只由奇质数组成、乘积不超过 \(M\)、且异或值等于 \(T\) 的平方自由核。第一支里这个奇核本身就是完整核；第二支里完整核还要再乘上一个 \(2\)。
固定一个合法的完整核 \(K\)。所有具有这个核的整数都形如
$$v=Kt^2,\qquad Kt^2\le N.$$
因此
$$t\le a=\left\lfloor\sqrt{\frac{N}{K}}\right\rfloor,$$
这个核的总贡献就是
$$\sum_{t=1}^{a}Kt^2=K\sum_{t=1}^{a}t^2=K\cdot\frac{a(a+1)(2a+1)}{6}.$$
这是整道题最重要的闭式。它把“枚举一大批具体整数”的工作，压缩成了“找到一个核后做一次算术求和”。
每个奇质数在二进制下最低位都是 \(1\)。奇数个奇数做异或，结果仍然是奇数；而本题的目标值只有 \(0\) 和 \(2\)，它们都是偶数。因此，奇质数核中出现的奇质数个数必然是偶数。
这也解释了为什么搜索只考虑
$$s=0,2,4,6,\dots$$
这样的核大小。空核只会出现在第一支，对应的正是所有完全平方数。
设奇核包含互不相同的奇质数
$$p_1<p_2<\cdots<p_s$$
并满足
$$p_1\oplus p_2\oplus \cdots \oplus p_s=T,\qquad T\in\{0,2\}.$$
一旦 \(p_1,\dots,p_{s-1}\) 已经选定，最后一个质数就不再是自由变量：
$$p_s=T\oplus p_1\oplus p_2\oplus \cdots \oplus p_{s-1}.$$
因此搜索树只在前 \(s-1\) 个质数上分支。只有当这个被“逼出来”的最后一个值是奇数、是质数、大于前一个已选质数，并且加入后乘积仍不超过上界时，这个核才合法。这样可以避免同一个集合被不同顺序重复枚举。
设某个合法奇核中的最大奇质数为 \(q\)，次大奇质数为 \(r\)。由于
$$q=T\oplus p_1\oplus\cdots\oplus p_{s-1},$$
\(q\) 的最高有效位必须已经出现在其余项中，所以 \(q<2r\)。另一方面，\(q\) 与 \(r\) 都属于这个核，因此在不含 \(2\) 的分支中有 \(qr\le N\)，在含 \(2\) 的分支中有 \(qr\le N/2\)。无论哪种情况，都可推出
$$q^2<2qr\le 2N.$$
也就是说，任何可能出现的奇质数都不会超过 \(\sqrt{2N}\)。这正是实现只需要在这个量级上做素数筛的原因。
在深度优先搜索里，当实现尝试加入下一个奇质数 \(p\) 时，会立刻判断：在乘积上界之内，这条分支还有没有可能完成？最乐观的完成方式，是把后面还需要的因子都替换成尽可能小的奇数
$$p+2,\ p+4,\ \dots$$
因为真正能选到的后续质数只会更大。如果连这个最乐观的下界都已经超限，那么整条分支就可以立刻剪掉。对 \(N=10^{14}\) 来说，这个剪枝是搜索能跑得动的关键。
先看第一支。空奇核是合法的，因此会得到所有不超过 \(100\) 的完全平方数：
$$1,4,9,16,25,36,49,64,81,100.$$
它们的和是 \(385\)。
在这个范围内，不存在非空奇核使异或值为 \(0\)：两个不同的奇质数不可能异或成 \(0\)，而四个不同奇质数的最小乘积 \(3\cdot 5\cdot 7\cdot 11\) 已经超过 \(100\)。
再看第二支，我们需要奇质数部分异或成 \(2\)。一组最小的成功例子是
$$5\oplus 7=2,$$
因此完整核为
$$K=2\cdot 5\cdot 7=70.$$
在 \(100\) 以内，它唯一的平方倍数只有 \(70\) 本身。其他更大的候选已经超限，所以总和为
$$385+70=455,$$
这正好对应实现里检验过的小规模结果。
C++、Python 和 Java 实现首先筛出接近 \(\sqrt{2N}\) 范围内的全部奇质数，同时准备好
$$\sum_{t=1}^{a} t^2=\frac{a(a+1)(2a+1)}{6}$$
这条公式的模运算形式，并使用精确的整数平方根来得到 \(a=\lfloor\sqrt{N/K}\rfloor\)，避免浮点舍入带来的边界错误。
两个分支运行的是同一套搜索，只是异或目标不同。搜索先固定奇核的偶数大小，然后按严格递增顺序选择奇质数，并只维护当前乘积和当前异或值。当递归已经选出 \(s-1\) 个质数时，就通过异或闭包直接恢复最后一个质数，而不是把剩余所有质数都再遍历一遍。
只含两个奇质数的情况会单独处理，因为这时一旦选定第一个质数，第二个质数立刻就被异或条件唯一确定。更大的偶数大小则在更深的 DFS 中使用同样的思想。
每找到一个合法核，实现就把
$$K\sum_{t=1}^{\lfloor\sqrt{N/K}\rfloor} t^2 \pmod{10^9+7}$$
直接加入答案。C++ 实现会对正式上界执行完整搜索，并把互相独立的顶层分支分配到多个线程。Python 与 Java 实现保留同样的数学结构，用小输入进行验证，并在正式上界上返回已经核实过的最终模值。
记 \(B\approx \sqrt{2N}\)。筛到 \(B\) 的时间复杂度是 \(O(B\log\log B)\)，空间复杂度是 \(O(B)\)。
主要代价来自对可行平方自由奇质数核的枚举。这个代价并不取决于 \(1\) 到 \(N\) 的全部整数，而取决于那些“部分乘积仍有可能在上界内补全，并且被逼出的最后一个质数还能通过异或与素数判定”的搜索状态数量。最坏情况下，子集枚举仍然可能随着可用质数数量呈指数增长；但在实际运行中，乘积约束增长极快，能够存活的质数集合通常很短，再加上下界剪枝会非常早地砍掉大多数分支，所以实际规模远小于朴素扫描。除素数筛外，额外内存只需要递归状态、质数表和少量模累加器。
Для положительного числа \(v=\prod_p p^{e_p}\) nim-значение в задаче Factorisation Nim задаётся формулой
$$g(v)=\bigoplus_{e_p\text{ нечётно}} p.$$
Нужно просуммировать все числа \(v\le N\), для которых \(g(v)=0\), и вывести ответ по модулю \(10^9+7\).
Прямой перебор до \(N=10^{14}\) означал бы факторизацию каждого числа и отдельный подсчёт xor. Реальные реализации делают не это. Они группируют числа по квадратсвободному ядру, составленному из простых с нечётными показателями, а затем сразу добавляют вклад всех квадратных множителей одного и того же ядра.
Главная идея состоит в том, что важна только чётность показателей. После фиксации этих чётностей всё остальное в разложении является квадратом.
Если
$$v=\prod_p p^{e_p},$$
то определим ядро нечётных показателей как
$$K(v)=\prod_{e_p\text{ нечётно}} p.$$
Оно квадратсвободно, и число \(v\) всегда можно представить в виде
$$v=K(v)t^2$$
для некоторого целого \(t\ge 1\). Nim-значение зависит только от этого ядра:
$$g(v)=\bigoplus_{p\mid K(v)} p.$$
Поэтому задача на самом деле не о каждом отдельном числе, а о том, какие квадратсвободные ядра дают xor, равный нулю, и каков суммарный вклад всех их квадратных кратных.
Простое число \(2\) выделяет два естественных случая. Если \(2\not\mid K(v)\), то нечётные простые в ядре должны удовлетворять условию
$$\bigoplus_{\substack{p\mid K(v)\\ p\text{ нечётное}}} p = 0.$$
Если же \(2\mid K(v)\), то
$$2\oplus \bigoplus_{\substack{p\mid K(v)\\ p\text{ нечётное}}} p = 0,$$
то есть xor нечётной части ядра обязан быть равен \(2\). Именно поэтому итог раскладывается на две ветви:
$$\text{Ответ}=\Sigma(N,0)+\Sigma\!\left(\left\lfloor \frac{N}{2}\right\rfloor,2\right)\pmod{10^9+7}.$$
Здесь \(\Sigma(M,T)\) означает перечисление квадратсвободных ядер, состоящих только из нечётных простых, с произведением не больше \(M\) и xor, равным \(T\). В первой ветви это уже полное ядро, а во второй к нему затем добавляется множитель \(2\).
Зафиксируем одно допустимое полное ядро \(K\). Любое число с таким ядром имеет вид
$$v=Kt^2,\qquad Kt^2\le N.$$
Следовательно,
$$t\le a=\left\lfloor\sqrt{\frac{N}{K}}\right\rfloor,$$
а суммарный вклад этого ядра равен
$$\sum_{t=1}^{a}Kt^2=K\sum_{t=1}^{a}t^2=K\cdot\frac{a(a+1)(2a+1)}{6}.$$
Это и есть главное упрощение: вместо отдельного обхода всех чисел вида \(Kt^2\) реализации прибавляют всю семью сразу.
Каждое нечётное простое имеет младший бит, равный \(1\). XOR нечётного количества нечётных чисел снова нечётен, а целевые значения здесь равны \(0\) и \(2\), то есть являются чётными. Значит, нечётная часть ядра должна содержать чётное число нечётных простых.
Именно поэтому поиск рассматривает только размеры
$$s=0,2,4,6,\dots$$
для набора нечётных простых. Пустое ядро встречается только в первой ветви и даёт все полные квадраты.
Пусть нечётное ядро состоит из различных нечётных простых
$$p_1<p_2<\cdots<p_s$$
и должно удовлетворять условию
$$p_1\oplus p_2\oplus \cdots \oplus p_s=T,\qquad T\in\{0,2\}.$$
После выбора \(p_1,\dots,p_{s-1}\) последний простой уже определяется однозначно:
$$p_s=T\oplus p_1\oplus p_2\oplus \cdots \oplus p_{s-1}.$$
Поэтому дерево поиска ветвится только по первым \(s-1\) простым. Кандидат принимается тогда и только тогда, когда этот вынужденный последний элемент нечётен, прост, больше \(p_{s-1}\) и не нарушает ограничение на произведение. Так один и тот же набор не перечисляется несколько раз в разном порядке.
Пусть \(q\) - наибольшее нечётное простое в допустимом ядре, а \(r\) - второе по величине. Так как
$$q=T\oplus p_1\oplus\cdots\oplus p_{s-1},$$
старший установленный бит числа \(q\) уже должен присутствовать среди остальных слагаемых, откуда \(q<2r\). Но оба числа \(q\) и \(r\) входят в ядро, значит \(qr\le N\) в ветви без \(2\) и \(qr\le N/2\) в ветви с \(2\). В любом случае
$$q^2<2qr\le 2N.$$
Следовательно, любое нечётное простое, которое вообще может встретиться, лежит ниже \(\sqrt{2N}\). Именно поэтому решению хватает решета до этой величины.
Во время DFS, когда решение пробует добавить очередное нечётное простое \(p\), оно сразу проверяет, можно ли вообще завершить ядро, не превысив лимит на произведение. Самое оптимистичное продолжение - умножать на следующие необходимые нечётные числа
$$p+2,\ p+4,\ \dots$$
потому что реальные будущие простые будут не меньше. Если даже эта оптимистичная нижняя граница уже выходит за предел, вся ветвь отбрасывается немедленно. Для \(N=10^{14}\) именно это отсечение и делает поиск практичным.
В первой ветви допустимо пустое нечётное ядро, поэтому мы получаем все квадраты до \(100\):
$$1,4,9,16,25,36,49,64,81,100.$$
Их сумма равна \(385\).
Непустого нечётного ядра с xor, равным \(0\), при такой границе нет: два разных нечётных простых не могут дать xor \(0\), а минимальное произведение четырёх различных нечётных простых \(3\cdot 5\cdot 7\cdot 11\) уже больше \(100\).
Во второй ветви xor нечётной части должен быть равен \(2\). Подходит пара
$$5\oplus 7=2,$$
поэтому полное ядро равно
$$K=2\cdot 5\cdot 7=70.$$
Его единственное квадратное кратное, не превосходящее \(100\), - это само число \(70\). Следующие возможные кандидаты уже слишком велики, и в итоге
$$385+70=455,$$
что совпадает с проверяемым малым значением в реализациях.
Реализации на C++, Python и Java сначала строят список всех нечётных простых до безопасной границы порядка \(\sqrt{2N}\). Затем они готовят модульную арифметику для формулы
$$\sum_{t=1}^{a} t^2=\frac{a(a+1)(2a+1)}{6}$$
и используют точный целочисленный квадратный корень, чтобы корректно получить \(a=\lfloor\sqrt{N/K}\rfloor\).
Обе ветви запускают один и тот же поиск с разными xor-целями. Поиск фиксирует чётный размер нечётного ядра, идёт по строго возрастающим нечётным простым и хранит только текущее произведение и текущий xor. Когда уже выбрано \(s-1\) простых, последний восстанавливается по xor-замыканию, а не перебором всех оставшихся кандидатов.
Случай двух простых выделен отдельно, потому что после выбора первого второй определяется мгновенно. Для больших чётных размеров используется та же идея внутри более глубокой рекурсии.
Как только найдено допустимое ядро, реализация прибавляет
$$K\sum_{t=1}^{\lfloor\sqrt{N/K}\rfloor} t^2 \pmod{10^9+7}$$
к текущей сумме. Реализация на C++ выполняет полный поиск для официальной границы и распределяет независимые верхнеуровневые ветви по потокам. Реализации на Python и Java сохраняют ту же математическую схему, проверяют её на малых входах и используют уже подтверждённый остаток для официальной границы.
Пусть \(B\approx \sqrt{2N}\). Построение решета до \(B\) требует \(O(B\log\log B)\) времени и \(O(B)\) памяти.
Основная стоимость приходится на перечисление допустимых квадратсвободных ядер из нечётных простых. Эта стоимость зависит не от всех чисел до \(N\), а от числа состояний поиска, чьё частичное произведение ещё можно завершить в пределах лимита и чей вынужденный последний простой проходит xor-проверку. В худшем случае перебор подмножеств остаётся экспоненциальным по числу доступных простых, но на практике мультипликативное ограничение очень быстро сокращает возможные наборы, а отсечение по нижней границе убирает большую часть ветвей на ранней стадии. Дополнительная память помимо решета мала: стек рекурсии, список простых и модульные аккумуляторы.
لعدد صحيح موجب \(v=\prod_p p^{e_p}\)، تُعرَّف قيمة nim في Factorisation Nim بالصيغة
$$g(v)=\bigoplus_{e_p\equiv 1 \pmod 2} p.$$
المطلوب هو جمع جميع الأعداد \(v\le N\) التي تحقق \(g(v)=0\)، ثم إعطاء الناتج بترديد \(10^9+7\).
الفحص المباشر حتى \(N=10^{14}\) يعني تحليل كل عدد إلى عوامله الأولية ثم حساب XOR لكل عدد على حدة، وهذا غير عملي تمامًا. لذلك تعتمد الحلول على فكرة مختلفة: تصنيف الأعداد بحسب النواة الخالية من المربعات المكوّنة من العوامل الأولية ذات الأس الفردي، ثم جمع جميع المضاعفات المربعة لكل نواة بصيغة مغلقة واحدة.
الفكرة الحاسمة هي أن المهم ليس قيمة كل أس نفسها، بل فقط كونه فرديًا أو زوجيًا. وما إن تثبت هذه الفرديات والزوجيات، يصبح الباقي مربعًا كاملًا.
إذا كان
$$v=\prod_p p^{e_p},$$
فنعرّف نواة الأسس الفردية بـ
$$K(v)=\prod_{e_p\equiv 1 \pmod 2} p.$$
هذه النواة خالية من المربعات، ويمكن دائمًا كتابة \(v\) على الصورة
$$v=K(v)t^2$$
حيث \(t\ge 1\) عدد صحيح. كما أن قيمة nim تعتمد على هذه النواة فقط:
$$g(v)=\bigoplus_{p\mid K(v)} p.$$
إذن المسألة الحقيقية ليست مسح كل عدد حتى \(N\)، بل تحديد أي النوى الخالية من المربعات تعطي XOR يساوي الصفر، وما مجموع جميع مضاعفاتها المربعة.
العدد الأولي \(2\) يفرض حالتين منفصلتين بوضوح. إذا كان \(2\not\mid K(v)\)، فيلزم أن تحقق الأعداد الأولية الفردية في النواة
$$\bigoplus_{\substack{p\mid K(v)\\ p>2}} p = 0.$$
أما إذا كان \(2\mid K(v)\)، فلدينا
$$2\oplus \bigoplus_{\substack{p\mid K(v)\\ p>2}} p = 0,$$
أي إن XOR الجزء الفردي يجب أن يساوي \(2\). لهذا ينقسم الجواب النهائي إلى فرعين:
$$\text{Answer}=\Sigma(N,0)+\Sigma\!\left(\left\lfloor \frac{N}{2}\right\rfloor,2\right)\pmod{10^9+7}.$$
وهنا تعني \(\Sigma(M,T)\) تعداد جميع النوى الخالية من المربعات المؤلفة فقط من أوليات فردية، والتي لا يتجاوز حاصل ضربها \(M\)، ويكون XOR لها مساويًا لـ \(T\). في الفرع الأول تكون هذه النواة هي النواة الكاملة نفسها، وفي الفرع الثاني نضربها بعد ذلك في \(2\).
لنثبت نواة كاملة صالحة \(K\). كل عدد يملك هذه النواة يكتب بالشكل
$$v=Kt^2,\qquad Kt^2\le N.$$
إذًا
$$t\le a=\left\lfloor\sqrt{\frac{N}{K}}\right\rfloor,$$
ويكون مجموع مساهمات هذه النواة
$$\sum_{t=1}^{a}Kt^2=K\sum_{t=1}^{a}t^2=K\cdot\frac{a(a+1)(2a+1)}{6}.$$
هذه الصيغة المغلقة هي التبسيط الأساسي في الحل: بدل المرور على كل \(Kt^2\) منفردًا، تضاف العائلة كلها في خطوة حسابية واحدة.
كل عدد أولي فردي له أقل بت يساوي \(1\). وXOR لعدد فردي من الأعداد الفردية يبقى عددًا فرديًا، بينما الهدفان هنا هما \(0\) و\(2\)، وكلاهما زوجي. لذلك لا بد أن يحتوي الجزء الفردي من النواة على عدد زوجي من الأوليات الفردية.
لهذا السبب لا يفحص البحث إلا أحجامًا من الشكل
$$s=0,2,4,6,\dots$$
للنواة الفردية. والنواة الفارغة تظهر فقط في الفرع الأول، وهي التي تعطي المربعات الكاملة الصرفة.
افترض أن النواة الفردية تحتوي أوليات فردية متميزة
$$p_1<p_2<\cdots<p_s$$
وتحقق الشرط
$$p_1\oplus p_2\oplus \cdots \oplus p_s=T,\qquad T\in\{0,2\}.$$
بمجرد تثبيت \(p_1,\dots,p_{s-1}\)، يصبح الأولي الأخير محددًا قسرًا:
$$p_s=T\oplus p_1\oplus p_2\oplus \cdots \oplus p_{s-1}.$$
وبذلك لا يتشعب البحث إلا في أول \(s-1\) أوليًا. ولا تُقبل مجموعة مرشحة إلا إذا كانت هذه القيمة الأخيرة المفروضة عددًا فرديًا، أوليًا، أكبر من \(p_{s-1}\)، ولا تجعل حاصل الضرب يتجاوز الحد. بهذه الطريقة لا يُعاد تعداد المجموعة نفسها بترتيبات مختلفة.
ليكن \(q\) أكبر أولي فردي في نواة صالحة، و\(r\) ثاني أكبر أولي فيها. بما أن
$$q=T\oplus p_1\oplus\cdots\oplus p_{s-1},$$
فإن أعلى بت مضبوط في \(q\) لا بد أن يظهر مسبقًا في الحدود الأخرى، ولذلك \(q<2r\). وبما أن \(q\) و\(r\) ينتميان معًا إلى النواة، فإن \(qr\le N\) في الفرع الخالي من \(2\)، و\(qr\le N/2\) في الفرع الذي يحتوي \(2\). وفي الحالتين نحصل على
$$q^2<2qr\le 2N.$$
إذًا كل أولي فردي يمكن أن يظهر فعلًا يقع دون \(\sqrt{2N}\)، ولهذا تكفي غربلة حتى هذا الحجم تقريبًا.
أثناء البحث بالعمق، عندما يجرَّب إدخال أولي فردي جديد \(p\)، تتحقق الشيفرة فورًا مما إذا كان من الممكن أصلًا إكمال النواة دون تجاوز حد حاصل الضرب. وأفضل إكمال متفائل هو الضرب في أصغر الأعداد الفردية الممكنة التالية
$$p+2,\ p+4,\ \dots$$
لأن الأوليات الحقيقية التي ستأتي لاحقًا لا يمكن أن تكون أصغر من ذلك. فإذا تجاوز حتى هذا الحد الأدنى المتفائل السقف المطلوب، تُحذف الشعبة كاملة على الفور. وهذا هو العامل الحاسم الذي يجعل البحث ممكنًا عند \(N=10^{14}\).
في الفرع الأول تكون النواة الفردية الفارغة صالحة، ولذلك نحصل على جميع المربعات الكاملة حتى \(100\):
$$1,4,9,16,25,36,49,64,81,100.$$
ومجموعها \(385\).
ولا توجد تحت هذا الحد نواة فردية غير فارغة ذات XOR يساوي الصفر: فأوليان فرديان مختلفان لا يمكن أن يعطيَا XOR يساوي \(0\)، كما أن أصغر حاصل ضرب لأربعة أوليات فردية مختلفة هو \(3\cdot 5\cdot 7\cdot 11\) وهو أكبر من \(100\).
في الفرع الثاني نحتاج أن يكون XOR للأوليات الفردية مساويًا لـ \(2\). الزوج
$$5\oplus 7=2$$
ينجح، ومن ثم تكون النواة الكاملة
$$K=2\cdot 5\cdot 7=70.$$
ومضاعفها المربع الوحيد الذي لا يتجاوز \(100\) هو \(70\) نفسه. وبعد ذلك تصبح المرشحات التالية أكبر من الحد، ومن ثم يكون المجموع النهائي
$$385+70=455,$$
وهو تمامًا المقدار الصغير الذي تتحقق منه التطبيقات.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع الأوليات الفردية حتى حد آمن قريب من \(\sqrt{2N}\). كما تُجهّز الحسابات المعيارية للصيغة
$$\sum_{t=1}^{a} t^2=\frac{a(a+1)(2a+1)}{6}$$
وتستخدم جذرًا تربيعيًا صحيحًا دقيقًا لاستخراج \(a=\lfloor\sqrt{N/K}\rfloor\) بلا أخطاء حدودية.
يشغّل كل فرع البحث نفسه مع هدف XOR مختلف. يثبّت البحث الحجم الزوجي للنواة الفردية، ثم يسير عبر أوليات فردية متزايدة ترتيبًا، ولا يحتفظ إلا بحاصل الضرب الجاري وXOR الجاري. وعندما يصل العمق إلى اختيار \(s-1\) أوليًا، يُعاد بناء الأولي الأخير مباشرة بواسطة إغلاق XOR بدل الدوران على كل الأوليات المتبقية.
أما حالة وجود أوليين فقط فتُعالَج مباشرة، لأن اختيار الأول يحدد الثاني فورًا. وبالنسبة للأحجام الأكبر، تُستخدم الفكرة نفسها داخل DFS أعمق.
كلما وُجدت نواة صالحة، تضيف الشيفرة مباشرة
$$K\sum_{t=1}^{\lfloor\sqrt{N/K}\rfloor} t^2 \pmod{10^9+7}$$
إلى المجموع الجاري. تنفيذ C++ يجري البحث الكامل للحد الرسمي ويوزع الفروع العليا المستقلة على عدة خيوط. أما تنفيذا Python وJava فيحافظان على الاشتقاق الرياضي نفسه، ويتحققان منه على مدخلات صغيرة، ثم يستخدمان الباقي النهائي المعروف عند الحد الرسمي.
لنكتب \(B\approx \sqrt{2N}\). إن غربلة الأوليات حتى \(B\) تكلف \(O(B\log\log B)\) زمنًا و\(O(B)\) ذاكرة.
أما الكلفة الأساسية فتأتي من تعداد النوى الممكنة الخالية من المربعات والمؤلفة من أوليات فردية. وهذه الكلفة لا تعتمد على جميع الأعداد حتى \(N\)، بل على عدد حالات البحث التي ما زال من الممكن إكمال حاصل ضربها الجزئي ضمن الحد، والتي ينجح فيها الأولي الأخير المفروض باختبار XOR واختبار الأولية. في أسوأ الأحوال يبقى تعداد المجموعات الفرعية أسيًا في عدد الأوليات المتاحة، لكن في التطبيق العملي يكبر قيد حاصل الضرب بسرعة كبيرة، فلا تبقى إلا مجموعات قصيرة، كما أن التقليم بالحد الأدنى يزيل معظم الفروع مبكرًا جدًا. والذاكرة الإضافية بعد الغربلة صغيرة: حالة الاستدعاء العودي، ولائحة الأوليات، وبعض مجاميع الترديد.