We want the smallest positive integer \(n\) whose number of divisors is exactly \(2^K\), where \(K=500{,}500\), and we only need the final value modulo \(M=500{,}500{,}507\). The minimum itself is astronomically large, so the solution never tries to build \(n\) explicitly. Instead, it minimizes the prime-power decisions that define \(n\).
Write the prime factorization of \(n\) as
$$n=\prod_{i\ge 1} p_i^{a_i},\qquad p_1\lt p_2\lt p_3\lt \dots.$$
The divisor formula gives
$$d(n)=\prod_{i\ge 1}(a_i+1).$$
So the entire problem is controlled by how the factors \(a_i+1\) multiply to \(2^K\).
Because \(2^K\) has no odd prime factor, every factor \(a_i+1\) in the product must itself be a power of two. Hence there are integers \(b_i\ge 0\) such that
$$a_i+1=2^{b_i},\qquad a_i=2^{b_i}-1,$$
and the divisor requirement becomes
$$\sum_{i\ge 1} b_i=K.$$
So we may think of the problem as distributing \(K\) identical units among the primes. If prime \(p_i\) receives \(b_i\) units, its final exponent is \(2^{b_i}-1\).
Suppose a prime currently has exponent \(2^t-1\). Giving that same prime one more unit changes the exponent to
$$2^{t+1}-1=(2^t-1)+2^t,$$
so \(n\) is multiplied by
$$p^{2^t}.$$
Thus each prime contributes an increasing sequence of possible elementary multipliers:
$$p,\ p^2,\ p^4,\ p^8,\ \dots.$$
If we take the first \(r\) terms from that sequence, their product is
$$p^{1+2+4+\dots+2^{r-1}}=p^{2^r-1},$$
which matches the exponent pattern required by the divisor formula.
Combine all prime sequences into one infinite multiset
$$\mathcal{U}=\left\{p^{2^t}: p \text{ prime},\ t\ge 0\right\}.$$
Any valid solution corresponds to choosing exactly \(K\) elements from \(\mathcal{U}\), with one important restriction: within the sequence for each fixed prime, we must choose a prefix. The final integer \(n\) is exactly the product of the chosen elements.
Now note that every sequence \(p,p^2,p^4,\dots\) is strictly increasing. Therefore, if some term \(p^{2^t}\) is among the first \(K\) smallest elements of \(\mathcal{U}\), then all earlier terms in that same sequence are even smaller and must also be among the first \(K\) smallest. So the first \(K\) smallest elements automatically satisfy the prefix rule.
That means the minimum possible \(n\) is simply the product of the \(K\) smallest elements of \(\mathcal{U}\). Replacing any chosen multiplier by a larger available one can only increase the final product.
Every distinct prime used in \(n\) consumes at least one unit, so an optimal solution can involve at most \(K\) different primes. If a larger prime were used while a smaller prime remained unused, replacing the larger prime by the smaller one would keep the divisor count unchanged and strictly decrease \(n\).
Equivalently, if \(p_{K+1}\) is the \((K+1)\)-st prime, then its first possible multiplier is \(p_{K+1}\), but there are already \(K\) smaller initial multipliers
$$p_1,p_2,\dots,p_K.$$
So no term from primes beyond \(p_K\) can belong to the first \(K\) chosen multipliers.
Start with the first \(K\) primes in a min-heap, each represented by its current offer. Repeatedly remove the smallest current offer \(q\), multiply the running answer by \(q\), and insert the next offer from the same prime, namely \(q^2\). After exactly \(K\) extractions, we have multiplied together the \(K\) smallest admissible multipliers.
If the current offer is \(q=p^{2^t}\), then the next offer from that prime is indeed
$$p^{2^{t+1}}=q^2.$$
The implementations compare offers by \(\log q\) rather than by the enormous integer \(q\) itself, because
$$q_1\lt q_2 \iff \log q_1\lt \log q_2.$$
At the same time, they keep the same offer reduced modulo \(M\), so the final result can be accumulated mod \(M\) without ever materializing the full minimum.
For \(K=4\), we need exactly \(2^4=16\) divisors. The initial heap offers are \(2,3,5,7\).
Greedy selection proceeds as follows:
$$\begin{aligned} \text{pick }2 &\Rightarrow \text{product }=2,\ \text{next offer }=4,\\ \text{pick }3 &\Rightarrow \text{product }=6,\ \text{next offer }=9,\\ \text{pick }4 &\Rightarrow \text{product }=24,\ \text{next offer }=16,\\ \text{pick }5 &\Rightarrow \text{product }=120,\ \text{next offer }=25. \end{aligned}$$
So the chosen multipliers are \(2,3,4,5\), and hence
$$n=2\cdot 3\cdot 4\cdot 5=2^3\cdot 3\cdot 5=120.$$
Its divisor count is
$$d(120)=(3+1)(1+1)(1+1)=16=2^4,$$
which matches the small checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same structure. First they generate the first \(K\) primes using a sieve together with a standard upper-bound estimate for the \(K\)-th prime. If the first estimate is too small, the bound is enlarged and the sieve is repeated.
They then build a min-heap whose entries store two views of the same current offer \(q\): a logarithmic key \(\log q\) for ordering, and the reduced residue \(q\bmod M\) for modular arithmetic. Initially the heap contains one offer for each of the first \(K\) primes.
Each of the \(K\) iterations removes the smallest offer, multiplies the running answer by its residue modulo \(M\), squares that residue modulo \(M\), doubles the logarithmic key, and pushes the updated offer back into the heap. This exactly enumerates the \(K\) smallest admissible multipliers in order. The C++ implementation also includes tiny checkpoint tests on small divisor powers to validate the greedy construction.
Let \(P_K\) be the \(K\)-th prime. Generating the first \(K\) primes with an ordinary sieve up to \(P_K\) costs \(O(P_K\log\log P_K)\) time and \(O(P_K)\) memory. The heap contains \(K\) entries, and the \(K\) pop-push iterations cost \(O(K\log K)\) time and \(O(K)\) extra memory.
Since \(P_K=\Theta(K\log K)\), the total running time is roughly \(O(K\log K\log\log K)\), and the total memory usage is \(O(P_K+K)\). For the fixed value \(K=500{,}500\), this is comfortably practical.
Gesucht ist die kleinste positive ganze Zahl \(n\), deren Teileranzahl genau \(2^K\) beträgt, wobei \(K=500{,}500\) ist. Benötigt wird nur der Wert modulo \(M=500{,}500{,}507\). Die minimale Zahl selbst ist astronomisch groß, daher konstruiert die Lösung nicht \(n\) direkt, sondern minimiert die Primzahlpotenzen, aus denen \(n\) besteht.
Schreibe die Primfaktorzerlegung von \(n\) als
$$n=\prod_{i\ge 1} p_i^{a_i},\qquad p_1\lt p_2\lt p_3\lt \dots.$$
Für die Teilerfunktion gilt
$$d(n)=\prod_{i\ge 1}(a_i+1).$$
Damit wird die gesamte Aufgabe darauf reduziert, wie die Faktoren \(a_i+1\) zu \(2^K\) multipliziert werden.
Da \(2^K\) keinen ungeraden Primfaktor besitzt, muss jeder Faktor \(a_i+1\) selbst eine Zweierpotenz sein. Es gibt also ganze Zahlen \(b_i\ge 0\) mit
$$a_i+1=2^{b_i},\qquad a_i=2^{b_i}-1,$$
und die Bedingung an die Teilerzahl wird zu
$$\sum_{i\ge 1} b_i=K.$$
Man kann das Problem daher als Verteilung von \(K\) identischen Einheiten auf die Primzahlen ansehen. Erhält die Primzahl \(p_i\) genau \(b_i\) Einheiten, dann ist ihr endgültiger Exponent \(2^{b_i}-1\).
Angenommen, eine Primzahl hat momentan den Exponenten \(2^t-1\). Gibt man ihr eine weitere Einheit, so wird der Exponent zu
$$2^{t+1}-1=(2^t-1)+2^t,$$
also wird \(n\) mit
$$p^{2^t}$$
multipliziert. Zu jeder Primzahl gehört damit eine streng wachsende Folge möglicher elementarer Faktoren:
$$p,\ p^2,\ p^4,\ p^8,\ \dots.$$
Nimmt man die ersten \(r\) Glieder dieser Folge, so ist ihr Produkt
$$p^{1+2+4+\dots+2^{r-1}}=p^{2^r-1},$$
also genau die Exponentenform, die von der Teilerformel verlangt wird.
Fasse alle Primzahlfolgen zu einer unendlichen Multimenge zusammen:
$$\mathcal{U}=\left\{p^{2^t}: p \text{ prim},\ t\ge 0\right\}.$$
Jede zulässige Lösung entspricht der Auswahl von genau \(K\) Elementen aus \(\mathcal{U}\), mit einer wichtigen Zusatzregel: Für jede feste Primzahl muss die Auswahl ein Präfix ihrer Folge sein. Die gesuchte Zahl \(n\) ist dann genau das Produkt dieser ausgewählten Elemente.
Da jede Folge \(p,p^2,p^4,\dots\) streng wächst, gilt: Ist ein Glied \(p^{2^t}\) unter den \(K\) kleinsten Elementen von \(\mathcal{U}\), dann sind alle früheren Glieder derselben Folge noch kleiner und damit ebenfalls unter diesen \(K\) kleinsten Elementen. Die \(K\) kleinsten Elemente erfüllen die Präfix-Bedingung also automatisch.
Folglich ist das minimale \(n\) einfach das Produkt der \(K\) kleinsten Elemente von \(\mathcal{U}\). Ersetzt man einen gewählten Faktor durch einen größeren verfügbaren, wird das Gesamtprodukt nur größer.
Jede verschiedene Primzahl, die in \(n\) vorkommt, verbraucht mindestens eine Einheit. Daher kann eine optimale Lösung höchstens \(K\) verschiedene Primzahlen enthalten. Würde eine größere Primzahl benutzt, obwohl eine kleinere noch unbenutzt ist, könnte man die größere durch die kleinere ersetzen, die Teilerzahl unverändert lassen und \(n\) strikt verkleinern.
Äquivalent dazu: Ist \(p_{K+1}\) die \((K+1)\)-te Primzahl, dann ist ihr erster möglicher Faktor \(p_{K+1}\), aber es gibt bereits \(K\) kleinere Anfangsfaktoren
$$p_1,p_2,\dots,p_K.$$
Somit kann kein Term von Primzahlen jenseits von \(p_K\) zu den ersten \(K\) gewählten Faktoren gehören.
Man startet mit den ersten \(K\) Primzahlen in einem Min-Heap, wobei jeder Eintrag den momentan kleinsten noch nicht verwendeten Faktor dieser Primzahl repräsentiert. Danach entfernt man wiederholt den kleinsten aktuellen Faktor \(q\), multipliziert die laufende Antwort mit \(q\) und fügt den nächsten Faktor derselben Primzahl wieder ein, also \(q^2\). Nach genau \(K\) Entnahmen hat man die \(K\) kleinsten zulässigen Faktoren multipliziert.
Ist der aktuelle Faktor \(q=p^{2^t}\), dann ist der nächste Faktor derselben Primzahl tatsächlich
$$p^{2^{t+1}}=q^2.$$
Die Implementierungen vergleichen diese Faktoren nicht als riesige ganze Zahlen, sondern über \(\log q\), denn
$$q_1\lt q_2 \iff \log q_1\lt \log q_2.$$
Gleichzeitig wird derselbe Faktor modulo \(M\) gespeichert, sodass das Endergebnis mod \(M\) akkumuliert werden kann, ohne die gigantische Minimalzahl je vollständig zu erzeugen.
Für \(K=4\) benötigen wir genau \(2^4=16\) Teiler. Die anfänglichen Heap-Angebote sind \(2,3,5,7\).
Die greedy Auswahl läuft so:
$$\begin{aligned} \text{nimm }2 &\Rightarrow \text{Produkt }=2,\ \text{nächstes Angebot }=4,\\ \text{nimm }3 &\Rightarrow \text{Produkt }=6,\ \text{nächstes Angebot }=9,\\ \text{nimm }4 &\Rightarrow \text{Produkt }=24,\ \text{nächstes Angebot }=16,\\ \text{nimm }5 &\Rightarrow \text{Produkt }=120,\ \text{nächstes Angebot }=25. \end{aligned}$$
Die gewählten Faktoren sind also \(2,3,4,5\), damit
$$n=2\cdot 3\cdot 4\cdot 5=2^3\cdot 3\cdot 5=120.$$
Die Teileranzahl ist
$$d(120)=(3+1)(1+1)(1+1)=16=2^4,$$
also genau der kleine Kontrollwert, den die Implementierungen verwenden.
Die C++-, Python- und Java-Implementierungen folgen demselben Aufbau. Zuerst erzeugen sie mit einem Sieb die ersten \(K\) Primzahlen und verwenden dabei eine Standardabschätzung für eine Obergrenze der \(K\)-ten Primzahl. Reicht die erste Abschätzung nicht aus, wird die Grenze vergrößert und erneut gesiebt.
Anschließend wird ein Min-Heap aufgebaut, dessen Einträge zwei Sichten auf dasselbe aktuelle Angebot \(q\) enthalten: einen logarithmischen Schlüssel \(\log q\) für die Ordnung und den Rest \(q\bmod M\) für die modulare Arithmetik. Anfangs liegt für jede der ersten \(K\) Primzahlen genau ein Angebot im Heap.
In jeder der \(K\) Iterationen wird das kleinste Angebot entfernt, die laufende Antwort mit seinem Rest modulo \(M\) multipliziert, dieser Rest modulo \(M\) quadriert, der logarithmische Schlüssel verdoppelt und das aktualisierte Angebot wieder in den Heap gelegt. Genau so werden die \(K\) kleinsten zulässigen Faktoren der Reihe nach erzeugt. Die C++-Implementierung enthält zusätzlich kleine Kontrolltests für kleine Zweierpotenzen der Teileranzahl.
Sei \(P_K\) die \(K\)-te Primzahl. Das Erzeugen der ersten \(K\) Primzahlen mit einem gewöhnlichen Sieb bis \(P_K\) kostet \(O(P_K\log\log P_K)\) Zeit und \(O(P_K)\) Speicher. Der Heap enthält \(K\) Einträge, und die \(K\) Pop-Push-Operationen kosten \(O(K\log K)\) Zeit und \(O(K)\) zusätzlichen Speicher.
Da \(P_K=\Theta(K\log K)\) gilt, liegt die Gesamtlaufzeit näherungsweise bei \(O(K\log K\log\log K)\), und der Gesamtbedarf an Speicher ist \(O(P_K+K)\). Für den festen Wert \(K=500{,}500\) ist das problemlos praktikabel.
Aranan şey, bölen sayısı tam olarak \(2^K\) olan en küçük pozitif tamsayı \(n\)'dir; burada \(K=500{,}500\) ve bizden yalnızca sonucun \(M=500{,}500{,}507\) modundaki değeri istenir. Minimum sayı kendi başına astronomik büyüklüktedir. Bu yüzden çözüm \(n\)'yi doğrudan üretmez; \(n\)'yi belirleyen asal üs seçimlerini en küçük yapacak biçimde kurar.
\(n\)'nin asal çarpanlara ayrılışını
$$n=\prod_{i\ge 1} p_i^{a_i},\qquad p_1\lt p_2\lt p_3\lt \dots$$
şeklinde yazalım. Bölen fonksiyonu formülü
$$d(n)=\prod_{i\ge 1}(a_i+1)$$
olduğundan, tüm mesele \(a_i+1\) çarpanlarının \(2^K\)'yi nasıl oluşturduğunu anlamaktır.
\(2^K\) sayısında tek asal çarpan olmadığı için, çarpımdaki her \(a_i+1\) terimi de ikinin bir kuvveti olmak zorundadır. Dolayısıyla \(b_i\ge 0\) olacak şekilde
$$a_i+1=2^{b_i},\qquad a_i=2^{b_i}-1$$
yazabiliriz ve bölen koşulu
$$\sum_{i\ge 1} b_i=K$$
haline gelir. Yani problem, \(K\) adet özdeş birimi asallara dağıtma problemidir. Asal \(p_i\) tam \(b_i\) birim alırsa son üssü \(2^{b_i}-1\) olur.
Bir asalın mevcut üssü \(2^t-1\) olsun. Aynı asala bir birim daha verirsek üs
$$2^{t+1}-1=(2^t-1)+2^t$$
olur; yani \(n\),
$$p^{2^t}$$
ile çarpılır. Böylece her asal için artan bir temel çarpan dizisi oluşur:
$$p,\ p^2,\ p^4,\ p^8,\ \dots.$$
Bu dizinin ilk \(r\) terimini seçersek çarpımları
$$p^{1+2+4+\dots+2^{r-1}}=p^{2^r-1}$$
olur; bu da bölen formülünün gerektirdiği üs biçimiyle tam olarak aynıdır.
Tüm asal dizilerini tek bir sonsuz çoklu kümede birleştirelim:
$$\mathcal{U}=\left\{p^{2^t}: p \text{ asal},\ t\ge 0\right\}.$$
Her geçerli çözüm, \(\mathcal{U}\) içinden tam \(K\) eleman seçmeye denktir; ancak her asalın kendi dizisi içinde seçim bir ön-ek olmak zorundadır. Elde edilen \(n\), seçilen elemanların çarpımıdır.
Şimdi önemli nokta şu: her dizi \(p,p^2,p^4,\dots\) sıkı biçimde artar. Dolayısıyla \(p^{2^t}\) terimi \(\mathcal{U}\)'nun en küçük \(K\) elemanı arasındaysa, aynı dizide ondan önce gelen tüm terimler daha da küçüktür ve onlar da en küçük \(K\) eleman arasında olmak zorundadır. Böylece en küçük \(K\) eleman ön-ek kuralını kendiliğinden sağlar.
Sonuç olarak minimum \(n\), \(\mathcal{U}\)'nun en küçük \(K\) elemanının çarpımıdır. Seçilmiş bir çarpanı daha büyük bir uygun çarpanla değiştirmek toplam çarpımı yalnızca büyütür.
\(n\)'de kullanılan her farklı asal en az bir birim tüketir. Bu yüzden optimal çözüm en fazla \(K\) farklı asal içerebilir. Daha küçük bir asal hiç kullanılmamışken daha büyük bir asal kullanılıyorsa, büyük olanı küçük olanla değiştirmek bölen sayısını değiştirmez ve \(n\)'yi kesin olarak küçültür.
Buna eşdeğer başka bir ifade de şudur: \(p_{K+1}\), \((K+1)\). asal olsun. Bunun ilk olası çarpanı \(p_{K+1}\)'dir; fakat ondan önce zaten
$$p_1,p_2,\dots,p_K$$
şeklinde \(K\) adet daha küçük başlangıç çarpanı vardır. Demek ki \(p_K\)'den sonraki asallardan gelen hiçbir terim ilk \(K\) seçimin içine giremez.
İlk \(K\) asalı bir min-heap içine yerleştiririz; her giriş, o asal için henüz kullanılmamış en küçük mevcut çarpanı temsil eder. Sonra tekrar tekrar en küçük mevcut çarpan \(q\) alınır, yürüyen cevap \(q\) ile çarpılır ve aynı asal için bir sonraki çarpan olan \(q^2\) tekrar heap'e konur. Tam \(K\) kez çıkarma yaptığımızda, izin verilen en küçük \(K\) çarpanı tam olarak üretmiş oluruz.
Mevcut çarpan \(q=p^{2^t}\) ise, aynı asalın bir sonraki çarpanı gerçekten
$$p^{2^{t+1}}=q^2$$
olur. Uygulamalar bu çarpanları devasa tamsayılar olarak karşılaştırmak yerine \(\log q\) ile sıralar; çünkü
$$q_1\lt q_2 \iff \log q_1\lt \log q_2.$$
Aynı anda bu çarpanın \(M\) modundaki kalanı da tutulur; böylece gerçek minimum sayıyı hiç oluşturmadan sonuç mod \(M\) olarak biriktirilir.
\(K=4\) için tam \(2^4=16\) bölen gerekir. Başlangıç heap çarpanları \(2,3,5,7\)'dir.
Greedy seçim şu sırayla ilerler:
$$\begin{aligned} \text{seç }2 &\Rightarrow \text{çarpım }=2,\ \text{sonraki teklif }=4,\\ \text{seç }3 &\Rightarrow \text{çarpım }=6,\ \text{sonraki teklif }=9,\\ \text{seç }4 &\Rightarrow \text{çarpım }=24,\ \text{sonraki teklif }=16,\\ \text{seç }5 &\Rightarrow \text{çarpım }=120,\ \text{sonraki teklif }=25. \end{aligned}$$
Seçilen çarpanlar \(2,3,4,5\) olduğundan
$$n=2\cdot 3\cdot 4\cdot 5=2^3\cdot 3\cdot 5=120$$
elde edilir. Bölen sayısı da
$$d(120)=(3+1)(1+1)(1+1)=16=2^4$$
olur; bu da uygulamaların kullandığı küçük kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı iskeleti izler. Önce, \(K\). asal için standart bir üst sınır tahmini kullanılarak bir sieve ile ilk \(K\) asal üretilir. İlk tahmin yetmezse sınır büyütülür ve sieve yeniden çalıştırılır.
Daha sonra bir min-heap kurulur. Her giriş, aynı mevcut çarpanın iki görünümünü taşır: sıralama için \(\log q\) ve modüler aritmetik için \(q\bmod M\). Başlangıçta heap'te ilk \(K\) asalın her biri için birer teklif bulunur.
\(K\) iterasyonun her birinde en küçük teklif çıkarılır, yürüyen cevap bunun modu ile çarpılır, bu mod değeri \(M\) altında karesine yükseltilir, logaritmik anahtar ikiyle çarpılır ve güncellenmiş teklif tekrar heap'e konur. Böylece izin verilen en küçük \(K\) çarpan tam sırayla üretilir. C++ uygulaması ayrıca greedy yapıyı küçük örneklerde doğrulayan minik kontrol testleri de içerir.
\(P_K\), \(K\). asal olsun. İlk \(K\) asalı \(P_K\)'ye kadar sıradan bir sieve ile üretmek \(O(P_K\log\log P_K)\) zaman ve \(O(P_K)\) bellek ister. Heap \(K\) giriş içerir; \(K\) adet çıkar-ekle adımı ise \(O(K\log K)\) zaman ve \(O(K)\) ek bellek gerektirir.
\(P_K=\Theta(K\log K)\) olduğundan toplam çalışma süresi yaklaşık \(O(K\log K\log\log K)\), toplam bellek kullanımı ise \(O(P_K+K)\)'dir. Sabit \(K=500{,}500\) için bu rahatlıkla uygulanabilir düzeydedir.
Buscamos el menor entero positivo \(n\) cuyo número de divisores sea exactamente \(2^K\), con \(K=500{,}500\), y solo necesitamos su valor final módulo \(M=500{,}500{,}507\). El mínimo real es gigantesco, así que la solución no intenta construir \(n\) de forma explícita. En cambio, minimiza las decisiones sobre potencias primas que determinan a \(n\).
Escribamos la factorización prima de \(n\) como
$$n=\prod_{i\ge 1} p_i^{a_i},\qquad p_1\lt p_2\lt p_3\lt \dots.$$
La fórmula de la función divisor dice
$$d(n)=\prod_{i\ge 1}(a_i+1).$$
Por tanto, todo el problema queda controlado por la manera en que los factores \(a_i+1\) producen \(2^K\).
Como \(2^K\) no tiene factores primos impares, cada factor \(a_i+1\) del producto debe ser, él mismo, una potencia de dos. Así, existen enteros \(b_i\ge 0\) tales que
$$a_i+1=2^{b_i},\qquad a_i=2^{b_i}-1,$$
y la condición sobre el número de divisores pasa a ser
$$\sum_{i\ge 1} b_i=K.$$
En otras palabras, el problema equivale a distribuir \(K\) unidades idénticas entre los primos. Si el primo \(p_i\) recibe \(b_i\) unidades, su exponente final será \(2^{b_i}-1\).
Supongamos que un primo tiene actualmente exponente \(2^t-1\). Si le damos una unidad más, el exponente pasa a
$$2^{t+1}-1=(2^t-1)+2^t,$$
de modo que \(n\) se multiplica por
$$p^{2^t}.$$
Por tanto, cada primo genera una sucesión creciente de multiplicadores elementales posibles:
$$p,\ p^2,\ p^4,\ p^8,\ \dots.$$
Si tomamos los primeros \(r\) términos de esa sucesión, su producto es
$$p^{1+2+4+\dots+2^{r-1}}=p^{2^r-1},$$
que coincide exactamente con la forma de exponente exigida por la fórmula del número de divisores.
Juntemos todas las sucesiones primas en un único multiconjunto infinito:
$$\mathcal{U}=\left\{p^{2^t}: p \text{ primo},\ t\ge 0\right\}.$$
Cada solución válida equivale a elegir exactamente \(K\) elementos de \(\mathcal{U}\), con una restricción importante: dentro de la sucesión asociada a cada primo, la elección debe ser un prefijo. El entero final \(n\) es precisamente el producto de los elementos elegidos.
Ahora bien, cada sucesión \(p,p^2,p^4,\dots\) es estrictamente creciente. Por eso, si un término \(p^{2^t}\) aparece entre los \(K\) elementos más pequeños de \(\mathcal{U}\), todos los términos anteriores de esa misma sucesión son aún menores y también deben aparecer entre esos \(K\) menores. Así, los \(K\) menores elementos cumplen automáticamente la condición de prefijo.
En consecuencia, el mínimo posible de \(n\) es simplemente el producto de los \(K\) menores elementos de \(\mathcal{U}\). Sustituir cualquiera de ellos por un multiplicador mayor solo puede empeorar el producto final.
Cada primo distinto usado en \(n\) consume al menos una unidad, de modo que una solución óptima no puede involucrar más de \(K\) primos diferentes. Si se utilizara un primo grande mientras uno más pequeño quedara sin usar, cambiar el grande por el pequeño mantendría intacto el número de divisores y reduciría estrictamente \(n\).
De forma equivalente, si \(p_{K+1}\) es el primo número \((K+1)\), su primer multiplicador posible es \(p_{K+1}\), pero ya existen \(K\) multiplicadores iniciales más pequeños:
$$p_1,p_2,\dots,p_K.$$
Así, ningún término procedente de primos posteriores a \(p_K\) puede pertenecer a los primeros \(K\) multiplicadores elegidos.
Se empieza con los primeros \(K\) primos en un min-heap, donde cada entrada representa la oferta actual de ese primo. A continuación, se repite siempre el mismo proceso: sacar la menor oferta actual \(q\), multiplicar por \(q\) la respuesta acumulada e insertar la siguiente oferta del mismo primo, que es \(q^2\). Tras exactamente \(K\) extracciones, se ha multiplicado el conjunto de los \(K\) menores multiplicadores admisibles.
Si la oferta actual es \(q=p^{2^t}\), entonces la siguiente oferta del mismo primo es efectivamente
$$p^{2^{t+1}}=q^2.$$
Las implementaciones ordenan las ofertas usando \(\log q\) en vez del enorme entero \(q\), porque
$$q_1\lt q_2 \iff \log q_1\lt \log q_2.$$
Al mismo tiempo guardan esa misma oferta reducida módulo \(M\), con lo que el resultado final puede acumularse módulo \(M\) sin construir nunca el mínimo completo.
Para \(K=4\), necesitamos exactamente \(2^4=16\) divisores. Las ofertas iniciales del heap son \(2,3,5,7\).
La selección voraz avanza así:
$$\begin{aligned} \text{tomar }2 &\Rightarrow \text{producto }=2,\ \text{siguiente oferta }=4,\\ \text{tomar }3 &\Rightarrow \text{producto }=6,\ \text{siguiente oferta }=9,\\ \text{tomar }4 &\Rightarrow \text{producto }=24,\ \text{siguiente oferta }=16,\\ \text{tomar }5 &\Rightarrow \text{producto }=120,\ \text{siguiente oferta }=25. \end{aligned}$$
Los multiplicadores elegidos son \(2,3,4,5\), y por tanto
$$n=2\cdot 3\cdot 4\cdot 5=2^3\cdot 3\cdot 5=120.$$
Su número de divisores es
$$d(120)=(3+1)(1+1)(1+1)=16=2^4,$$
lo que coincide con el pequeño punto de control utilizado por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma estructura. Primero generan los primeros \(K\) primos mediante una criba y una cota superior estándar para el \(K\)-ésimo primo. Si la primera cota no alcanza, se amplía y la criba se repite.
Después construyen un min-heap cuyas entradas almacenan dos vistas de la misma oferta actual \(q\): una clave logarítmica \(\log q\) para ordenar y el residuo \(q\bmod M\) para la aritmética modular. Al principio, el heap contiene una oferta por cada uno de los primeros \(K\) primos.
En cada una de las \(K\) iteraciones se extrae la menor oferta, se multiplica la respuesta acumulada por su residuo módulo \(M\), se sustituye esa oferta por su cuadrado, se actualiza la clave logarítmica y la entrada se vuelve a insertar. De este modo se enumeran exactamente los \(K\) menores multiplicadores admisibles. La implementación en C++ añade además pequeñas comprobaciones sobre potencias de divisor muy pequeñas para validar la construcción voraz.
Sea \(P_K\) el \(K\)-ésimo primo. Generar los primeros \(K\) primos con una criba ordinaria hasta \(P_K\) cuesta \(O(P_K\log\log P_K)\) tiempo y \(O(P_K)\) memoria. El heap contiene \(K\) entradas, y las \(K\) operaciones de extraer e insertar cuestan \(O(K\log K)\) tiempo y \(O(K)\) memoria adicional.
Como \(P_K=\Theta(K\log K)\), el tiempo total es aproximadamente \(O(K\log K\log\log K)\), y la memoria total es \(O(P_K+K)\). Para el valor fijo \(K=500{,}500\), esto es perfectamente manejable.
题目要求最小的正整数 \(n\)，使它的约数个数恰好等于 \(2^K\)，其中 \(K=500{,}500\)。真正需要输出的并不是这个巨大整数本身，而是它对 \(M=500{,}500{,}507\) 取模后的结果。由于最小值本体极其庞大，解法不能直接构造 \(n\)，而必须只构造“哪些素数幂应该被乘进去”这一最优决策。
把 \(n\) 的素因数分解写成
$$n=\prod_{i\ge 1} p_i^{a_i},\qquad p_1\lt p_2\lt p_3\lt \dots.$$
约数函数公式告诉我们
$$d(n)=\prod_{i\ge 1}(a_i+1).$$
因此，题目的核心不在于直接搜索整数，而在于理解这些因子 \(a_i+1\) 如何相乘得到 \(2^K\)。
因为 \(2^K\) 没有任何奇素因子，所以乘积中的每个 \(a_i+1\) 本身也必须是 2 的幂。于是存在整数 \(b_i\ge 0\)，使得
$$a_i+1=2^{b_i},\qquad a_i=2^{b_i}-1,$$
并且约数条件等价于
$$\sum_{i\ge 1} b_i=K.$$
这意味着，我们可以把问题理解为：把 \(K\) 个完全相同的“预算单位”分配给不同的素数。若素数 \(p_i\) 分到 \(b_i\) 个单位，那么它在最终结果中的指数就是 \(2^{b_i}-1\)。
假设某个素数当前的指数是 \(2^t-1\)。如果再给它一个单位，那么指数就会变成
$$2^{t+1}-1=(2^t-1)+2^t,$$
于是整个 \(n\) 会额外乘上
$$p^{2^t}.$$
所以，对每个素数 \(p\) 而言，它对应着一条严格递增的“可选乘子”序列：
$$p,\ p^2,\ p^4,\ p^8,\ \dots.$$
如果对同一个素数取前 \(r\) 个乘子，那么它们的乘积是
$$p^{1+2+4+\dots+2^{r-1}}=p^{2^r-1},$$
这正好就是约数公式要求的指数形状。
把所有素数的这些序列合并成一个无限多重集合：
$$\mathcal{U}=\left\{p^{2^t}: p \text{ 是素数},\ t\ge 0\right\}.$$
任意一个合法解，都等价于从 \(\mathcal{U}\) 里恰好选出 \(K\) 个元素，但要满足一个约束：对于同一个素数对应的序列，所选元素必须是该序列的一个前缀。最终的整数 \(n\)，就是这些被选元素的乘积。
关键观察是：每条序列 \(p,p^2,p^4,\dots\) 都严格递增。因此如果某个元素 \(p^{2^t}\) 已经进入了 \(\mathcal{U}\) 中最小的 \(K\) 个元素，那么同一条序列里更早的元素一定更小，也必然同时位于这最小的 \(K\) 个元素之中。换句话说，“取全局最小的 \(K\) 个元素”天然就满足前缀约束。
于是问题的答案就是 \(\mathcal{U}\) 中最小的 \(K\) 个元素之积。把其中任何一个已选乘子换成更大的可用乘子，只会让总乘积变大，不可能得到更优解。
每使用一个不同的素数，至少要消耗一个预算单位，所以最优解中出现的不同素数个数不可能超过 \(K\)。如果某个更大的素数被使用，而一个更小的素数完全没有使用，那么把大的换成小的并不会改变约数个数，却一定会让 \(n\) 变小。
也可以从初始乘子来理解：设 \(p_{K+1}\) 是第 \((K+1)\) 个素数，那么它的第一个可能乘子就是 \(p_{K+1}\)。但在它之前，已经有
$$p_1,p_2,\dots,p_K$$
这 \(K\) 个更小的初始乘子。因此，来自第 \(K\) 个素数之后的任何序列项，都不可能进入全局最小的前 \(K\) 个乘子。
算法先把前 \(K\) 个素数的当前乘子放入一个最小堆中。然后反复执行同一件事：取出当前最小乘子 \(q\)，把答案乘上 \(q\)，再把同一个素数的下一个乘子 \(q^2\) 放回堆里。做满 \(K\) 次后，恰好就把全局最小的 \(K\) 个允许乘子全部乘过一遍了。
如果当前乘子是 \(q=p^{2^t}\)，那么同一个素数的下一个乘子确实就是
$$p^{2^{t+1}}=q^2.$$
实现时并不直接比较巨大整数 \(q\)，而是比较 \(\log q\)，因为
$$q_1\lt q_2 \iff \log q_1\lt \log q_2.$$
与此同时，还把这个乘子对 \(M\) 取模后的值一并保存。这样就能在从头到尾都不构造完整大整数的前提下，持续维护最终答案的模值。
当 \(K=4\) 时，我们要求一个恰好有 \(2^4=16\) 个约数的最小整数。初始堆中的乘子是 \(2,3,5,7\)。
按贪心顺序取出时，过程如下：
$$\begin{aligned} \text{取 }2 &\Rightarrow \text{当前乘积 }=2,\ \text{新放回 }4,\\ \text{取 }3 &\Rightarrow \text{当前乘积 }=6,\ \text{新放回 }9,\\ \text{取 }4 &\Rightarrow \text{当前乘积 }=24,\ \text{新放回 }16,\\ \text{取 }5 &\Rightarrow \text{当前乘积 }=120,\ \text{新放回 }25. \end{aligned}$$
所以被选中的乘子是 \(2,3,4,5\)，从而
$$n=2\cdot 3\cdot 4\cdot 5=2^3\cdot 3\cdot 5=120.$$
它的约数个数为
$$d(120)=(3+1)(1+1)(1+1)=16=2^4,$$
与实现中使用的小规模校验结果完全一致。
C++、Python 和 Java 的实现遵循同一条主线。首先利用筛法生成前 \(K\) 个素数，并结合对第 \(K\) 个素数的常用上界估计来确定筛的范围。如果第一次估计不足，就扩大范围后重新筛。
接着建立一个最小堆。堆中的每个元素都保存同一个当前乘子的两种表示方式：一种是用于比较大小的对数键 \(\log q\)，另一种是用于更新答案的模值 \(q\bmod M\)。初始状态下，前 \(K\) 个素数各有一个当前乘子进入堆中。
在接下来的 \(K\) 次循环中，程序每次取出最小乘子，把答案乘上它的模值，然后把该乘子替换成平方后的下一项，再把更新后的条目放回堆里。这个过程正好按顺序枚举出全局最小的 \(K\) 个允许乘子。C++ 实现还额外加入了几个很小的检查点，用来验证贪心构造在小规模情况下的正确性。
设 \(P_K\) 表示第 \(K\) 个素数。用普通筛法在 \(P_K\) 以内生成前 \(K\) 个素数，需要 \(O(P_K\log\log P_K)\) 时间和 \(O(P_K)\) 空间。之后的堆中有 \(K\) 个元素，执行 \(K\) 次弹出加插入，总耗时为 \(O(K\log K)\)，额外空间为 \(O(K)\)。
由于 \(P_K=\Theta(K\log K)\)，总时间大致是 \(O(K\log K\log\log K)\)，总空间是 \(O(P_K+K)\)。对固定的 \(K=500{,}500\) 而言，这一规模完全可行。
Нужно найти наименьшее положительное число \(n\), у которого количество делителей равно точно \(2^K\), где \(K=500{,}500\), и вывести лишь значение по модулю \(M=500{,}500{,}507\). Само минимальное число колоссально велико, поэтому решение не пытается строить его напрямую. Вместо этого оно минимизирует набор простых степеней, из которых это число складывается.
Запишем разложение \(n\) на простые множители в виде
$$n=\prod_{i\ge 1} p_i^{a_i},\qquad p_1\lt p_2\lt p_3\lt \dots.$$
Формула для числа делителей имеет вид
$$d(n)=\prod_{i\ge 1}(a_i+1).$$
Следовательно, вся задача определяется тем, как множители \(a_i+1\) перемножаются в \(2^K\).
Поскольку у \(2^K\) нет нечётных простых делителей, каждый множитель \(a_i+1\) сам обязан быть степенью двойки. Значит, существуют целые \(b_i\ge 0\), такие что
$$a_i+1=2^{b_i},\qquad a_i=2^{b_i}-1,$$
а условие на число делителей превращается в
$$\sum_{i\ge 1} b_i=K.$$
То есть можно думать, что мы распределяем \(K\) одинаковых единиц бюджета между простыми числами. Если простое \(p_i\) получает \(b_i\) единиц, то его итоговый показатель будет равен \(2^{b_i}-1\).
Пусть у некоторого простого сейчас показатель \(2^t-1\). Если добавить ему ещё одну единицу, новый показатель станет
$$2^{t+1}-1=(2^t-1)+2^t,$$
а значит, число \(n\) домножается на
$$p^{2^t}.$$
Таким образом, каждому простому соответствует возрастающая последовательность допустимых элементарных множителей:
$$p,\ p^2,\ p^4,\ p^8,\ \dots.$$
Если взять первые \(r\) членов этой последовательности, их произведение равно
$$p^{1+2+4+\dots+2^{r-1}}=p^{2^r-1},$$
что в точности совпадает с формой показателя, диктуемой формулой для числа делителей.
Объединим все такие последовательности в одну бесконечную мультимножество:
$$\mathcal{U}=\left\{p^{2^t}: p \text{ простое},\ t\ge 0\right\}.$$
Любое допустимое решение эквивалентно выбору ровно \(K\) элементов из \(\mathcal{U}\), но с важным ограничением: внутри последовательности, соответствующей фиксированному простому, выбор обязан быть префиксом. Итоговое число \(n\) есть произведение выбранных элементов.
Ключевое наблюдение состоит в том, что каждая последовательность \(p,p^2,p^4,\dots\) строго возрастает. Поэтому если некоторый элемент \(p^{2^t}\) попал в число \(K\) наименьших элементов \(\mathcal{U}\), то все предыдущие элементы той же последовательности ещё меньше и тоже обязаны входить в этот набор. Значит, набор из \(K\) наименьших элементов автоматически удовлетворяет префиксному условию.
Следовательно, минимальное возможное \(n\) есть просто произведение \(K\) наименьших элементов \(\mathcal{U}\). Замена любого выбранного множителя на больший доступный только увеличит итоговый продукт.
Каждое различное простое в разложении \(n\) потребляет хотя бы одну единицу бюджета. Поэтому в оптимальном решении не может участвовать более \(K\) различных простых. Если бы использовалось большее простое при том, что меньшее простое вообще не используется, можно было бы заменить большее на меньшее, сохранить число делителей и строго уменьшить \(n\).
То же самое можно сказать через стартовые множители. Пусть \(p_{K+1}\) обозначает \((K+1)\)-е простое. Его первый возможный множитель равен \(p_{K+1}\), но уже существуют \(K\) меньших начальных множителей
$$p_1,p_2,\dots,p_K.$$
Значит, никакой член последовательностей для простых, больших чем \(p_K\), не может входить в число первых \(K\) выбранных множителей.
В начале в min-heap помещаются первые \(K\) простых, каждое в виде его текущего предложения. Затем многократно выполняется один и тот же шаг: извлекается наименьший текущий множитель \(q\), накопленный ответ домножается на \(q\), а в кучу возвращается следующий множитель для того же простого, то есть \(q^2\). После ровно \(K\) извлечений будут перемножены именно \(K\) наименьших допустимых множителей.
Если текущее предложение имеет вид \(q=p^{2^t}\), то следующее предложение для того же простого действительно равно
$$p^{2^{t+1}}=q^2.$$
В реализациях порядок определяется не огромным числом \(q\), а его логарифмом \(\log q\), поскольку
$$q_1\lt q_2 \iff \log q_1\lt \log q_2.$$
Одновременно хранится и значение этого же множителя по модулю \(M\), поэтому итог можно накапливать по модулю, никогда не материализуя само гигантское минимальное число.
При \(K=4\) нам нужно число с ровно \(2^4=16\) делителями. Начальные предложения в куче равны \(2,3,5,7\).
Жадный выбор идёт так:
$$\begin{aligned} \text{взять }2 &\Rightarrow \text{произведение }=2,\ \text{следующее предложение }=4,\\ \text{взять }3 &\Rightarrow \text{произведение }=6,\ \text{следующее предложение }=9,\\ \text{взять }4 &\Rightarrow \text{произведение }=24,\ \text{следующее предложение }=16,\\ \text{взять }5 &\Rightarrow \text{произведение }=120,\ \text{следующее предложение }=25. \end{aligned}$$
Итак, выбраны множители \(2,3,4,5\), а значит
$$n=2\cdot 3\cdot 4\cdot 5=2^3\cdot 3\cdot 5=120.$$
Число его делителей равно
$$d(120)=(3+1)(1+1)(1+1)=16=2^4,$$
что совпадает с малым контрольным примером, используемым в реализациях.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала они генерируют первые \(K\) простых при помощи решета и стандартной верхней оценки для \(K\)-го простого. Если первая оценка оказывается недостаточной, граница увеличивается, и решето запускается ещё раз.
После этого строится min-heap, в котором каждая запись хранит две формы одного и того же текущего множителя \(q\): логарифмический ключ \(\log q\) для сравнения и остаток \(q\bmod M\) для модульной арифметики. Изначально в куче лежит по одному предложению для каждого из первых \(K\) простых.
На каждой из \(K\) итераций код извлекает минимальное предложение, домножает накопленный ответ на его остаток по модулю \(M\), заменяет его квадратом, обновляет логарифмический ключ и возвращает запись обратно в кучу. Тем самым в правильном порядке перечисляются ровно \(K\) наименьших допустимых множителей. В C++-реализации дополнительно есть маленькие проверки на совсем небольших значениях степени двойки для числа делителей.
Обозначим через \(P_K\) \(K\)-е простое. Генерация первых \(K\) простых обычным решетом до \(P_K\) требует \(O(P_K\log\log P_K)\) времени и \(O(P_K)\) памяти. Куча содержит \(K\) элементов, а \(K\) операций извлечения и вставки дают \(O(K\log K)\) времени и \(O(K)\) дополнительной памяти.
Так как \(P_K=\Theta(K\log K)\), суммарное время работы составляет примерно \(O(K\log K\log\log K)\), а суммарная память равна \(O(P_K+K)\). Для фиксированного значения \(K=500{,}500\) это вполне практично.
نريد أصغر عدد صحيح موجب \(n\) يكون عدد قواسمه مساويًا تمامًا لـ \(2^K\)، حيث \(K=500{,}500\)، ثم نأخذ الناتج فقط modulo \(M=500{,}500{,}507\). العدد الأدنى نفسه هائل جدًا، لذلك لا تبنيه الخوارزمية بصورة صريحة، بل تبحث عن أصغر مجموعة ممكنة من قرارات القوى الأولية التي تحدده.
لنكتب التحليل الأولي للعدد \(n\) على الصورة
$$n=\prod_{i\ge 1} p_i^{a_i},\qquad p_1\lt p_2\lt p_3\lt \dots.$$
وصيغة دالة عدد القواسم تقول إن
$$d(n)=\prod_{i\ge 1}(a_i+1).$$
إذًا جوهر المسألة هو فهم كيف تتكاثر الحدود \(a_i+1\) لتعطي \(2^K\).
بما أن \(2^K\) لا يملك أي عامل أولي فردي، فلا بد أن يكون كل حد من الحدود \(a_i+1\) نفسه قوةً للعدد 2. لذلك توجد أعداد صحيحة \(b_i\ge 0\) بحيث
$$a_i+1=2^{b_i},\qquad a_i=2^{b_i}-1,$$
ويصبح شرط عدد القواسم
$$\sum_{i\ge 1} b_i=K.$$
بمعنى آخر، يمكننا التفكير في المسألة على أنها توزيع \(K\) وحدات متطابقة على الأعداد الأولية. فإذا حصل العدد الأولي \(p_i\) على \(b_i\) وحدات، كان أسه النهائي هو \(2^{b_i}-1\).
افترض أن عددًا أوليًا ما يملك حاليًا الأس \(2^t-1\). إذا أعطيناه وحدة إضافية، يصبح الأس
$$2^{t+1}-1=(2^t-1)+2^t,$$
ولذلك يُضرب \(n\) في
$$p^{2^t}.$$
إذن كل عدد أولي يولد متتالية متزايدة من العوامل الابتدائية الممكنة:
$$p,\ p^2,\ p^4,\ p^8,\ \dots.$$
وإذا أخذنا أول \(r\) حدود من هذه المتتالية، فإن حاصل ضربها يساوي
$$p^{1+2+4+\dots+2^{r-1}}=p^{2^r-1},$$
وهو بالضبط شكل الأس الذي تفرضه صيغة عدد القواسم.
لنضم جميع هذه المتتاليات في متعدد مجموعة لا نهائي واحد:
$$\mathcal{U}=\left\{p^{2^t}: p \text{ prime},\ t\ge 0\right\}.$$
كل حل صحيح يكافئ اختيار \(K\) عنصرًا بالضبط من \(\mathcal{U}\)، لكن مع قيد مهم: داخل المتتالية الخاصة بكل عدد أولي ثابت، يجب أن يكون الاختيار بادئة من تلك المتتالية. والعدد النهائي \(n\) هو حاصل ضرب العناصر المختارة.
الملاحظة الحاسمة أن كل متتالية من الشكل \(p,p^2,p^4,\dots\) متزايدة بصرامة. لذلك إذا كان العنصر \(p^{2^t}\) ضمن أصغر \(K\) عناصر في \(\mathcal{U}\)، فإن جميع العناصر السابقة له في المتتالية نفسها أصغر منه، وبالتالي لا بد أن تكون هي أيضًا ضمن هذه العناصر \(K\). وهذا يعني أن أخذ أصغر \(K\) عناصر يحقق قيد البادئة تلقائيًا.
إذن أصغر قيمة ممكنة لـ \(n\) هي ببساطة حاصل ضرب أصغر \(K\) عناصر في \(\mathcal{U}\). واستبدال أي عامل مختار بعامل أكبر لا يمكن إلا أن يزيد الناتج النهائي.
كل عدد أولي مختلف يظهر في \(n\) يستهلك على الأقل وحدة واحدة من الميزانية، لذلك لا يمكن أن يحتوي الحل الأمثل على أكثر من \(K\) أعداد أولية مختلفة. وإذا استُخدم عدد أولي أكبر بينما بقي عدد أولي أصغر غير مستخدم، فإن استبدال الأكبر بالأصغر يحافظ على عدد القواسم ويجعل \(n\) أصغر قطعًا.
وبصياغة مكافئة: إذا كان \(p_{K+1}\) هو العدد الأولي رقم \((K+1)\)، فإن أول عامل ممكن له هو \(p_{K+1}\)، لكن توجد بالفعل \(K\) عوامل ابتدائية أصغر منه، وهي
$$p_1,p_2,\dots,p_K.$$
لذلك لا يمكن لأي حد قادم من عدد أولي بعد \(p_K\) أن يدخل ضمن أول \(K\) عوامل مختارة.
نبدأ بوضع أول \(K\) أعداد أولية في heap أدنى، بحيث تمثل كل عقدة العامل الحالي لذلك العدد الأولي. بعد ذلك نكرر العملية نفسها: نزيل أصغر عامل حالي \(q\)، ونضرب الجواب الجاري في \(q\)، ثم نعيد إدخال العامل التالي لنفس العدد الأولي، أي \(q^2\). وبعد تنفيذ هذه الخطوة \(K\) مرة نكون قد ضربنا بالفعل أصغر \(K\) عوامل مسموح بها.
إذا كان العامل الحالي هو \(q=p^{2^t}\)، فإن العامل التالي لنفس العدد الأولي هو فعلًا
$$p^{2^{t+1}}=q^2.$$
ولا تقارن التطبيقات هذه القيم كأعداد صحيحة هائلة، بل تستخدم \(\log q\) للمقارنة، لأن
$$q_1\lt q_2 \iff \log q_1\lt \log q_2.$$
وفي الوقت نفسه تحتفظ بالقيمة نفسها بعد أخذها modulo \(M\)، وبذلك يمكن تحديث الناتج modulo \(M\) طوال الوقت من دون بناء العدد الأدنى كاملًا.
عندما يكون \(K=4\)، نحتاج عددًا له بالضبط \(2^4=16\) قاسمًا. والعوامل الابتدائية الموجودة في heap في البداية هي \(2,3,5,7\).
يسير الاختيار الجشع كما يلي:
$$\begin{aligned} \text{pick }2 &\Rightarrow \text{prod }=2,\ \text{next }=4,\\ \text{pick }3 &\Rightarrow \text{prod }=6,\ \text{next }=9,\\ \text{pick }4 &\Rightarrow \text{prod }=24,\ \text{next }=16,\\ \text{pick }5 &\Rightarrow \text{prod }=120,\ \text{next }=25. \end{aligned}$$
إذن العوامل المختارة هي \(2,3,4,5\)، ومن ثم
$$n=2\cdot 3\cdot 4\cdot 5=2^3\cdot 3\cdot 5=120.$$
وعدد قواسمه يساوي
$$d(120)=(3+1)(1+1)(1+1)=16=2^4,$$
وهو تمامًا مثال التحقق الصغير المستخدم في التطبيقات.
تنفذ تطبيقات C++ وPython وJava الفكرة نفسها. أولًا تولد أول \(K\) عددًا أوليًا باستخدام sieve مع تقدير علوي قياسي للعدد الأولي رقم \(K\). وإذا لم يكفِ هذا التقدير الأول، تُزاد الحدود ويعاد تشغيل sieve.
بعد ذلك يُبنى heap أدنى، وتحمل كل عقدة صورتين للعامل الحالي نفسه \(q\): مفتاحًا لوغاريتميًا \(\log q\) من أجل الترتيب، والباقي \(q\bmod M\) من أجل الحسابات المعيارية. وفي البداية يحتوي heap على عامل واحد لكل من أول \(K\) عددًا أوليًا.
في كل واحدة من \(K\) دورة، يزيل التنفيذ أصغر عامل، ويضرب الجواب الجاري في باقيه modulo \(M\)، ثم يستبدل ذلك العامل بمربعه، ويحدث المفتاح اللوغاريتمي، ويعيد العنصر إلى heap. بهذه الطريقة تُعدَّد أصغر \(K\) عوامل مسموح بها بالترتيب الصحيح تمامًا. وتضيف نسخة C++ أيضًا اختبارات صغيرة جدًا على حالات محدودة للتأكد من صحة البناء الجشع.
ليكن \(P_K\) هو العدد الأولي رقم \(K\). توليد أول \(K\) عددًا أوليًا باستخدام sieve عادي حتى \(P_K\) يكلف \(O(P_K\log\log P_K)\) زمنًا و\(O(P_K)\) ذاكرة. ويحتوي heap على \(K\) عقد، أما عمليات الإزالة والإدراج وعددها \(K\) فتأخذ \(O(K\log K)\) زمنًا و\(O(K)\) ذاكرة إضافية.
وبما أن \(P_K=\Theta(K\log K)\)، فإن الزمن الكلي يقارب \(O(K\log K\log\log K)\)، بينما تكون الذاكرة الكلية \(O(P_K+K)\). وبالنسبة للقيمة الثابتة \(K=500{,}500\)، فهذا ضمن حدود عملية تمامًا.