The implementations do not simulate a square rolling step by step. Instead, they use a number-theoretic parametrization in which each admissible contribution is represented by an integer \(q \ge 1\), one of four companion values \(k \in \{4q+1,4q+2,4q+3,4q+4\}\), and a second parameter \(m\) with \(1 \le m \le q\).
The key invariant is primitiveness: a contribution is valid exactly when \(\gcd(m,k)=1\). The bound in the problem is imposed through the associated size parameter \(n\): the families \(k=4q+1\), \(4q+2\), and \(4q+4\) contribute at \(n=4q\), while \(k=4q+3\) contributes at \(n=4q+2\). So the total answer up to \(N\) is a cumulative sum over even \(n\), with no odd case at all.
Once the rolling-square geometry has been reduced to this parametrization, the problem becomes a clean coprime-counting question. The whole job is to evaluate the right coprime counts quickly and add them in the right four families.
Define
$$R(q,k)=\#\{1 \le m \le q : \gcd(m,k)=1\}.$$
The arithmetic structure visible in the implementations is then
$$S(N)=\sum_{q=1}^{\lfloor N/4 \rfloor}\Bigl(R(q,4q+1)+R(q,4q+2)+R(q,4q+4)\Bigr)+\sum_{q=1}^{\lfloor (N-2)/4 \rfloor}R(q,4q+3).$$
Equivalently, if \(F(n)\) denotes the contribution attached to one value of \(n\), then
$$F(4q)=R(q,4q+1)+R(q,4q+2)+R(q,4q+4), \qquad F(4q+2)=R(q,4q+3),$$
and \(F(n)=0\) for odd \(n\). That is the first important invariant: only the residue classes \(0\) and \(2\) modulo 4 can occur.
For fixed \(q\) and \(k\), the only thing that matters about \(m\) is whether it shares a prime factor with \(k\). Prime powers do not create new exclusions: if a prime \(p\) divides \(k\), then every multiple of \(p\) must be removed, regardless of whether \(p\) occurs once or many times in \(k\).
That is why the count depends only on the distinct prime divisors of \(k\). Writing
$$\operatorname{rad}(k)=\prod_{p \mid k} p,$$
the forbidden values of \(m\) are exactly the multiples of the primes dividing \(\operatorname{rad}(k)\).
Counting the complement of those forbidden multiples gives the exact formula
$$R(q,k)=\sum_{d \mid \operatorname{rad}(k)} \mu(d)\left\lfloor \frac{q}{d}\right\rfloor,$$
where \(\mu\) is the Möbius function. This is simply inclusion-exclusion written compactly: start with all \(q\) candidates, subtract multiples of each prime divisor of \(k\), add back multiples of each product of two distinct prime divisors, and continue alternating.
The implementations do not build a global Möbius table. They factor \(k\), list its distinct prime divisors, enumerate all subsets of that list, multiply the chosen primes to obtain \(d\), and add or subtract \(\left\lfloor q/d \right\rfloor\) according to the subset parity. That direct subset view matches the formula exactly.
Take \(q=2\). Then the three \(n=4q=8\) branches are \(k=9\), \(10\), and \(12\).
For \(k=12\), the distinct prime divisors are \(2\) and \(3\), so
$$R(2,12)=\left\lfloor\frac{2}{1}\right\rfloor-\left\lfloor\frac{2}{2}\right\rfloor-\left\lfloor\frac{2}{3}\right\rfloor+\left\lfloor\frac{2}{6}\right\rfloor=2-1-0+0=1.$$
Also, \(R(2,9)=2\) because both \(1\) and \(2\) are coprime to \(9\), and \(R(2,10)=1\) because only \(1\) is coprime to \(10\). Hence
$$F(8)=R(2,9)+R(2,10)+R(2,12)=2+1+1=4.$$
The \(4q+2\) branch gives \(n=10\) with \(k=11\), so
$$F(10)=R(2,11)=2.$$
At the smallest nontrivial level, \(q=1\) gives \(F(4)=3\) and \(F(6)=1\), so \(S(6)=4\), exactly matching the checkpoint embedded in the implementations.
The C++, Python, and Java implementations all evaluate the same arithmetic decomposition. They differ only in execution strategy, not in the mathematics.
A smallest-prime-factor table is precomputed up to \(N+4\). This is a linear sieve, so every later factorization of a candidate \(k\) can peel off its distinct prime divisors in near-constant amortized time per divisor instead of testing divisibility up to \(\sqrt{k}\).
For each required value of \(k\), the implementation extracts the distinct prime divisors, enumerates all subset products, and evaluates the inclusion-exclusion sum for \(R(q,k)\). Because the bound is \(m \le q\), each subset contributes exactly one floor term \(\left\lfloor q/d \right\rfloor\).
No symbolic simplification is required. The same routine works uniformly for \(4q+1\), \(4q+2\), \(4q+3\), and \(4q+4\).
The outer loop runs over \(q\) and evaluates the four admissible families, adding a branch only when its associated \(n\) is at most the requested bound. The native implementations split the \(q\)-interval into chunks, let each worker accumulate an exact local sum, and then reduce the partial sums at the end. The Python entry point delegates to the same compiled arithmetic, so it produces the same count rather than a different algorithm.
Let \(K=N+4\) and \(Q=\lfloor K/4 \rfloor\). The sieve phase is \(O(K)\) time and \(O(K)\) memory. That memory cost is the dominant storage use, because the smallest-prime-factor table has one entry per integer up to the limit.
The accumulation phase evaluates up to four candidate values of \(k\) for each \(q\). A single coprime count costs \(O(2^{\omega(k)})\), where \(\omega(k)\) is the number of distinct prime divisors of \(k\). For the target limit \(N=10^8\), every \(k \le 100000004\) has at most 8 distinct prime divisors, so each inclusion-exclusion pass uses at most \(2^8=256\) subset terms. In practice this makes the arithmetic phase very close to linear in the number of processed branches, and parallel chunking improves wall-clock time without changing the exact count.
Die Implementierungen simulieren kein Quadrat, das Zug für Zug rollt. Stattdessen verwenden sie eine zahlentheoretische Parametrisierung, in der jeder zulässige Beitrag durch eine ganze Zahl \(q \ge 1\), einen von vier Begleitwerten \(k \in \{4q+1,4q+2,4q+3,4q+4\}\) und einen zweiten Parameter \(m\) mit \(1 \le m \le q\) beschrieben wird.
Die entscheidende Invariante ist die Primitivität: Ein Beitrag ist genau dann gültig, wenn \(\gcd(m,k)=1\) gilt. Die Schranke der Aufgabe erscheint über den zugehörigen Größenparameter \(n\): Die Familien \(k=4q+1\), \(4q+2\) und \(4q+4\) tragen bei \(n=4q\) bei, während \(k=4q+3\) zu \(n=4q+2\) gehört. Damit ist die Gesamtsumme bis \(N\) eine Aufsummierung über gerade \(n\); ungerade Fälle treten gar nicht auf.
Sobald die Geometrie des rollenden Quadrats auf diese Parametrisierung reduziert ist, bleibt ein sauberes Problem des Zählens teilerfremder Zahlen übrig. Die gesamte Arbeit besteht darin, die richtigen Teilerfremdheitszahlen schnell auszuwerten und sie in den vier Familien korrekt zusammenzusetzen.
Definiere
$$R(q,k)=\#\{1 \le m \le q : \gcd(m,k)=1\}.$$
Die in den Implementierungen sichtbare arithmetische Struktur lautet dann
$$S(N)=\sum_{q=1}^{\lfloor N/4 \rfloor}\Bigl(R(q,4q+1)+R(q,4q+2)+R(q,4q+4)\Bigr)+\sum_{q=1}^{\lfloor (N-2)/4 \rfloor}R(q,4q+3).$$
Äquivalent dazu gilt mit dem Beitrag \(F(n)\) eines festen Werts \(n\)
$$F(4q)=R(q,4q+1)+R(q,4q+2)+R(q,4q+4), \qquad F(4q+2)=R(q,4q+3),$$
und \(F(n)=0\) für ungerade \(n\). Das ist die erste wichtige Invariante: Nur die Restklassen \(0\) und \(2\) modulo 4 kommen überhaupt vor.
Für feste \(q\) und \(k\) ist nur relevant, ob \(m\) einen Primfaktor mit \(k\) teilt. Potenzen von Primzahlen erzeugen keine neuen Verbote: Wenn eine Primzahl \(p\) ein Teiler von \(k\) ist, müssen alle Vielfachen von \(p\) ausgeschlossen werden, ganz gleich, mit welcher Exponentenzahl \(p\) in \(k\) vorkommt.
Deshalb hängt die Zählung nur von den verschiedenen Primteilern von \(k\) ab. Mit
$$\operatorname{rad}(k)=\prod_{p \mid k} p$$
sind die verbotenen Werte von \(m\) genau die Vielfachen der Primzahlen, die \(\operatorname{rad}(k)\) teilen.
Das Zählen des Komplements dieser verbotenen Vielfachen liefert die exakte Formel
$$R(q,k)=\sum_{d \mid \operatorname{rad}(k)} \mu(d)\left\lfloor \frac{q}{d}\right\rfloor,$$
wobei \(\mu\) die Möbius-Funktion ist. Das ist nichts anderes als Inklusion-Exklusion in kompakter Schreibweise: Man startet mit allen \(q\) Kandidaten, subtrahiert die Vielfachen jedes Primteilers von \(k\), addiert die Vielfachen jedes Produkts aus zwei verschiedenen Primteilern wieder hinzu und setzt dieses Wechselspiel fort.
Die Implementierungen bauen keine globale Möbius-Tabelle auf. Stattdessen zerlegen sie \(k\) in verschiedene Primteiler, enumerieren alle Teilmengen dieser Liste, multiplizieren die gewählten Primzahlen zu \(d\) und addieren oder subtrahieren \(\left\lfloor q/d \right\rfloor\) je nach Parität der Teilmenge. Genau so wird die Formel direkt ausgewertet.
Nimm \(q=2\). Dann sind die drei Zweige für \(n=4q=8\) durch \(k=9\), \(10\) und \(12\) gegeben.
Für \(k=12\) sind die verschiedenen Primteiler \(2\) und \(3\), also
$$R(2,12)=\left\lfloor\frac{2}{1}\right\rfloor-\left\lfloor\frac{2}{2}\right\rfloor-\left\lfloor\frac{2}{3}\right\rfloor+\left\lfloor\frac{2}{6}\right\rfloor=2-1-0+0=1.$$
Außerdem gilt \(R(2,9)=2\), weil sowohl \(1\) als auch \(2\) teilerfremd zu \(9\) sind, und \(R(2,10)=1\), weil nur \(1\) zu \(10\) teilerfremd ist. Damit folgt
$$F(8)=R(2,9)+R(2,10)+R(2,12)=2+1+1=4.$$
Der \(4q+2\)-Zweig liefert \(n=10\) mit \(k=11\), also
$$F(10)=R(2,11)=2.$$
Schon auf der kleinsten nichttrivialen Stufe liefert \(q=1\) die Werte \(F(4)=3\) und \(F(6)=1\), also \(S(6)=4\). Genau dieser Kontrollwert ist auch in den Implementierungen hinterlegt.
Die C++-, Python- und Java-Implementierungen werten alle dieselbe arithmetische Zerlegung aus. Sie unterscheiden sich nur in der Ausführungsstrategie, nicht in der Mathematik.
Bis \(N+4\) wird eine Tabelle des kleinsten Primfaktors vorab berechnet. Das ist ein lineares Sieb; dadurch kann jede spätere Faktorisierung eines Kandidaten \(k\) seine verschiedenen Primteiler praktisch direkt aus der Tabelle abziehen, statt alle Teiler bis \(\sqrt{k}\) zu testen.
Für jeden benötigten Wert \(k\) extrahiert die Implementierung die verschiedenen Primteiler, enumeriert alle Teilmengenprodukte und wertet damit die Inklusion-Exklusion-Summe für \(R(q,k)\) aus. Weil die Schranke \(m \le q\) lautet, liefert jede Teilmenge genau einen Fußboden-Term \(\left\lfloor q/d \right\rfloor\).
Es ist keine fallweise symbolische Vereinfachung nötig. Dieselbe Routine funktioniert unverändert für \(4q+1\), \(4q+2\), \(4q+3\) und \(4q+4\).
Die äußere Schleife läuft über \(q\) und prüft die vier zulässigen Familien; ein Zweig wird genau dann addiert, wenn sein zugehöriges \(n\) die geforderte Schranke nicht überschreitet. Die nativen Implementierungen teilen das \(q\)-Intervall in Blöcke, lassen jeden Worker eine exakte lokale Summe bilden und reduzieren diese Teilsummen erst am Ende. Der Python-Einstiegspunkt delegiert an dieselbe kompilierte Arithmetik und erzeugt daher keinen anderen Algorithmus, sondern dieselbe Zählung.
Seien \(K=N+4\) und \(Q=\lfloor K/4 \rfloor\). Die Siebphase benötigt \(O(K)\) Zeit und \(O(K)\) Speicher. Dieser Speicher ist der dominante Verbrauch, weil die Tabelle des kleinsten Primfaktors einen Eintrag für jede ganze Zahl bis zur Grenze enthält.
Die Summationsphase betrachtet für jedes \(q\) bis zu vier Kandidaten \(k\). Eine einzelne Teilerfremdheitszählung kostet \(O(2^{\omega(k)})\), wobei \(\omega(k)\) die Anzahl der verschiedenen Primteiler von \(k\) ist. Für die Zielgrenze \(N=10^8\) besitzt jedes \(k \le 100000004\) höchstens 8 verschiedene Primteiler; deshalb hat jeder Inklusion-Exklusion-Durchlauf höchstens \(2^8=256\) Teilmengen-Terme. Praktisch ist die arithmetische Phase damit fast linear in der Zahl der bearbeiteten Zweige, und die Blockparallelisierung verbessert nur die Laufzeit an der Wanduhr, nicht das exakte Ergebnis.
Uygulamalar kareyi adım adım yuvarlayarak simüle etmiyor. Bunun yerine, her geçerli katkının \(q \ge 1\) tam sayısı, \(k \in \{4q+1,4q+2,4q+3,4q+4\}\) biçimindeki dört eşlikçi değerden biri ve \(1 \le m \le q\) koşulunu sağlayan ikinci bir parametre ile temsil edildiği sayısal bir parametreleştirme kullanılıyor.
Belirleyici değişmez primitiflik koşuludur: bir katkı tam olarak \(\gcd(m,k)=1\) olduğunda geçerlidir. Problemin üst sınırı ilişkili boyut parametresi \(n\) üzerinden gelir: \(k=4q+1\), \(4q+2\) ve \(4q+4\) aileleri \(n=4q\) için katkı verirken, \(k=4q+3\) ailesi \(n=4q+2\) için katkı verir. Dolayısıyla \(N\)'e kadar olan toplam yalnızca çift \(n\) değerleri üzerinde birikimli bir toplamdır; tek \(n\) için hiç katkı yoktur.
Yuvarlanan kare geometrisi bu parametreleştirmeye indirgendikten sonra problem temiz bir aralarında asallık sayımına dönüşür. Yapılması gereken şey, doğru sayımları hızlıca hesaplamak ve bunları dört ailenin içine doğru şekilde yerleştirmektir.
Şunu tanımlayalım:
$$R(q,k)=\#\{1 \le m \le q : \gcd(m,k)=1\}.$$
Uygulamalarda görülen aritmetik yapı tam olarak
$$S(N)=\sum_{q=1}^{\lfloor N/4 \rfloor}\Bigl(R(q,4q+1)+R(q,4q+2)+R(q,4q+4)\Bigr)+\sum_{q=1}^{\lfloor (N-2)/4 \rfloor}R(q,4q+3)$$
şeklindedir. Eşdeğer olarak, tek bir \(n\) değerine karşılık gelen katkıyı \(F(n)\) ile gösterirsek
$$F(4q)=R(q,4q+1)+R(q,4q+2)+R(q,4q+4), \qquad F(4q+2)=R(q,4q+3),$$
ve tek \(n\) için \(F(n)=0\) olur. Bu ilk önemli değişmezdir: yalnızca 4'e göre \(0\) ve \(2\) kalan sınıfları ortaya çıkabilir.
Sabit \(q\) ve \(k\) için \(m\) hakkında önemli olan tek şey, \(k\) ile ortak bir asal çarpan paylaşıp paylaşmadığıdır. Asal kuvvetleri yeni bir yasak kümesi oluşturmaz: \(p\) asalı \(k\)'yi bölüyorsa, \(p\)'nin tüm katları dışarı atılmalıdır; \(p\)'nin \(k\) içinde bir kez ya da birçok kez görünmesi fark yaratmaz.
Bu nedenle sayım yalnızca \(k\)'nin farklı asal bölenlerine bağlıdır. Şöyle yazalım:
$$\operatorname{rad}(k)=\prod_{p \mid k} p.$$
O zaman yasaklı \(m\) değerleri tam olarak \(\operatorname{rad}(k)\)'yi bölen asalların katlarıdır.
Bu yasaklı katların tümleyeni sayıldığında kesin formül elde edilir:
$$R(q,k)=\sum_{d \mid \operatorname{rad}(k)} \mu(d)\left\lfloor \frac{q}{d}\right\rfloor,$$
burada \(\mu\) Möbius fonksiyonudur. Bu, dahil etme-hariç tutmanın kısa yazımıdır: önce tüm \(q\) adayla başlanır, sonra \(k\)'nin her asal böleninin katları çıkarılır, iki farklı asal bölenin çarpımının katları geri eklenir ve işaretler sırayla değiştirilir.
Uygulamalar küresel bir Möbius tablosu kurmaz. Bunun yerine \(k\)'yi çarpanlarına ayırır, farklı asal bölenleri listeler, bu listenin tüm alt kümelerini dolaşır, seçilen asalları çarparak \(d\)'yi oluşturur ve alt küme paritesine göre \(\left\lfloor q/d \right\rfloor\) terimini ekler ya da çıkarır. Kodun yaptığı şey formülün doğrudan açılımıdır.
\(q=2\) alalım. O zaman \(n=4q=8\) için gelen üç dal \(k=9\), \(10\) ve \(12\) olur.
\(k=12\) için farklı asal bölenler \(2\) ve \(3\) olduğundan
$$R(2,12)=\left\lfloor\frac{2}{1}\right\rfloor-\left\lfloor\frac{2}{2}\right\rfloor-\left\lfloor\frac{2}{3}\right\rfloor+\left\lfloor\frac{2}{6}\right\rfloor=2-1-0+0=1.$$
Ayrıca \(R(2,9)=2\) çünkü \(1\) ve \(2\), \(9\) ile aralarında asaldır; \(R(2,10)=1\) çünkü yalnızca \(1\), \(10\) ile aralarında asaldır. Bu yüzden
$$F(8)=R(2,9)+R(2,10)+R(2,12)=2+1+1=4.$$
\(4q+2\) dalı ise \(k=11\) ile \(n=10\) üretir; dolayısıyla
$$F(10)=R(2,11)=2.$$
En küçük trivial olmayan seviyede \(q=1\) için \(F(4)=3\) ve \(F(6)=1\) gelir; yani \(S(6)=4\). Bu değer, uygulamalardaki yerleşik kontrol ile tam olarak aynıdır.
C++, Python ve Java uygulamalarının hepsi aynı aritmetik ayrışımı hesaplar. Aralarındaki fark matematikte değil, yürütme stratejisindedir.
\(N+4\)'e kadar en küçük asal çarpan tablosu önceden hazırlanır. Bu doğrusal bir elektir; böylece aday bir \(k\) daha sonra çarpanlarına ayrılırken \(\sqrt{k}\)'ye kadar bölme denemek yerine farklı asal bölenler tablo yardımıyla çok hızlı biçimde çıkarılabilir.
Her gerekli \(k\) değeri için uygulama farklı asal bölenleri çıkarır, bütün alt küme çarpımlarını dolaşır ve \(R(q,k)\) için dahil etme-hariç tutma toplamını hesaplar. Sınır \(m \le q\) olduğu için her alt küme tam olarak bir \(\left\lfloor q/d \right\rfloor\) taban terimi üretir.
Ayrı ayrı sembolik sadeleştirme gerekmez. Aynı yordam \(4q+1\), \(4q+2\), \(4q+3\) ve \(4q+4\) için hiç değişmeden çalışır.
Dış döngü \(q\) üzerinde ilerler ve dört geçerli aileyi değerlendirir; yalnızca ilişkili \(n\) değeri istenen sınırı aşmıyorsa o dal toplama eklenir. Yerel uygulamalar \(q\) aralığını parçalara böler, her işçiye tam bir kısmi toplam hesaplatır ve kısmi sonuçları en sonda birleştirir. Python girişi de aynı derlenmiş aritmetiğe delege olur; dolayısıyla farklı bir algoritma değil, aynı sayımı üretir.
\(K=N+4\) ve \(Q=\lfloor K/4 \rfloor\) olsun. Elek aşaması \(O(K)\) zaman ve \(O(K)\) bellek kullanır. Baskın bellek maliyeti budur; çünkü en küçük asal çarpan tablosu, sınıra kadar her tamsayı için bir giriş taşır.
Toplama aşaması her \(q\) için en fazla dört aday \(k\) değeri işler. Tek bir aralarında asallık sayımı \(O(2^{\omega(k)})\) maliyetindedir; burada \(\omega(k)\), \(k\)'nin farklı asal bölen sayısıdır. Hedef sınır \(N=10^8\) için \(k \le 100000004\) olan her sayının en fazla 8 farklı asal böleni vardır; bu yüzden her dahil etme-hariç tutma geçişinde en fazla \(2^8=256\) alt küme terimi oluşur. Pratikte aritmetik aşama işlenen dal sayısına göre neredeyse doğrusaldır; parçalara bölünmüş paralelleştirme ise tam sonucu değiştirmeden yalnızca geçen süreyi kısaltır.
Las implementaciones no simulan un cuadrado rodando paso a paso. En su lugar usan una parametrización aritmética en la que cada contribución admisible queda representada por un entero \(q \ge 1\), uno de los cuatro valores asociados \(k \in \{4q+1,4q+2,4q+3,4q+4\}\), y un segundo parámetro \(m\) con \(1 \le m \le q\).
La invariante decisiva es la primitividad: una contribución es válida exactamente cuando \(\gcd(m,k)=1\). La cota del problema entra mediante el parámetro de tamaño \(n\): las familias \(k=4q+1\), \(4q+2\) y \(4q+4\) aportan en \(n=4q\), mientras que \(k=4q+3\) aporta en \(n=4q+2\). Por eso la suma total hasta \(N\) es una acumulación sobre valores pares de \(n\), y no aparece ningún caso impar.
Una vez que la geometría del cuadrado rodante se reduce a esta parametrización, el problema se convierte en un conteo de enteros coprimos. Toda la tarea consiste en evaluar rápidamente esos conteos y sumarlos en las cuatro familias correctas.
Definimos
$$R(q,k)=\#\{1 \le m \le q : \gcd(m,k)=1\}.$$
La estructura aritmética que aparece en las implementaciones es
$$S(N)=\sum_{q=1}^{\lfloor N/4 \rfloor}\Bigl(R(q,4q+1)+R(q,4q+2)+R(q,4q+4)\Bigr)+\sum_{q=1}^{\lfloor (N-2)/4 \rfloor}R(q,4q+3).$$
De forma equivalente, si \(F(n)\) denota la contribución asociada a un valor fijo de \(n\), entonces
$$F(4q)=R(q,4q+1)+R(q,4q+2)+R(q,4q+4), \qquad F(4q+2)=R(q,4q+3),$$
y \(F(n)=0\) para \(n\) impar. Esa es la primera invariante útil: solo pueden aparecer las clases \(0\) y \(2\) módulo 4.
Para \(q\) y \(k\) fijos, lo único importante sobre \(m\) es si comparte o no un factor primo con \(k\). Las potencias de primos no crean exclusiones nuevas: si un primo \(p\) divide a \(k\), entonces deben eliminarse todos los múltiplos de \(p\), sin importar si \(p\) aparece una vez o muchas veces en \(k\).
Por eso el conteo depende solo de los divisores primos distintos de \(k\). Si escribimos
$$\operatorname{rad}(k)=\prod_{p \mid k} p,$$
los valores prohibidos de \(m\) son exactamente los múltiplos de los primos que dividen a \(\operatorname{rad}(k)\).
Contar el complemento de esos múltiplos prohibidos da la fórmula exacta
$$R(q,k)=\sum_{d \mid \operatorname{rad}(k)} \mu(d)\left\lfloor \frac{q}{d}\right\rfloor,$$
donde \(\mu\) es la función de Möbius. Esto no es más que el principio de inclusión-exclusión en forma compacta: se empieza con los \(q\) candidatos, se restan los múltiplos de cada primo que divide a \(k\), se vuelven a sumar los múltiplos de cada producto de dos primos distintos, y así sucesivamente.
Las implementaciones no construyen una tabla global de Möbius. Factorizan cada \(k\), listan sus primos distintos, enumeran todos los subconjuntos de esa lista, multiplican los primos elegidos para obtener \(d\), y suman o restan \(\left\lfloor q/d \right\rfloor\) según la paridad del subconjunto. Esa enumeración de subconjuntos coincide exactamente con la fórmula.
Tomemos \(q=2\). Entonces las tres ramas con \(n=4q=8\) corresponden a \(k=9\), \(10\) y \(12\).
Para \(k=12\), los primos distintos son \(2\) y \(3\), así que
$$R(2,12)=\left\lfloor\frac{2}{1}\right\rfloor-\left\lfloor\frac{2}{2}\right\rfloor-\left\lfloor\frac{2}{3}\right\rfloor+\left\lfloor\frac{2}{6}\right\rfloor=2-1-0+0=1.$$
Además, \(R(2,9)=2\) porque tanto \(1\) como \(2\) son coprimos con \(9\), y \(R(2,10)=1\) porque solo \(1\) es coprimo con \(10\). Por tanto
$$F(8)=R(2,9)+R(2,10)+R(2,12)=2+1+1=4.$$
La rama \(4q+2\) produce \(n=10\) con \(k=11\), de modo que
$$F(10)=R(2,11)=2.$$
En el primer nivel no trivial, \(q=1\) da \(F(4)=3\) y \(F(6)=1\), así que \(S(6)=4\). Ese valor coincide exactamente con la comprobación incorporada en las implementaciones.
Las implementaciones en C++, Python y Java evalúan la misma descomposición aritmética. Solo cambia la estrategia de ejecución; la matemática es la misma.
Se precalcula una tabla del menor factor primo hasta \(N+4\). Es un cribado lineal, así que toda factorización posterior de un candidato \(k\) puede extraer sus factores primos distintos muy rápido, sin probar divisores hasta \(\sqrt{k}\).
Para cada valor necesario de \(k\), la implementación extrae los factores primos distintos, enumera todos los productos de subconjuntos y evalúa con ellos la suma de inclusión-exclusión para \(R(q,k)\). Como la cota es \(m \le q\), cada subconjunto aporta exactamente un término \(\left\lfloor q/d \right\rfloor\).
No hace falta ninguna simplificación simbólica especial. La misma rutina sirve sin cambios para \(4q+1\), \(4q+2\), \(4q+3\) y \(4q+4\).
El bucle exterior recorre \(q\) y evalúa las cuatro familias admisibles, añadiendo una rama solo cuando su \(n\) asociado no supera la cota pedida. Las implementaciones nativas parten el intervalo de \(q\) en bloques, hacen que cada trabajador calcule una suma local exacta y reducen las parciales al final. La entrada en Python delega en la misma aritmética compilada, así que produce el mismo conteo y no un algoritmo distinto.
Sea \(K=N+4\) y \(Q=\lfloor K/4 \rfloor\). La fase del cribado cuesta \(O(K)\) tiempo y \(O(K)\) memoria. Ese uso de memoria es el dominante, porque la tabla del menor factor primo tiene una entrada por cada entero hasta el límite.
La fase de acumulación evalúa hasta cuatro candidatos \(k\) por cada \(q\). Un único conteo de coprimos cuesta \(O(2^{\omega(k)})\), donde \(\omega(k)\) es el número de factores primos distintos de \(k\). Para el límite objetivo \(N=10^8\), todo \(k \le 100000004\) tiene como mucho 8 factores primos distintos, así que cada pasada de inclusión-exclusión usa a lo sumo \(2^8=256\) términos de subconjuntos. En la práctica esto deja la fase aritmética muy cerca de ser lineal en el número de ramas procesadas, y la partición en bloques paralelos solo mejora el tiempo de pared sin alterar el conteo exacto.
这些实现并不是按步骤去模拟一个正方形在平面上滚动。它们采用的是一种数论参数化：每一个有效贡献都由一个整数 \(q \ge 1\)、四个伴随值 \(k \in \{4q+1,4q+2,4q+3,4q+4\}\) 中的一个，以及满足 \(1 \le m \le q\) 的第二个参数 \(m\) 来表示。
最关键的不变量是“原始性”条件：一项贡献成立，当且仅当 \(\gcd(m,k)=1\)。题目中的上界通过关联的规模参数 \(n\) 进入公式：族 \(k=4q+1\)、\(4q+2\)、\(4q+4\) 都对应 \(n=4q\)，而 \(k=4q+3\) 对应 \(n=4q+2\)。因此到 \(N\) 为止的总答案，其实只是对偶数 \(n\) 的累计求和，奇数 \(n\) 完全不会出现。
一旦把滚动正方形的几何结构压缩成这套参数，问题就变成了一个纯粹的互素计数问题。真正需要做的只有两件事：快速算出正确的互素个数，以及把它们放回四个合法分支里求和。
定义
$$R(q,k)=\#\{1 \le m \le q : \gcd(m,k)=1\}.$$
代码里对应的总结构是
$$S(N)=\sum_{q=1}^{\lfloor N/4 \rfloor}\Bigl(R(q,4q+1)+R(q,4q+2)+R(q,4q+4)\Bigr)+\sum_{q=1}^{\lfloor (N-2)/4 \rfloor}R(q,4q+3).$$
也可以把它写成单个 \(n\) 的贡献函数 \(F(n)\)：
$$F(4q)=R(q,4q+1)+R(q,4q+2)+R(q,4q+4), \qquad F(4q+2)=R(q,4q+3),$$
而对奇数 \(n\) 有 \(F(n)=0\)。这就是第一个重要不变量：只有模 4 余 \(0\) 或 \(2\) 的规模值才会产生贡献。
对固定的 \(q\) 与 \(k\) 而言，参数 \(m\) 唯一重要的性质就是它是否与 \(k\) 共享某个素因子。素数幂不会带来新的限制：只要素数 \(p\) 整除 \(k\)，那么所有 \(p\) 的倍数都必须剔除，而 \(p\) 在 \(k\) 中出现一次还是多次并不改变这一点。
因此，计数只依赖于 \(k\) 的不同素因子。记
$$\operatorname{rad}(k)=\prod_{p \mid k} p,$$
那么所有被禁止的 \(m\) 恰好就是被 \(\operatorname{rad}(k)\) 的某个素因子整除的那些数。
对这些被禁止倍数的补集进行计数，就得到精确公式
$$R(q,k)=\sum_{d \mid \operatorname{rad}(k)} \mu(d)\left\lfloor \frac{q}{d}\right\rfloor,$$
其中 \(\mu\) 是 Möbius 函数。这就是容斥原理的紧凑写法：先把全部 \(q\) 个候选都算进去，再减去每个素因子的倍数，加回任意两个不同素因子乘积的倍数，然后继续交替下去。
实现并没有先构造一整张 Möbius 表，而是对每个 \(k\) 单独分解质因数，取出其中互不相同的素数，枚举这些素数的所有子集，把选中的素数相乘得到 \(d\)，再按子集大小的奇偶性去加减 \(\left\lfloor q/d \right\rfloor\)。这与上面的公式是一一对应的。
取 \(q=2\)。这时 \(n=4q=8\) 的三条分支分别对应 \(k=9\)、\(10\) 与 \(12\)。
对 \(k=12\) 而言，不同素因子是 \(2\) 和 \(3\)，于是
$$R(2,12)=\left\lfloor\frac{2}{1}\right\rfloor-\left\lfloor\frac{2}{2}\right\rfloor-\left\lfloor\frac{2}{3}\right\rfloor+\left\lfloor\frac{2}{6}\right\rfloor=2-1-0+0=1.$$
另外，\(R(2,9)=2\)，因为 \(1\) 和 \(2\) 都与 \(9\) 互素；而 \(R(2,10)=1\)，因为只有 \(1\) 与 \(10\) 互素。因此
$$F(8)=R(2,9)+R(2,10)+R(2,12)=2+1+1=4.$$
\(4q+2\) 这一支给出的是 \(n=10\)，对应 \(k=11\)，所以
$$F(10)=R(2,11)=2.$$
在最小的非平凡情形里，\(q=1\) 给出 \(F(4)=3\) 和 \(F(6)=1\)，从而 \(S(6)=4\)。这恰好与实现中的校验值完全一致。
C++、Python 和 Java 三个实现计算的是同一套算术分解。它们的差别只在执行方式，不在数学内容。
程序会先预计算一张到 \(N+4\) 为止的最小素因子表。这是一个线性筛，因此之后任何候选 \(k\) 的分解都可以非常快地抽出所有不同素因子，而不必再去试除到 \(\sqrt{k}\)。
对每个需要的 \(k\)，实现先取出不同素因子，再枚举所有子集乘积，并用这些子集项来计算 \(R(q,k)\) 的容斥和。由于上界是 \(m \le q\)，每个子集只对应一个地板函数项 \(\left\lfloor q/d \right\rfloor\)。
这里不需要针对不同分支做额外的符号化简。完全相同的过程可以统一处理 \(4q+1\)、\(4q+2\)、\(4q+3\) 和 \(4q+4\)。
外层循环遍历 \(q\)，检查四个合法分支，并且只有当该分支对应的 \(n\) 没有超过要求上界时才把它加入答案。原生实现会把 \(q\) 的区间切成若干块，让每个工作线程独立累加出一个精确的局部和，最后再把这些部分结果合并。Python 入口调用的是同一套已编译的算术核心，因此它得到的是同一个计数，而不是另一种算法。
记 \(K=N+4\)，\(Q=\lfloor K/4 \rfloor\)。筛法阶段的时间复杂度是 \(O(K)\)，空间复杂度也是 \(O(K)\)。这份空间就是主要内存开销，因为最小素因子表需要为上界以内的每一个整数存一个条目。
累加阶段对每个 \(q\) 最多检查四个候选值 \(k\)。一次互素计数的代价是 \(O(2^{\omega(k)})\)，其中 \(\omega(k)\) 表示 \(k\) 的不同素因子个数。对于目标上界 \(N=10^8\)，所有 \(k \le 100000004\) 的数最多只含有 8 个不同素因子，所以每次容斥最多只需要 \(2^8=256\) 个子集项。实际运行时，这使得算术阶段非常接近于按已处理分支数线性增长，而分块并行只会改善墙钟时间，不会改变精确结果。
Реализации не моделируют катящийся квадрат шаг за шагом. Вместо этого используется арифметическая параметризация, в которой каждый допустимый вклад задается целым числом \(q \ge 1\), одним из четырех сопутствующих значений \(k \in \{4q+1,4q+2,4q+3,4q+4\}\) и вторым параметром \(m\), удовлетворяющим \(1 \le m \le q\).
Ключевой инвариант здесь состоит в примитивности: вклад допустим ровно тогда, когда \(\gcd(m,k)=1\). Ограничение задачи входит через связанный параметр размера \(n\): семейства \(k=4q+1\), \(4q+2\) и \(4q+4\) дают вклад при \(n=4q\), а семейство \(k=4q+3\) относится к \(n=4q+2\). Поэтому итоговая сумма до \(N\) накапливается только по четным значениям \(n\); нечетные случаи вообще не возникают.
После того как геометрия катящегося квадрата сведена к этой параметризации, задача превращается в чистое подсчитывание взаимно простых чисел. Дальше нужно лишь быстро вычислить правильные значения и сложить их по четырем допустимым семействам.
Определим
$$R(q,k)=\#\{1 \le m \le q : \gcd(m,k)=1\}.$$
Тогда арифметическая структура, которую прямо используют реализации, имеет вид
$$S(N)=\sum_{q=1}^{\lfloor N/4 \rfloor}\Bigl(R(q,4q+1)+R(q,4q+2)+R(q,4q+4)\Bigr)+\sum_{q=1}^{\lfloor (N-2)/4 \rfloor}R(q,4q+3).$$
Иначе говоря, если \(F(n)\) обозначает вклад, соответствующий одному значению \(n\), то
$$F(4q)=R(q,4q+1)+R(q,4q+2)+R(q,4q+4), \qquad F(4q+2)=R(q,4q+3),$$
а для нечетных \(n\) имеем \(F(n)=0\). Это первый важный инвариант: возможны только классы \(0\) и \(2\) по модулю 4.
При фиксированных \(q\) и \(k\) о параметре \(m\) важно только одно: делит ли его какой-нибудь простой делитель числа \(k\). Степени простых чисел не дают новых ограничений: если простой \(p\) делит \(k\), то нужно исключить все кратные \(p\), независимо от того, входит ли \(p\) в \(k\) в первой степени или в более высокой.
Именно поэтому подсчет зависит только от различных простых делителей числа \(k\). Если обозначить
$$\operatorname{rad}(k)=\prod_{p \mid k} p,$$
то запрещенные значения \(m\) — это в точности все числа, кратные простым делителям \(\operatorname{rad}(k)\).
Подсчет дополнения к этому множеству запрещенных кратных дает точную формулу
$$R(q,k)=\sum_{d \mid \operatorname{rad}(k)} \mu(d)\left\lfloor \frac{q}{d}\right\rfloor,$$
где \(\mu\) — функция Мёбиуса. Это и есть принцип включения-исключения в компактной записи: сначала берутся все \(q\) кандидатов, затем вычитаются кратные каждого простого делителя \(k\), потом добавляются обратно кратные произведений двух различных простых делителей и так далее со сменой знака.
Реализации не строят глобальную таблицу значений функции Мёбиуса. Они факторизуют каждое \(k\), выписывают его различные простые делители, перебирают все подмножества этого списка, перемножают выбранные простые числа, чтобы получить \(d\), и затем прибавляют или вычитают \(\left\lfloor q/d \right\rfloor\) в зависимости от четности размера подмножества. Это буквальная реализация формулы.
Возьмем \(q=2\). Тогда три ветви для \(n=4q=8\) соответствуют значениям \(k=9\), \(10\) и \(12\).
Для \(k=12\) различными простыми делителями являются \(2\) и \(3\), поэтому
$$R(2,12)=\left\lfloor\frac{2}{1}\right\rfloor-\left\lfloor\frac{2}{2}\right\rfloor-\left\lfloor\frac{2}{3}\right\rfloor+\left\lfloor\frac{2}{6}\right\rfloor=2-1-0+0=1.$$
Кроме того, \(R(2,9)=2\), потому что и \(1\), и \(2\) взаимно просты с \(9\), а \(R(2,10)=1\), потому что с \(10\) взаимно просто только число \(1\). Следовательно,
$$F(8)=R(2,9)+R(2,10)+R(2,12)=2+1+1=4.$$
Ветвь \(4q+2\) дает \(n=10\) при \(k=11\), так что
$$F(10)=R(2,11)=2.$$
На самом маленьком нетривиальном уровне \(q=1\) получаем \(F(4)=3\) и \(F(6)=1\), откуда \(S(6)=4\). Это в точности совпадает с контрольным значением, встроенным в реализации.
Реализации на C++, Python и Java вычисляют одну и ту же арифметическую декомпозицию. Различается только способ исполнения, но не сама математика.
До значения \(N+4\) заранее строится таблица наименьшего простого делителя. Это линейное решето, поэтому любая последующая факторизация числа \(k\) может очень быстро извлечь все его различные простые делители, не перебирая делители вплоть до \(\sqrt{k}\).
Для каждого нужного значения \(k\) реализация извлекает различные простые делители, перебирает все произведения подмножеств и по ним вычисляет сумму включения-исключения для \(R(q,k)\). Поскольку ограничение имеет вид \(m \le q\), каждое подмножество дает ровно один член \(\left\lfloor q/d \right\rfloor\).
Никакой отдельной символической обработки для разных ветвей не требуется. Одна и та же процедура без изменений работает для \(4q+1\), \(4q+2\), \(4q+3\) и \(4q+4\).
Внешний цикл идет по \(q\), проверяет четыре допустимых семейства и добавляет ветвь только тогда, когда связанное с ней значение \(n\) не превышает нужной границы. Нативные реализации делят диапазон \(q\) на блоки, позволяют каждому рабочему потоку накопить точную локальную сумму и затем сводят частичные результаты в конце. Точка входа Python делегирует той же скомпилированной арифметике, так что она выдает тот же самый подсчет, а не другой алгоритм.
Пусть \(K=N+4\), а \(Q=\lfloor K/4 \rfloor\). Фаза решета занимает \(O(K)\) времени и \(O(K)\) памяти. Этот расход памяти является основным, потому что таблица наименьших простых делителей хранит по одному значению для каждого целого числа до границы.
Фаза накопления рассматривает до четырех кандидатов \(k\) для каждого \(q\). Один подсчет взаимно простых чисел стоит \(O(2^{\omega(k)})\), где \(\omega(k)\) — число различных простых делителей числа \(k\). Для целевой границы \(N=10^8\) любое \(k \le 100000004\) имеет не более 8 различных простых делителей, поэтому в каждом проходе включения-исключения используется не более \(2^8=256\) подмножеств. На практике это делает арифметическую фазу почти линейной по числу обработанных ветвей, а разбиение на параллельные блоки уменьшает только время выполнения, не меняя точного результата.
التنفيذات لا تحاكي مربعا يتدحرج خطوة بعد خطوة. بدلا من ذلك فهي تستخدم توصيفا عدديا تصبح فيه كل مساهمة صالحة ممثلة بعدد صحيح \(q \ge 1\)، وبأحد القيم الأربع المرافقة \(k \in \{4q+1,4q+2,4q+3,4q+4\}\)، وبمعامل ثان \(m\) يحقق \(1 \le m \le q\).
الثابت الأهم هنا هو شرط الأولية: تكون المساهمة صالحة إذا وفقط إذا تحقق \(\gcd(m,k)=1\). يدخل حد المسألة عبر وسيط الحجم الموافق \(n\): العائلات \(k=4q+1\) و\(4q+2\) و\(4q+4\) تسهم عند \(n=4q\)، بينما العائلة \(k=4q+3\) تسهم عند \(n=4q+2\). لذلك فإن المجموع الكلي حتى \(N\) هو تجميع تراكمي فوق قيم \(n\) الزوجية فقط، ولا تظهر أي حالة فردية.
بعد اختزال هندسة المربع المتدحرج إلى هذا التمثيل، تتحول المسألة إلى عدٍّ نظيف للأعداد المتباينة أوليا. والمطلوب فعلا هو حساب هذه الأعداد بسرعة ثم جمعها داخل العائلات الأربع الصحيحة.
لنعرّف
$$R(q,k)=\#\{1 \le m \le q : \gcd(m,k)=1\}.$$
وعندها تصبح البنية الحسابية الظاهرة في التنفيذات هي
$$S(N)=\sum_{q=1}^{\lfloor N/4 \rfloor}\Bigl(R(q,4q+1)+R(q,4q+2)+R(q,4q+4)\Bigr)+\sum_{q=1}^{\lfloor (N-2)/4 \rfloor}R(q,4q+3).$$
وبصورة مكافئة، إذا رمزنا بمساهمة القيمة \(n\) الواحدة إلى \(F(n)\)، فلدينا
$$F(4q)=R(q,4q+1)+R(q,4q+2)+R(q,4q+4), \qquad F(4q+2)=R(q,4q+3),$$
بينما \(F(n)=0\) عندما يكون \(n\) فرديا. وهذا هو أول ثابت مهم: لا تظهر إلا فئتَا البواقي \(0\) و\(2\) بترديد 4.
عند تثبيت \(q\) و\(k\)، فإن الشيء الوحيد المهم في \(m\) هو ما إذا كان يشترك مع \(k\) في عامل أولي. قوى الأعداد الأولية لا تضيف قيودا جديدة: فإذا كان العدد الأولي \(p\) يقسم \(k\)، فيجب استبعاد جميع مضاعفات \(p\)، سواء ظهر \(p\) مرة واحدة أو مرات عدة داخل \(k\).
ولهذا يعتمد العد فقط على العوامل الأولية المميزة للعدد \(k\). وإذا كتبنا
$$\operatorname{rad}(k)=\prod_{p \mid k} p,$$
فإن القيم الممنوعة لـ \(m\) هي بالضبط مضاعفات الأعداد الأولية التي تقسم \(\operatorname{rad}(k)\).
بعدّ متممة هذه المضاعفات الممنوعة نحصل على الصيغة الدقيقة
$$R(q,k)=\sum_{d \mid \operatorname{rad}(k)} \mu(d)\left\lfloor \frac{q}{d}\right\rfloor,$$
حيث \(\mu\) هي دالة موبيوس. وهذه ليست إلا مبدأ الاشتمال والاستبعاد بصياغة مضغوطة: نبدأ بكل المرشحين وعددهم \(q\)، ثم نطرح مضاعفات كل عامل أولي يقسم \(k\)، ثم نعيد إضافة مضاعفات حاصل ضرب كل عاملين أوليين مختلفين، ونستمر بالتناوب نفسه.
التنفيذات لا تبني جدولا عاما لقيم موبيوس. بل تفكك كل \(k\) إلى عوامله الأولية المميزة، ثم تعدّد كل المجموعات الجزئية لتلك القائمة، وتضرب العوامل المختارة للحصول على \(d\)، ثم تضيف أو تطرح \(\left\lfloor q/d \right\rfloor\) بحسب زوجية حجم المجموعة. وهذا يطابق الصيغة السابقة حرفيا.
خذ \(q=2\). عندئذ تكون الفروع الثلاثة الخاصة بـ \(n=4q=8\) هي \(k=9\) و\(10\) و\(12\).
بالنسبة إلى \(k=12\)، فإن العوامل الأولية المميزة هي \(2\) و\(3\)، ولذلك
$$R(2,12)=\left\lfloor\frac{2}{1}\right\rfloor-\left\lfloor\frac{2}{2}\right\rfloor-\left\lfloor\frac{2}{3}\right\rfloor+\left\lfloor\frac{2}{6}\right\rfloor=2-1-0+0=1.$$
كذلك فإن \(R(2,9)=2\) لأن كلا من \(1\) و\(2\) متباين أوليا مع \(9\)، بينما \(R(2,10)=1\) لأن العدد \(1\) وحده هو المتباين أوليا مع \(10\). ومن ثم
$$F(8)=R(2,9)+R(2,10)+R(2,12)=2+1+1=4.$$
أما فرع \(4q+2\) فيعطي \(n=10\) مع \(k=11\)، ولذلك
$$F(10)=R(2,11)=2.$$
وفي أصغر مستوى غير تافه، يعطي \(q=1\) القيمتين \(F(4)=3\) و\(F(6)=1\)، ومن ثم \(S(6)=4\). وهذا يطابق تماما قيمة التحقق المدمجة في التنفيذات.
التنفيذات في C++ وPython وJava تحسب التفكيك الحسابي نفسه. الاختلاف بينها في أسلوب التنفيذ فقط، لا في الرياضيات.
يُحسب مسبقا جدول لأصغر عامل أولي حتى \(N+4\). وهذا غربال خطي، لذا فإن أي تفكيك لاحق لعدد مرشح \(k\) يستطيع استخراج عوامله الأولية المميزة بسرعة كبيرة بدلا من اختبار القواسم حتى \(\sqrt{k}\).
لكل قيمة مطلوبة من \(k\)، تستخرج الشيفرة العوامل الأولية المميزة، ثم تعدّد جميع حاصل ضربات المجموعات الجزئية، وبها تقيّم مجموع الاشتمال والاستبعاد الموافق لـ \(R(q,k)\). وبما أن الحد هو \(m \le q\)، فإن كل مجموعة جزئية تسهم بحد واحد فقط من الشكل \(\left\lfloor q/d \right\rfloor\).
لا حاجة إلى أي تبسيط رمزي منفصل. فالروتين نفسه يعمل دون تغيير مع \(4q+1\) و\(4q+2\) و\(4q+3\) و\(4q+4\).
تدور الحلقة الخارجية على \(q\) وتفحص العائلات الأربع المسموح بها، ولا تضيف فرعا إلا إذا كانت قيمة \(n\) المرتبطة به لا تتجاوز الحد المطلوب. التنفيذات الأصلية تقسّم مجال \(q\) إلى كتل، وتجعل كل عامل يحسب مجموعا محليا دقيقا، ثم تجمع المجاميع الجزئية في النهاية. ومدخل Python يفوض إلى النواة الحسابية المترجمة نفسها، ولذلك فهو ينتج العد نفسه لا خوارزمية مختلفة.
ليكن \(K=N+4\) و\(Q=\lfloor K/4 \rfloor\). مرحلة الغربال تكلف \(O(K)\) زمنا و\(O(K)\) ذاكرة. وهذا الاستهلاك للذاكرة هو الأكبر، لأن جدول أصغر عامل أولي يحمل قيمة واحدة لكل عدد صحيح حتى الحد.
أما مرحلة التجميع فتفحص حتى أربع قيم مرشحة لـ \(k\) لكل \(q\). وتكلفة عدٍّ واحد للأعداد المتباينة أوليا هي \(O(2^{\omega(k)})\)، حيث تمثل \(\omega(k)\) عدد العوامل الأولية المميزة للعدد \(k\). وعند الحد الهدف \(N=10^8\)، فإن أي \(k \le 100000004\) لا يملك أكثر من 8 عوامل أولية مميزة، ولذلك فإن كل مرور للاشتمال والاستبعاد يستخدم في أقصى الأحوال \(2^8=256\) حدا من حدود المجموعات الجزئية. وعمليا يجعل هذا المرحلة الحسابية قريبة جدا من الخطية في عدد الفروع المعالجة، بينما تحسّن التجزئة المتوازية زمن التنفيذ فقط من دون أن تغيّر العد الدقيق.