A partition of \(n\) is balanceable if its parts can be split into two groups with the same total. A partition is \(k\)-bounded if every part is at most \(k\). The problem asks for the least positive integer \(f(k)\) such that every \(k\)-bounded partition of \(f(k)\) is balanceable, and then asks for \(f(10^8)\bmod(10^9+7)\). The C++, Python, and Java implementations do not enumerate partitions at all; they rely on a structural theorem that turns the problem into one least-common-multiple computation.
Write
$$L_k=\operatorname{lcm}(1,2,\dots,k).$$
The key identity behind the implementations is
$$\boxed{f(k)=2L_k.}$$
Once this is proved, the remaining work is purely arithmetic.
Suppose a \(k\)-bounded partition of \(n\) is written as
$$n=\lambda_1+\lambda_2+\cdots+\lambda_m,\qquad 1\le \lambda_i\le k.$$
It is balanceable exactly when some submultiset of the parts has sum \(n/2\). Equivalently, there exists an index set \(I\subseteq\{1,\dots,m\}\) such that
$$\sum_{i\in I}\lambda_i=\frac{n}{2}.$$
So if we can show that every \(k\)-bounded partition of \(2L_k\) has a submultiset summing to \(L_k\), then \(f(k)\le 2L_k\). The opposite inequality comes from divisibility constraints.
Fix any \(j\) with \(1\le j\le k\). Consider the partition of \(n\) consisting only of parts of size \(j\):
$$n=\underbrace{j+j+\cdots+j}_{n/j\text{ terms}}.$$
If this partition is balanceable, the two sides must contain the same number of \(j\)'s, so \(n/j\) has to be even. Therefore
$$2j\mid n\qquad \text{for every }1\le j\le k.$$
This implies
$$2\operatorname{lcm}(1,2,\dots,k)=2L_k\mid n.$$
Hence no universal value can be smaller than \(2L_k\), so
$$f(k)\ge 2L_k.$$
Now take an arbitrary \(k\)-bounded partition of \(2L_k\):
$$2L_k=a_1+a_2+\cdots+a_r,\qquad 1\le a_i\le k.$$
Because every integer from \(1\) to \(k\) divides \(L_k\), each part \(a_i\) also divides \(L_k\). Regard each \(a_i\) as an element of the cyclic group \(\mathbb{Z}/L_k\mathbb{Z}\). The whole sequence has sum
$$a_1+\cdots+a_r\equiv 2L_k\equiv 0 \pmod{L_k},$$
so it is a zero-sum sequence in that group.
For a part \(a_i\), its order in \(\mathbb{Z}/L_k\mathbb{Z}\) is
$$\operatorname{ord}(a_i)=\frac{L_k}{a_i},$$
since \(a_i\mid L_k\).
Assume, for contradiction, that this partition is not balanceable. Then no proper nonempty submultiset of \(\{a_1,\dots,a_r\}\) sums to \(L_k\). In modular language that means the zero-sum sequence is minimal: no proper nonempty subsequence sums to \(0\) in \(\mathbb{Z}/L_k\mathbb{Z}\).
Define its cross number by
$$\kappa=\sum_{i=1}^{r}\frac{1}{\operatorname{ord}(a_i)}=\sum_{i=1}^{r}\frac{a_i}{L_k}=\frac{2L_k}{L_k}=2.$$
A standard theorem from zero-sum theory states that every minimal zero-sum sequence in a finite cyclic group satisfies
$$\kappa\le 1.$$
Our sequence has \(\kappa=2\), which is impossible. Therefore a proper nonempty zero-sum subsequence must exist. Its ordinary sum is a positive multiple of \(L_k\), but it is strictly smaller than the total sum \(2L_k\), so its sum can only be
$$L_k.$$
That is exactly the required balanced split. Thus every \(k\)-bounded partition of \(2L_k\) is balanceable, and therefore
$$f(k)\le 2L_k.$$
The lower and upper bounds match, so
$$f(k)=2L_k.$$
To compute \(L_k\), factor it prime by prime. For each prime \(p\le k\), the exponent is the largest integer \(e\) such that \(p^e\le k\):
$$e_p=\max\{e\in\mathbb{Z}_{\ge 0}:p^e\le k\}=\left\lfloor\log_p k\right\rfloor.$$
Therefore
$$L_k=\prod_{p\le k}p^{e_p},\qquad f(k)=2\prod_{p\le k}p^{e_p}.$$
This is the exact arithmetic form evaluated by the implementations.
For \(k=3\),
$$L_3=\operatorname{lcm}(1,2,3)=6,$$
so the formula predicts
$$f(3)=2L_3=12.$$
The lower bound already forces divisibility by \(2\), \(4\), and \(6\), hence by \(12\). For the upper bound, every \(3\)-bounded partition of \(12\) uses parts drawn from \(\{1,2,3\}\), all of which divide \(6\). For example,
$$12=3+3+2+2+1+1$$
is balanceable because
$$6=3+2+1=3+2+1.$$
The theorem above guarantees that the same must happen for every \(3\)-bounded partition of \(12\), which matches the small checkpoint \(f(3)=12\).
The C++, Python, and Java implementations never manipulate partitions directly. They first generate all primes up to \(k\) with an odd-only sieve: the prime \(2\) is handled explicitly, and only odd candidates are stored afterward. For each prime \(p\), the implementation repeatedly multiplies by \(p\) until the next multiplication would exceed \(k\); this produces the largest prime power \(p^{e_p}\le k\).
Those prime powers are multiplied into a running product modulo \(10^9+7\). After the product for \(L_k\) is complete, the implementation multiplies once more by \(2\) to obtain \(f(k)\bmod(10^9+7)\). In short, the code evaluates the closed form directly and avoids any exponential partition search.
Let the input be \(k\). Building the sieve up to \(k\) costs \(O(k\log\log k)\) time and \(O(k)\) memory. The second phase loops over the primes and climbs through the prime powers \(p,p^2,p^3,\dots\le k\), which costs
$$\sum_{p\le k} O(\log_p k),$$
a lower-order term compared with the sieve. Therefore the overall algorithm runs in \(O(k\log\log k)\) time and uses \(O(k)\) memory.
Eine Partition von \(n\) heißt ausbalancierbar, wenn sich ihre Teile in zwei Gruppen mit gleicher Summe zerlegen lassen. Eine Partition ist \(k\)-beschränkt, wenn jeder Teil höchstens \(k\) ist. Gesucht ist die kleinste positive Zahl \(f(k)\), so dass jede \(k\)-beschränkte Partition von \(f(k)\) ausbalancierbar ist; anschließend soll \(f(10^8)\bmod(10^9+7)\) berechnet werden. Die C++-, Python- und Java-Implementierungen zählen keine Partitionen direkt, sondern benutzen einen Struktursatz, der das Problem auf ein einziges kgV reduziert.
Schreibe
$$L_k=\operatorname{lcm}(1,2,\dots,k).$$
Die zentrale Identität lautet
$$\boxed{f(k)=2L_k.}$$
Ist diese Aussage bewiesen, bleibt nur noch eine arithmetische Auswertung.
Sei eine \(k\)-beschränkte Partition von \(n\) gegeben durch
$$n=\lambda_1+\lambda_2+\cdots+\lambda_m,\qquad 1\le \lambda_i\le k.$$
Sie ist genau dann ausbalancierbar, wenn eine Teilmenge der Teile die Summe \(n/2\) besitzt. Es muss also eine Indexmenge \(I\subseteq\{1,\dots,m\}\) geben mit
$$\sum_{i\in I}\lambda_i=\frac{n}{2}.$$
Wenn wir also zeigen, dass jede \(k\)-beschränkte Partition von \(2L_k\) eine Teilmenge mit Summe \(L_k\) enthält, folgt \(f(k)\le 2L_k\). Die Gegenrichtung kommt aus Divisibilitätsargumenten.
Fixiere ein \(j\) mit \(1\le j\le k\). Betrachte die Partition von \(n\), die nur aus Teilen der Größe \(j\) besteht:
$$n=\underbrace{j+j+\cdots+j}_{n/j\text{ Summanden}}.$$
Ist diese Partition ausbalancierbar, dann müssen beide Seiten gleich viele \(j\)'s enthalten. Also muss \(n/j\) gerade sein. Damit gilt
$$2j\mid n\qquad \text{für jedes }1\le j\le k.$$
Folglich ist
$$2\operatorname{lcm}(1,2,\dots,k)=2L_k\mid n.$$
Daher kann kein universeller Wert kleiner als \(2L_k\) sein, also
$$f(k)\ge 2L_k.$$
Nimm nun eine beliebige \(k\)-beschränkte Partition von \(2L_k\):
$$2L_k=a_1+a_2+\cdots+a_r,\qquad 1\le a_i\le k.$$
Da jede Zahl zwischen \(1\) und \(k\) ein Teiler von \(L_k\) ist, teilt auch jeder Teil \(a_i\) die Zahl \(L_k\). Wir betrachten daher jedes \(a_i\) als Element der zyklischen Gruppe \(\mathbb{Z}/L_k\mathbb{Z}\). Die gesamte Folge hat Summe
$$a_1+\cdots+a_r\equiv 2L_k\equiv 0 \pmod{L_k},$$
also ist sie eine Nullsummenfolge.
Die Ordnung eines Teils \(a_i\) in \(\mathbb{Z}/L_k\mathbb{Z}\) ist
$$\operatorname{ord}(a_i)=\frac{L_k}{a_i},$$
weil \(a_i\mid L_k\) gilt.
Nehmen wir zum Widerspruch an, die Partition sei nicht ausbalancierbar. Dann gibt es keine echte nichtleere Teilmultimenge mit Summe \(L_k\). In der Sprache der Gruppe bedeutet das: Die Nullsummenfolge ist minimal, also hat keine echte nichtleere Teilfolge Summe \(0\) in \(\mathbb{Z}/L_k\mathbb{Z}\).
Definiere ihre Cross Number durch
$$\kappa=\sum_{i=1}^{r}\frac{1}{\operatorname{ord}(a_i)}=\sum_{i=1}^{r}\frac{a_i}{L_k}=\frac{2L_k}{L_k}=2.$$
Ein Standardresultat der Zero-Sum-Theorie besagt, dass für minimale Nullsummenfolgen in endlichen zyklischen Gruppen stets
$$\kappa\le 1$$
gilt. Unsere Folge hat aber \(\kappa=2\), was unmöglich ist. Also muss eine echte nichtleere Nullsummen-Teilfolge existieren. Ihre gewöhnliche Summe ist ein positives Vielfaches von \(L_k\), aber echt kleiner als \(2L_k\); deshalb kann sie nur
$$L_k$$
sein. Genau das ist die gesuchte ausbalancierte Zerlegung. Also gilt für jede \(k\)-beschränkte Partition von \(2L_k\): sie ist ausbalancierbar, also
$$f(k)\le 2L_k.$$
Die obere und die untere Schranke stimmen überein, also
$$f(k)=2L_k.$$
Zur Berechnung von \(L_k\) zerlegt man es nach Primzahlen. Für jede Primzahl \(p\le k\) ist der Exponent die größte ganze Zahl \(e\) mit \(p^e\le k\):
$$e_p=\max\{e\in\mathbb{Z}_{\ge 0}:p^e\le k\}=\left\lfloor\log_p k\right\rfloor.$$
Daher folgt
$$L_k=\prod_{p\le k}p^{e_p},\qquad f(k)=2\prod_{p\le k}p^{e_p}.$$
Genau diese geschlossene Form wird von den Implementierungen ausgewertet.
Für \(k=3\) gilt
$$L_3=\operatorname{lcm}(1,2,3)=6,$$
also sagt die Formel voraus:
$$f(3)=2L_3=12.$$
Die untere Schranke erzwingt bereits Teilbarkeit durch \(2\), \(4\) und \(6\), also durch \(12\). Für die obere Schranke besteht jede \(3\)-beschränkte Partition von \(12\) nur aus Teilen aus \(\{1,2,3\}\), die alle \(6\) teilen. Zum Beispiel ist
$$12=3+3+2+2+1+1$$
ausbalancierbar, denn
$$6=3+2+1=3+2+1.$$
Der Satz oben garantiert, dass dies für jede \(3\)-beschränkte Partition von \(12\) gilt. Das passt genau zum kleinen Kontrollwert \(f(3)=12\).
Die C++-, Python- und Java-Implementierungen erzeugen niemals Partitionen explizit. Zuerst werden alle Primzahlen bis \(k\) mit einem ungeraden Sieb erzeugt: Die Primzahl \(2\) wird separat behandelt, danach werden nur noch ungerade Kandidaten gespeichert. Für jede Primzahl \(p\) wird wiederholt mit \(p\) multipliziert, bis die nächste Multiplikation größer als \(k\) wäre; dadurch erhält man die größte Primzahlpotenz \(p^{e_p}\le k\).
Diese Primzahlpotenzen werden modulo \(10^9+7\) in ein laufendes Produkt multipliziert. Ist das Produkt für \(L_k\) fertig, wird noch einmal mit \(2\) multipliziert, um \(f(k)\bmod(10^9+7)\) zu erhalten. Der Code wertet also die geschlossene Formel direkt aus und vermeidet jede exponentielle Partitionssuche.
Mit Eingabe \(k\) kostet das Sieb bis \(k\) insgesamt \(O(k\log\log k)\) Zeit und \(O(k)\) Speicher. In der zweiten Phase werden für jede Primzahl die Potenzen \(p,p^2,p^3,\dots\le k\) durchlaufen; das kostet
$$\sum_{p\le k} O(\log_p k),$$
also einen kleineren Beitrag als das Sieb. Insgesamt benötigt das Verfahren daher \(O(k\log\log k)\) Zeit und \(O(k)\) Speicher.
Bir \(n\) bölünümü, parçaları toplamı eşit iki gruba ayrılabiliyorsa dengelenebilirdir. Bir bölünüm, tüm parçaları en fazla \(k\) ise \(k\)-sınırlıdır. Problem, her \(k\)-sınırlı \(f(k)\) bölünümünün dengelenebilir olmasını sağlayan en küçük pozitif \(f(k)\) değerini tanımlar ve ardından \(f(10^8)\bmod(10^9+7)\) ister. C++, Python ve Java uygulamaları bölünümleri tek tek saymaz; problemi tek bir EKOK hesabına indiren yapısal bir teorem kullanır.
Şunu yazalım:
$$L_k=\operatorname{lcm}(1,2,\dots,k).$$
Uygulamanın dayandığı ana özdeşlik şudur:
$$\boxed{f(k)=2L_k.}$$
Bu özdeşlik kanıtlandıktan sonra geriye yalnızca aritmetik hesap kalır.
\(n\)'in bir \(k\)-sınırlı bölünümü
$$n=\lambda_1+\lambda_2+\cdots+\lambda_m,\qquad 1\le \lambda_i\le k$$
olsun. Bu bölünüm, tam ve ancak parçaların bir alt çoklu kümesi \(n/2\) toplamını veriyorsa dengelenebilirdir. Yani bir \(I\subseteq\{1,\dots,m\}\) kümesi için
$$\sum_{i\in I}\lambda_i=\frac{n}{2}$$
olmalıdır. Demek ki her \(2L_k\) toplamlı \(k\)-sınırlı bölünümün \(L_k\) toplamlı bir alt kümesi olduğunu gösterebilirsek \(f(k)\le 2L_k\) elde ederiz. Ters yöndeki eşitsizlik ise bölünebilme koşullarından gelir.
\(1\le j\le k\) için sabit bir \(j\) seçelim. Sadece \(j\) parçalarından oluşan bölünümü düşünelim:
$$n=\underbrace{j+j+\cdots+j}_{n/j\text{ adet}}.$$
Bu bölünüm dengelenebiliyorsa iki tarafta aynı sayıda \(j\) bulunmalıdır; dolayısıyla \(n/j\) çift olmalıdır. Yani
$$2j\mid n\qquad \text{her }1\le j\le k\text{ için}.$$
Bundan
$$2\operatorname{lcm}(1,2,\dots,k)=2L_k\mid n$$
çıkar. O halde evrensel çözüm bundan küçük olamaz ve
$$f(k)\ge 2L_k$$
elde edilir.
Şimdi \(2L_k\)'nin rastgele bir \(k\)-sınırlı bölünümünü alalım:
$$2L_k=a_1+a_2+\cdots+a_r,\qquad 1\le a_i\le k.$$
\(1\) ile \(k\) arasındaki her tam sayı \(L_k\)'yi böldüğü için her parça \(a_i\) de \(L_k\)'nin bölenidir. Bu nedenle her \(a_i\)'yi çevrimsel grup \(\mathbb{Z}/L_k\mathbb{Z}\) içinde bir eleman olarak görebiliriz. Tüm dizinin toplamı
$$a_1+\cdots+a_r\equiv 2L_k\equiv 0 \pmod{L_k}$$
olduğundan elimizde bir sıfır-toplam dizi vardır.
Bir \(a_i\) parçasının \(\mathbb{Z}/L_k\mathbb{Z}\) içindeki mertebesi
$$\operatorname{ord}(a_i)=\frac{L_k}{a_i}$$
olur; çünkü \(a_i\mid L_k\).
Çelişki için bu bölünümün dengelenemediğini varsayalım. O zaman \(L_k\) toplamlı uygun boş olmayan gerçek bir alt çoklu küme yoktur. Modüler dilde bu, sıfır-toplam dizisinin minimal olduğu anlamına gelir: gerçek ve boş olmayan hiçbir alt dizi \(\mathbb{Z}/L_k\mathbb{Z}\) içinde \(0\) toplamını vermez.
Bu dizinin cross number değeri
$$\kappa=\sum_{i=1}^{r}\frac{1}{\operatorname{ord}(a_i)}=\sum_{i=1}^{r}\frac{a_i}{L_k}=\frac{2L_k}{L_k}=2$$
şeklindedir. Sıfır-toplam teorisindeki standart bir sonuç, sonlu çevrimsel gruplarda minimal sıfır-toplam diziler için her zaman
$$\kappa\le 1$$
olduğunu söyler. Bizde \(\kappa=2\) çıktığı için bu imkansızdır. Demek ki gerçek ve boş olmayan bir sıfır-toplam alt dizi vardır. Bunun normal toplamı \(L_k\)'nin pozitif bir katıdır ama toplam \(2L_k\)'den küçüktür; o halde tek olasılık
$$L_k$$
olmasıdır. Bu da tam olarak istenen dengeli ayrımdır. Böylece her \(2L_k\) toplamlı \(k\)-sınırlı bölünüm dengelenebilir ve
$$f(k)\le 2L_k$$
sonucuna varırız.
Alt ve üst sınırlar eşit olduğundan
$$f(k)=2L_k$$
olur. \(L_k\)'yi hesaplamak için asal bazda ilerleriz. \(p\le k\) asal ise üs, \(p^e\le k\) koşulunu sağlayan en büyük \(e\) değeridir:
$$e_p=\max\{e\in\mathbb{Z}_{\ge 0}:p^e\le k\}=\left\lfloor\log_p k\right\rfloor.$$
Dolayısıyla
$$L_k=\prod_{p\le k}p^{e_p},\qquad f(k)=2\prod_{p\le k}p^{e_p}.$$
Üç dildeki uygulama da tam olarak bu kapalı formu hesaplar.
\(k=3\) için
$$L_3=\operatorname{lcm}(1,2,3)=6$$
olur; dolayısıyla formül
$$f(3)=2L_3=12$$
der. Alt sınır zaten \(2\), \(4\) ve \(6\)'ya bölünebilirliği zorlar; EKOK bunların \(12\) olduğunu söyler. Üst sınır tarafında ise \(12\)'nin her \(3\)-sınırlı bölünümü yalnızca \(\{1,2,3\}\) parçalarını kullanır ve bunların hepsi \(6\)'yı böler. Örneğin
$$12=3+3+2+2+1+1$$
bölünümü dengelenebilir, çünkü
$$6=3+2+1=3+2+1.$$
Yukarıdaki teorem bunun \(12\)'nin her \(3\)-sınırlı bölünümü için geçerli olduğunu söyler. Bu da küçük kontrol değeri \(f(3)=12\) ile uyumludur.
C++, Python ve Java uygulamaları bölünümleri açıkça üretmez. Önce tek-sayı odaklı bir elek ile \(k\)'ya kadar tüm asallar bulunur: \(2\) doğrudan eklenir, sonrasında yalnızca tek adaylar tutulur. Her asal \(p\) için, bir sonraki çarpım \(k\)'yı aşana kadar \(p\) ile tekrar tekrar çarpılır; böylece \(p^{e_p}\le k\) olan en büyük asal kuvvet elde edilir.
Bu asal kuvvetler \(10^9+7\) modunda yürüyen çarpıma eklenir. \(L_k\) için ürün tamamlanınca bir kez daha \(2\) ile çarpılır ve \(f(k)\bmod(10^9+7)\) bulunur. Yani kod, kapalı formu doğrudan değerlendirir ve üstel büyüklükte bir bölünüm araması yapmaz.
Girdi \(k\) olsun. \(k\)'ya kadar elek kurmak \(O(k\log\log k)\) zaman ve \(O(k)\) bellek gerektirir. İkinci aşamada her asal için \(p,p^2,p^3,\dots\le k\) kuvvetleri dolaşılır; bunun maliyeti
$$\sum_{p\le k} O(\log_p k)$$
olup eleğe göre daha düşük mertebededir. Bu yüzden toplam karmaşıklık \(O(k\log\log k)\) zaman ve \(O(k)\) bellektir.
Una partición de \(n\) es equilibrable si sus partes pueden separarse en dos grupos con la misma suma. Una partición es \(k\)-acotada si todas sus partes son a lo sumo \(k\). El problema pide el menor entero positivo \(f(k)\) tal que toda partición \(k\)-acotada de \(f(k)\) sea equilibrable, y luego solicita \(f(10^8)\bmod(10^9+7)\). Las implementaciones en C++, Python y Java no enumeran particiones; usan un teorema estructural que reduce todo a un único cálculo de mínimo común múltiplo.
Definimos
$$L_k=\operatorname{lcm}(1,2,\dots,k).$$
La identidad clave es
$$\boxed{f(k)=2L_k.}$$
Una vez demostrada, el resto del problema es puramente aritmético.
Sea una partición \(k\)-acotada de \(n\):
$$n=\lambda_1+\lambda_2+\cdots+\lambda_m,\qquad 1\le \lambda_i\le k.$$
Es equilibrable exactamente cuando algún submulticonjunto de sus partes suma \(n/2\). Es decir, debe existir un conjunto de índices \(I\subseteq\{1,\dots,m\}\) tal que
$$\sum_{i\in I}\lambda_i=\frac{n}{2}.$$
Por tanto, si demostramos que toda partición \(k\)-acotada de \(2L_k\) contiene un submulticonjunto que suma \(L_k\), entonces obtendremos \(f(k)\le 2L_k\). La desigualdad opuesta vendrá de condiciones de divisibilidad.
Fijemos \(j\) con \(1\le j\le k\). Consideremos la partición de \(n\) formada solo por partes de tamaño \(j\):
$$n=\underbrace{j+j+\cdots+j}_{n/j\text{ términos}}.$$
Si esta partición es equilibrable, ambos lados deben contener la misma cantidad de \(j\)'s, así que \(n/j\) tiene que ser par. Por lo tanto,
$$2j\mid n\qquad \text{para todo }1\le j\le k.$$
Eso implica
$$2\operatorname{lcm}(1,2,\dots,k)=2L_k\mid n.$$
En consecuencia, ningún valor universal puede ser menor que \(2L_k\), y obtenemos
$$f(k)\ge 2L_k.$$
Tomemos ahora una partición \(k\)-acotada cualquiera de \(2L_k\):
$$2L_k=a_1+a_2+\cdots+a_r,\qquad 1\le a_i\le k.$$
Como cada entero entre \(1\) y \(k\) divide a \(L_k\), cada parte \(a_i\) también divide a \(L_k\). Entonces podemos ver cada \(a_i\) como un elemento del grupo cíclico \(\mathbb{Z}/L_k\mathbb{Z}\). La suma total es
$$a_1+\cdots+a_r\equiv 2L_k\equiv 0 \pmod{L_k},$$
de modo que obtenemos una secuencia de suma cero.
El orden de una parte \(a_i\) en \(\mathbb{Z}/L_k\mathbb{Z}\) es
$$\operatorname{ord}(a_i)=\frac{L_k}{a_i},$$
ya que \(a_i\mid L_k\).
Supongamos, para llegar a una contradicción, que la partición no es equilibrable. Entonces no existe ningún submulticonjunto propio y no vacío con suma \(L_k\). En lenguaje modular, eso significa que la secuencia de suma cero es mínima: ninguna subsecuencia propia y no vacía suma \(0\) en \(\mathbb{Z}/L_k\mathbb{Z}\).
Definimos su cross number por
$$\kappa=\sum_{i=1}^{r}\frac{1}{\operatorname{ord}(a_i)}=\sum_{i=1}^{r}\frac{a_i}{L_k}=\frac{2L_k}{L_k}=2.$$
Un resultado estándar de la teoría de secuencias de suma cero afirma que toda secuencia mínima de suma cero en un grupo cíclico finito satisface
$$\kappa\le 1.$$
Aquí obtenemos \(\kappa=2\), lo cual es imposible. Luego debe existir una subsecuencia propia y no vacía de suma cero. Su suma ordinaria es un múltiplo positivo de \(L_k\), pero además es estrictamente menor que \(2L_k\), así que solo puede ser
$$L_k.$$
Eso es exactamente la división equilibrada que buscábamos. Por tanto, toda partición \(k\)-acotada de \(2L_k\) es equilibrable y se concluye que
$$f(k)\le 2L_k.$$
Las dos cotas coinciden, así que
$$f(k)=2L_k.$$
Para calcular \(L_k\), lo descomponemos primo por primo. Si \(p\le k\) es primo, su exponente es el mayor entero \(e\) tal que \(p^e\le k\):
$$e_p=\max\{e\in\mathbb{Z}_{\ge 0}:p^e\le k\}=\left\lfloor\log_p k\right\rfloor.$$
En consecuencia,
$$L_k=\prod_{p\le k}p^{e_p},\qquad f(k)=2\prod_{p\le k}p^{e_p}.$$
Esa es exactamente la forma cerrada que evalúan las implementaciones.
Cuando \(k=3\),
$$L_3=\operatorname{lcm}(1,2,3)=6,$$
así que la fórmula predice
$$f(3)=2L_3=12.$$
La cota inferior ya obliga divisibilidad por \(2\), \(4\) y \(6\), luego por \(12\). Para la cota superior, toda partición \(3\)-acotada de \(12\) usa solamente partes en \(\{1,2,3\}\), y todas dividen a \(6\). Por ejemplo,
$$12=3+3+2+2+1+1$$
es equilibrable porque
$$6=3+2+1=3+2+1.$$
El teorema anterior garantiza que lo mismo ocurre con toda partición \(3\)-acotada de \(12\). Eso coincide con el pequeño valor de control \(f(3)=12\).
Las implementaciones en C++, Python y Java nunca construyen particiones de manera explícita. Primero generan todos los primos hasta \(k\) con una criba que solo almacena candidatos impares: el primo \(2\) se trata por separado, y luego solo se marcan compuestos impares. Para cada primo \(p\), la implementación multiplica repetidamente por \(p\) hasta que la siguiente multiplicación superaría a \(k\); así obtiene la mayor potencia prima \(p^{e_p}\le k\).
Esas potencias primas se multiplican en un producto acumulado módulo \(10^9+7\). Cuando el producto correspondiente a \(L_k\) está listo, la implementación multiplica una vez más por \(2\) para obtener \(f(k)\bmod(10^9+7)\). En otras palabras, el código evalúa directamente la forma cerrada y evita por completo cualquier búsqueda exponencial sobre particiones.
Si la entrada es \(k\), construir la criba hasta \(k\) cuesta \(O(k\log\log k)\) tiempo y \(O(k)\) memoria. La segunda fase recorre, para cada primo, las potencias \(p,p^2,p^3,\dots\le k\), con costo
$$\sum_{p\le k} O(\log_p k),$$
que es de orden inferior al de la criba. Por lo tanto, el algoritmo completo ejecuta en \(O(k\log\log k)\) tiempo y usa \(O(k)\) memoria.
如果一个 \(n\) 的分拆可以把所有部件分成两个和相同的组，我们就称它是可平衡的。如果一个分拆中的每个部件都不超过 \(k\)，就称它是 \(k\)-有界分拆。题目要求找到最小的正整数 \(f(k)\)，使得 \(f(k)\) 的每一个 \(k\)-有界分拆都可平衡，然后计算 \(f(10^8)\bmod(10^9+7)\)。C++、Python 和 Java 实现都不会直接枚举分拆；它们依赖一个结构性结论，把整个问题化成一次最小公倍数计算。
记
$$L_k=\operatorname{lcm}(1,2,\dots,k).$$
实现真正利用的核心恒等式是
$$\boxed{f(k)=2L_k.}$$
只要这个结论成立，后面的任务就只剩下算术展开和取模乘法。
设 \(n\) 的一个 \(k\)-有界分拆写成
$$n=\lambda_1+\lambda_2+\cdots+\lambda_m,\qquad 1\le \lambda_i\le k.$$
这个分拆可平衡，当且仅当某个部件子多重集的和恰好等于 \(n/2\)。也就是说，必须存在一个指标集合 \(I\subseteq\{1,\dots,m\}\)，满足
$$\sum_{i\in I}\lambda_i=\frac{n}{2}.$$
因此，如果我们能证明每个总和为 \(2L_k\) 的 \(k\)-有界分拆都存在一个子多重集，其和为 \(L_k\)，那么就得到 \(f(k)\le 2L_k\)。反过来的不等式来自整除性限制。
固定 \(1\le j\le k\)。考虑只由大小为 \(j\) 的部件组成的分拆：
$$n=\underbrace{j+j+\cdots+j}_{n/j\text{ 项}}.$$
如果这个分拆可平衡，那么左右两边必须含有相同数量的 \(j\)，所以 \(n/j\) 必须是偶数。这说明
$$2j\mid n\qquad \text{对所有 }1\le j\le k\text{ 都成立}.$$
于是
$$2\operatorname{lcm}(1,2,\dots,k)=2L_k\mid n.$$
因此，任何“对所有 \(k\)-有界分拆都有效”的统一值都不可能小于 \(2L_k\)，于是
$$f(k)\ge 2L_k.$$
现在取任意一个 \(2L_k\) 的 \(k\)-有界分拆：
$$2L_k=a_1+a_2+\cdots+a_r,\qquad 1\le a_i\le k.$$
由于 \(1\) 到 \(k\) 的每个整数都整除 \(L_k\)，所以每个部件 \(a_i\) 也都整除 \(L_k\)。于是我们可以把每个 \(a_i\) 看成循环群 \(\mathbb{Z}/L_k\mathbb{Z}\) 中的一个元素。整组元素的和满足
$$a_1+\cdots+a_r\equiv 2L_k\equiv 0 \pmod{L_k},$$
所以这是一条零和序列。
对于某个部件 \(a_i\)，它在 \(\mathbb{Z}/L_k\mathbb{Z}\) 中的阶为
$$\operatorname{ord}(a_i)=\frac{L_k}{a_i},$$
因为 \(a_i\mid L_k\)。
反设这个分拆不可平衡。那就意味着不存在真且非空的子多重集，其和等于 \(L_k\)。换成模 \(L_k\) 的语言，就是说这条零和序列是最小的：没有任何真且非空的子序列在 \(\mathbb{Z}/L_k\mathbb{Z}\) 中的和为 \(0\)。
定义它的 cross number 为
$$\kappa=\sum_{i=1}^{r}\frac{1}{\operatorname{ord}(a_i)}=\sum_{i=1}^{r}\frac{a_i}{L_k}=\frac{2L_k}{L_k}=2.$$
零和理论中的一个标准结论指出：在有限循环群里，任何最小零和序列都满足
$$\kappa\le 1.$$
而这里得到的是 \(\kappa=2\)，矛盾。因此，必然存在一个真且非空的零和子序列。它的普通整数和是 \(L_k\) 的正倍数，但又严格小于总和 \(2L_k\)，所以只能等于
$$L_k.$$
这正是把原分拆分成两个和都为 \(L_k\) 的方式。于是每个 \(2L_k\) 的 \(k\)-有界分拆都可平衡，从而得到
$$f(k)\le 2L_k.$$
上下界一致，所以
$$f(k)=2L_k.$$
接下来要计算 \(L_k\)。对每个素数 \(p\le k\)，它在 \(L_k\) 中的指数就是满足 \(p^e\le k\) 的最大整数 \(e\)：
$$e_p=\max\{e\in\mathbb{Z}_{\ge 0}:p^e\le k\}=\left\lfloor\log_p k\right\rfloor.$$
因此
$$L_k=\prod_{p\le k}p^{e_p},\qquad f(k)=2\prod_{p\le k}p^{e_p}.$$
这就是三个实现真正计算的闭式表达式。
当 \(k=3\) 时，
$$L_3=\operatorname{lcm}(1,2,3)=6,$$
所以公式给出
$$f(3)=2L_3=12.$$
下界部分已经要求结果同时被 \(2\)、\(4\) 和 \(6\) 整除，因此至少要是 \(12\) 的倍数。上界部分说明，任何 \(12\) 的 \(3\)-有界分拆都只会用到 \(\{1,2,3\}\) 这三种部件，而它们都整除 \(6\)。例如
$$12=3+3+2+2+1+1$$
显然可平衡，因为
$$6=3+2+1=3+2+1.$$
上面的定理说明，这种现象不是偶然，而是对所有 \(12\) 的 \(3\)-有界分拆都成立。这也与小规模检验值 \(f(3)=12\) 一致。
C++、Python 和 Java 实现都不会显式构造分拆。它们先用“只存奇数候选”的筛法生成不超过 \(k\) 的全部素数：素数 \(2\) 单独处理，之后只标记奇数合数。对于每个素数 \(p\)，实现会不断乘以 \(p\)，直到下一次乘法会超过 \(k\) 为止；这样就得到最大的素数幂 \(p^{e_p}\le k\)。
接着，把这些素数幂在模 \(10^9+7\) 下乘入一个累计乘积，得到 \(L_k\) 的模值。最后再额外乘以 \(2\)，就得到 \(f(k)\bmod(10^9+7)\)。换句话说，代码直接计算闭式，而完全避开了指数级的分拆枚举。
把输入记为 \(k\)。建立到 \(k\) 的筛需要 \(O(k\log\log k)\) 时间和 \(O(k)\) 空间。第二阶段会对每个素数遍历 \(p,p^2,p^3,\dots\le k\) 这些幂次，其代价为
$$\sum_{p\le k} O(\log_p k),$$
这是比筛法更低阶的项。因此总复杂度是 \(O(k\log\log k)\) 时间和 \(O(k)\) 空间。
Разбиение числа \(n\) называется балансируемым, если его части можно разделить на две группы с одинаковой суммой. Разбиение называется \(k\)-ограниченным, если каждая часть не превосходит \(k\). Требуется найти наименьшее положительное число \(f(k)\), такое что любое \(k\)-ограниченное разбиение числа \(f(k)\) балансируемо, а затем вычислить \(f(10^8)\bmod(10^9+7)\). Реализации на C++, Python и Java не перебирают разбиения напрямую; они используют структурную теорему, сводящую задачу к одному вычислению НОК.
Обозначим
$$L_k=\operatorname{lcm}(1,2,\dots,k).$$
Ключевая формула такова:
$$\boxed{f(k)=2L_k.}$$
После доказательства этой формулы остается только эффективное арифметическое вычисление.
Пусть \(k\)-ограниченное разбиение числа \(n\) имеет вид
$$n=\lambda_1+\lambda_2+\cdots+\lambda_m,\qquad 1\le \lambda_i\le k.$$
Оно балансируемо тогда и только тогда, когда некоторый подмультимножество частей имеет сумму \(n/2\). То есть существует множество индексов \(I\subseteq\{1,\dots,m\}\), для которого
$$\sum_{i\in I}\lambda_i=\frac{n}{2}.$$
Следовательно, если доказать, что в любом \(k\)-ограниченном разбиении числа \(2L_k\) есть подмультимножество с суммой \(L_k\), то получится \(f(k)\le 2L_k\). Обратное неравенство даст делимость.
Зафиксируем \(j\) при \(1\le j\le k\). Рассмотрим разбиение числа \(n\), состоящее только из частей размера \(j\):
$$n=\underbrace{j+j+\cdots+j}_{n/j\text{ слагаемых}}.$$
Если такое разбиение балансируемо, то в обеих половинах должно быть одинаковое число частей \(j\), значит \(n/j\) обязано быть четным. Поэтому
$$2j\mid n\qquad \text{для всех }1\le j\le k.$$
Отсюда следует
$$2\operatorname{lcm}(1,2,\dots,k)=2L_k\mid n.$$
Значит, универсальное значение не может быть меньше \(2L_k\), и мы получаем
$$f(k)\ge 2L_k.$$
Теперь возьмем произвольное \(k\)-ограниченное разбиение числа \(2L_k\):
$$2L_k=a_1+a_2+\cdots+a_r,\qquad 1\le a_i\le k.$$
Поскольку каждое число от \(1\) до \(k\) делит \(L_k\), каждая часть \(a_i\) тоже делит \(L_k\). Поэтому можно рассматривать каждое \(a_i\) как элемент циклической группы \(\mathbb{Z}/L_k\mathbb{Z}\). Сумма всей последовательности равна
$$a_1+\cdots+a_r\equiv 2L_k\equiv 0 \pmod{L_k},$$
то есть это нуль-суммовая последовательность.
Порядок элемента \(a_i\) в \(\mathbb{Z}/L_k\mathbb{Z}\) равен
$$\operatorname{ord}(a_i)=\frac{L_k}{a_i},$$
так как \(a_i\mid L_k\).
Предположим противное: данное разбиение не балансируемо. Тогда не существует собственного непустого подмультимножества частей с суммой \(L_k\). На языке группы это означает, что нуль-суммовая последовательность минимальна: никакая собственная непустая подпоследовательность не имеет сумму \(0\) в \(\mathbb{Z}/L_k\mathbb{Z}\).
Определим ее cross number:
$$\kappa=\sum_{i=1}^{r}\frac{1}{\operatorname{ord}(a_i)}=\sum_{i=1}^{r}\frac{a_i}{L_k}=\frac{2L_k}{L_k}=2.$$
Стандартный результат теории нуль-суммовых последовательностей утверждает, что для минимальной нуль-суммовой последовательности в конечной циклической группе всегда выполнено
$$\kappa\le 1.$$
У нас \(\kappa=2\), что невозможно. Следовательно, существует собственная непустая нуль-суммовая подпоследовательность. Ее обычная сумма является положительным кратным \(L_k\), но строго меньше полной суммы \(2L_k\), значит она может быть только
$$L_k.$$
Это и есть требуемое разбиение на две равные по сумме части. Значит, любое \(k\)-ограниченное разбиение числа \(2L_k\) балансируемо, и потому
$$f(k)\le 2L_k.$$
Нижняя и верхняя оценки совпадают, поэтому
$$f(k)=2L_k.$$
Чтобы вычислить \(L_k\), раскладываем его по простым. Для каждого простого \(p\le k\) показатель равен наибольшему целому \(e\), для которого \(p^e\le k\):
$$e_p=\max\{e\in\mathbb{Z}_{\ge 0}:p^e\le k\}=\left\lfloor\log_p k\right\rfloor.$$
Следовательно,
$$L_k=\prod_{p\le k}p^{e_p},\qquad f(k)=2\prod_{p\le k}p^{e_p}.$$
Именно эту замкнутую формулу вычисляют все три реализации.
При \(k=3\)
$$L_3=\operatorname{lcm}(1,2,3)=6,$$
поэтому формула дает
$$f(3)=2L_3=12.$$
Нижняя граница уже требует делимости на \(2\), \(4\) и \(6\), то есть на \(12\). Для верхней границы заметим, что любое \(3\)-ограниченное разбиение числа \(12\) использует только части из \(\{1,2,3\}\), и каждая из них делит \(6\). Например,
$$12=3+3+2+2+1+1$$
балансируемо, потому что
$$6=3+2+1=3+2+1.$$
Приведенная выше теорема гарантирует, что это верно для любого \(3\)-ограниченного разбиения числа \(12\). Это согласуется с малой контрольной точкой \(f(3)=12\).
Реализации на C++, Python и Java не строят разбиения явно. Сначала они генерируют все простые числа до \(k\) при помощи решета, хранящего только нечетные кандидаты: число \(2\) обрабатывается отдельно, а дальше отмечаются лишь нечетные составные. Для каждого простого \(p\) программа многократно умножает на \(p\), пока следующее умножение не превысит \(k\); так получается наибольшая простая степень \(p^{e_p}\le k\).
Затем эти простые степени перемножаются по модулю \(10^9+7\), образуя значение \(L_k\) по модулю. После этого результат еще раз умножается на \(2\), чтобы получить \(f(k)\bmod(10^9+7)\). Иными словами, код напрямую вычисляет замкнутую формулу и полностью избегает экспоненциального перебора разбиений.
Если вход равен \(k\), построение решета до \(k\) требует \(O(k\log\log k)\) времени и \(O(k)\) памяти. На втором этапе для каждого простого перебираются степени \(p,p^2,p^3,\dots\le k\), что стоит
$$\sum_{p\le k} O(\log_p k),$$
и это меньше по порядку, чем цена самого решета. Следовательно, полный алгоритм работает за \(O(k\log\log k)\) времени и использует \(O(k)\) памяти.
يُقال إن تجزئة العدد \(n\) قابلة للموازنة إذا أمكن تقسيم أجزائها إلى مجموعتين لهما المجموع نفسه. وتكون التجزئة \(k\)-محدودة إذا كانت كل الأجزاء لا تتجاوز \(k\). المطلوب هو أصغر عدد صحيح موجب \(f(k)\) بحيث تكون كل تجزئة \(k\)-محدودة للعدد \(f(k)\) قابلة للموازنة، ثم حساب \(f(10^8)\bmod(10^9+7)\). لا تقوم تطبيقات C++ وPython وJava بعدّ التجزئات مباشرة، بل تعتمد على نتيجة بنيوية تختزل المسألة إلى حساب واحد للمضاعف المشترك الأصغر.
لنكتب
$$L_k=\operatorname{lcm}(1,2,\dots,k).$$
الهوية الأساسية التي تعتمد عليها التطبيقات هي
$$\boxed{f(k)=2L_k.}$$
وبعد إثبات هذه الهوية تصبح بقية المسألة حسابية بحتة.
إذا كُتبت تجزئة \(k\)-محدودة للعدد \(n\) على الصورة
$$n=\lambda_1+\lambda_2+\cdots+\lambda_m,\qquad 1\le \lambda_i\le k,$$
فإنها تكون قابلة للموازنة إذا وفقط إذا وُجد متعدد جزئي من الأجزاء مجموعه \(n/2\). أي يجب أن توجد مجموعة فهارس \(I\subseteq\{1,\dots,m\}\) تحقق
$$\sum_{i\in I}\lambda_i=\frac{n}{2}.$$
لذلك إذا برهنا أن كل تجزئة \(k\)-محدودة للعدد \(2L_k\) تحتوي على متعدد جزئي مجموعُه \(L_k\)، فإننا نحصل على \(f(k)\le 2L_k\). أما المتباينة العكسية فتأتي من شروط القابلية للقسمة.
لنثبت عددًا \(j\) حيث \(1\le j\le k\). انظر إلى التجزئة التي تتكون فقط من أجزاء قيمتها \(j\):
$$n=\underbrace{j+j+\cdots+j}_{n/j}.$$
وهذا يعني أن عدد الحدود يساوي \(n/j\). إذا كانت هذه التجزئة قابلة للموازنة، فلا بد أن يحتوي كل جانب على العدد نفسه من حدود \(j\)، ومن ثم يجب أن يكون \(n/j\) عددًا زوجيًا. إذن
$$2j\mid n\qquad (1\le j\le k).$$
ومن هنا نستنتج أن
$$2\operatorname{lcm}(1,2,\dots,k)=2L_k\mid n.$$
وعليه فلا يمكن أن يكون أي حد شامل أصغر من \(2L_k\)، وبالتالي
$$f(k)\ge 2L_k.$$
خذ الآن تجزئة \(k\)-محدودة اعتباطية للعدد \(2L_k\):
$$2L_k=a_1+a_2+\cdots+a_r,\qquad 1\le a_i\le k.$$
بما أن كل عدد من \(1\) إلى \(k\) يقسم \(L_k\)، فإن كل جزء \(a_i\) يقسم \(L_k\) أيضًا. لذلك يمكن النظر إلى كل \(a_i\) بوصفه عنصرًا في الزمرة الدورية \(\mathbb{Z}/L_k\mathbb{Z}\). مجموع السلسلة كلها يساوي
$$a_1+\cdots+a_r\equiv 2L_k\equiv 0 \pmod{L_k},$$
وهذا يعني أننا أمام سلسلة مجموعها صفر.
ورتبة الجزء \(a_i\) داخل \(\mathbb{Z}/L_k\mathbb{Z}\) هي
$$\operatorname{ord}(a_i)=\frac{L_k}{a_i},$$
لأن \(a_i\mid L_k\).
افترض على سبيل التناقض أن هذه التجزئة غير قابلة للموازنة. عندئذ لا يوجد متعدد جزئي حقيقي وغير فارغ مجموعه \(L_k\). وباللغة الزمرية يعني هذا أن سلسلة المجموع الصفري سلسلة دنيا: فلا توجد متتالية جزئية حقيقية وغير فارغة مجموعها \(0\) في \(\mathbb{Z}/L_k\mathbb{Z}\).
لنعرّف قيمة cross number لها بالصيغة
$$\kappa=\sum_{i=1}^{r}\frac{1}{\operatorname{ord}(a_i)}=\sum_{i=1}^{r}\frac{a_i}{L_k}=\frac{2L_k}{L_k}=2.$$
وتنص نتيجة قياسية من نظرية السلاسل ذات المجموع الصفري على أن كل سلسلة دنيا ذات مجموع صفري في زمرة دورية منتهية تحقق
$$\kappa\le 1.$$
لكننا هنا نحصل على \(\kappa=2\)، وهذا مستحيل. إذن لا بد من وجود متتالية جزئية حقيقية وغير فارغة مجموعها صفر. مجموعها العادي هو مضاعف موجب لـ \(L_k\)، لكنه أصغر من المجموع الكلي \(2L_k\)، ولذلك لا يمكن إلا أن يكون
$$L_k.$$
وهذا بالضبط هو التقسيم المتوازن المطلوب. وبالتالي فإن كل تجزئة \(k\)-محدودة للعدد \(2L_k\) قابلة للموازنة، ومن ثم
$$f(k)\le 2L_k.$$
بما أن الحدين الأدنى والأعلى متساويان، نحصل على
$$f(k)=2L_k.$$
ولحساب \(L_k\) نحلله حسب الأعداد الأولية. إذا كان \(p\le k\) عددًا أوليًا، فإن أسه هو أكبر عدد صحيح \(e\) يحقق \(p^e\le k\):
$$e_p=\max\{e\in\mathbb{Z}_{\ge 0}:p^e\le k\}=\left\lfloor\log_p k\right\rfloor.$$
إذن
$$L_k=\prod_{p\le k}p^{e_p},\qquad f(k)=2\prod_{p\le k}p^{e_p}.$$
وهذه هي الصيغة المغلقة نفسها التي تقيمها التطبيقات.
عندما \(k=3\)، يكون
$$L_3=\operatorname{lcm}(1,2,3)=6,$$
ولذلك تتنبأ الصيغة بأن
$$f(3)=2L_3=12.$$
الحد الأدنى يفرض أصلًا القابلية للقسمة على \(2\) و\(4\) و\(6\)، أي على \(12\). أما من جهة الحد الأعلى، فكل تجزئة \(3\)-محدودة للعدد \(12\) تستخدم فقط الأجزاء \(\{1,2,3\}\)، وكلها تقسم \(6\). مثلًا
$$12=3+3+2+2+1+1$$
تجزئة قابلة للموازنة لأن
$$6=3+2+1=3+2+1.$$
والنظرية السابقة تضمن أن هذا يحدث مع كل تجزئة \(3\)-محدودة للعدد \(12\)، وهو ما يطابق قيمة التحقق الصغيرة \(f(3)=12\).
لا تبني تطبيقات C++ وPython وJava التجزئات صراحة. أولًا تولد جميع الأعداد الأولية حتى \(k\) باستخدام غربال يخزن المرشحات الفردية فقط: يُعالج العدد \(2\) مباشرة، ثم تُخزن الأعداد الفردية وحدها. ولكل عدد أولي \(p\)، تضرب الشيفرة في \(p\) مرارًا حتى يصبح الضرب التالي أكبر من \(k\)؛ وهكذا تحصل على أكبر قوة أولية \(p^{e_p}\le k\).
بعد ذلك تُضرب هذه القوى الأولية في حاصل ضرب تراكمي modulo \(10^9+7\). وعندما يكتمل حاصل الضرب الموافق لـ \(L_k\)، تُجرى ضربة أخيرة في \(2\) للحصول على \(f(k)\bmod(10^9+7)\). باختصار، الشيفرة تقيّم الصيغة المغلقة مباشرة وتتجنب كليًا أي بحث أسي في فضاء التجزئات.
إذا كانت قيمة الإدخال هي \(k\)، فإن بناء الغربال حتى \(k\) يكلف \(O(k\log\log k)\) زمنًا و\(O(k)\) ذاكرة. وفي المرحلة الثانية تُفحص لكل عدد أولي القوى \(p,p^2,p^3,\dots\le k\)، وهذا يكلف
$$\sum_{p\le k} O(\log_p k),$$
وهو حد أقل رتبة من كلفة الغربال نفسها. لذلك فإن الخوارزمية الكاملة تعمل في \(O(k\log\log k)\) زمنًا وتستخدم \(O(k)\) ذاكرة.