For a positive integer \(n\), let \(b(n)\) denote the number of bi-unitary divisors of \(n\). The product of all bi-unitary divisors has the form \(n^{b(n)/2}\), so the integers counted by
$$Q_k(N)=\#\{1\le n\le N : b(n)=2k\}$$
are exactly the integers whose bi-unitary-divisor product equals \(n^k\). The task is to compute
$$\sum_{k=2}^{10} Q_k(10^{12}).$$
A brute-force scan up to \(10^{12}\) is impossible, so the solution works directly with prime exponents and counts only the exponent patterns that can produce the small targets \(2k\in\{4,6,\dots,20\}\).
Write the prime factorization of \(n\) as
$$n=\prod_{i=1}^r p_i^{e_i}.$$
The key observation is that the bi-unitary-divisor count depends only on the exponents \(e_i\), and the code exploits that structure very aggressively.
For \(p^e\), the ordinary divisors are \(1,p,p^2,\dots,p^e\). In the bi-unitary setting, every divisor survives except the middle divisor \(p^{e/2}\) when \(e\) is even. Therefore
$$b(p^e)= \begin{cases} e, & e \text{ is even},\\ e+1, & e \text{ is odd}, \end{cases}$$
which is the same as
$$b(p^e)=e+(e\bmod 2).$$
Because prime powers contribute independently, \(b(n)\) is multiplicative across the prime-power factors:
$$b(n)=\prod_{i=1}^r \bigl(e_i+(e_i\bmod 2)\bigr).$$
Separate primes with exponent at least \(2\) from the primes that appear only once:
$$n=\left(\prod_{i=1}^s p_i^{e_i}\right)\left(\prod_{j=1}^t q_j\right),\qquad e_i\ge 2,$$
where the \(q_j\) are distinct primes different from every \(p_i\). Then
$$b(n)=\left(\prod_{i=1}^s \bigl(e_i+(e_i\bmod 2)\bigr)\right)2^t.$$
Call the first factor \(c\). Once the heavy exponents are fixed, the only freedom left is the number \(t\) of exponent-\(1\) primes. To force \(b(n)=2k\), we need
$$2k=c\,2^t.$$
So \(2k/c\) must be a power of two. If that quotient is not a power of two, the chosen heavy part cannot contribute to \(Q_k(N)\).
Each heavy prime contributes at least a factor \(p^2\) to \(n\), so the numeric product grows quickly. At the same time, each heavy exponent contributes at least \(2\) to \(b(n)\), so the bi-unitary-divisor count also grows quickly.
Because the largest target here is \(2k=20\), only very small values of \(c\) are relevant. The implementation therefore performs a depth-first search over prime powers \(p^e\) with \(e\ge 2\), multiplies their contributions into the heavy product and into \(c\), and prunes the branch as soon as either
$$\text{heavy product}>N$$
or the current \(c\) can no longer divide any target \(2k\) with \(2\le k\le 10\).
Fix a heavy part
$$a=\prod_{i=1}^s p_i^{e_i}$$
and suppose that \(2k=c\,2^t\). Then every corresponding integer has the form
$$n=a\,q_1q_2\cdots q_t,$$
with distinct primes
$$q_1<q_2<\cdots<q_t,\qquad q_j\notin\{p_1,\dots,p_s\},$$
and the product restriction
$$a\,q_1q_2\cdots q_t\le N.$$
When \(t=0\), the heavy part itself contributes one solution. When \(t=1\), we only need to count primes \(q\le N/a\) while excluding the heavy primes already used. When \(t\ge 2\), the implementation recursively chooses increasing primes and updates the remaining bound after every choice.
The crucial optimization is the base case \(t=1\): instead of scanning primes one by one, the algorithm queries the prime-counting function \(\pi(x)\). To make those queries fast, it precomputes \(\pi(x)\) on the standard set of arguments
$$x\in\{1,2,\dots,\lfloor\sqrt N\rfloor\}\cup\left\{\left\lfloor\frac{N}{i}\right\rfloor:1\le i\le \lfloor\sqrt N\rfloor\right\}.$$
Instead of rebuilding the search from scratch for every \(k\), the implementation first computes the cumulative quantity
$$C(k)=\sum_{j=2}^k Q_j(N).$$
Every heavy-part pattern can contribute to several targets \(2j\), so the search tree is reused while accumulating \(C(k)\). After that, the exact count is recovered by the telescoping identity
$$Q_k(N)=C(k)-C(k-1).$$
This is especially effective here because the targets are very small and heavily overlap.
Here the target condition is \(b(n)=4\). We classify possibilities by the heavy factor \(c\).
If \(c=1\), then \(t=2\), so \(n=pq\) with distinct primes and \(pq\le 100\). These are the squarefree semiprimes, and there are \(30\) of them.
If \(c=2\), then \(t=1\). The only way to get \(c=2\) from a heavy exponent is \(p^2\), so we count numbers of the form \(p^2q\) with \(p\ne q\) prime and \(p^2q\le 100\). Grouping by \(p\) gives
$$8+4+2+1=15,$$
coming from \(p=2,3,5,7\).
If \(c=4\), then \(t=0\), so the heavy part alone must satisfy \(b(n)=4\). The possible shapes are
$$p^3,\qquad p^4,\qquad p^2q^2.$$
Under \(100\), these contribute \(2\), \(2\), and \(2\) cases respectively, so this branch contributes \(6\).
Therefore
$$Q_2(100)=30+15+6=51,$$
which matches the checkpoint built into the implementation.
The C++, Python, and Java implementations follow the same number-theoretic strategy. The C++ and Java versions contain the full combinatorial search, while the Python version delegates to the compiled implementation, so the observable algorithm is the same in all three languages.
First, the implementation generates primes up to about \(2\sqrt N\) and builds a fast \(\pi(x)\) table on the complementary floor-division values needed by the recursion. Next, it enumerates every admissible heavy part made of prime powers \(p^e\) with \(e\ge 2\), carrying both the numeric contribution of that part and its multiplicative contribution to \(b(n)\).
For each heavy part, the implementation tests every target \(2j\) up to the required bound. If the remaining quotient is a power of two, it knows exactly how many exponent-\(1\) primes must still be appended. Those squarefree completions are counted recursively with increasing primes, and the final one-prime case is handled by the precomputed prime-counting table instead of explicit iteration.
Finally, cumulative values are cached, individual \(Q_k(N)\) values are recovered by subtraction, and the required sum over \(k=2,\dots,10\) is produced.
Let \(R=\lfloor\sqrt N\rfloor\). The prime sieve and the prime-counting table both use \(O(R)\) memory and near \(O(R\log\log R)\) time. The search over heavy parts is far smaller than a full factorization sweep, because every new heavy prime costs at least a square factor and every new heavy exponent multiplies the bi-unitary-divisor factor by at least \(2\).
For this particular problem the squarefree-completion recursion is very shallow: since \(2k\le 20\), the power-of-two quotient is at most \(16\), so at most four exponent-\(1\) primes ever need to be appended. In practice, the runtime is dominated by prime preprocessing and a modest number of prime-counting queries, while the memory usage remains \(O(\sqrt N)\).
Für eine positive ganze Zahl \(n\) bezeichne \(b(n)\) die Anzahl der bi-unitären Teiler von \(n\). Das Produkt aller bi-unitären Teiler hat die Form \(n^{b(n)/2}\), also zählen
$$Q_k(N)=\#\{1\le n\le N : b(n)=2k\}$$
genau die Zahlen, deren Produkt aller bi-unitären Teiler gleich \(n^k\) ist. Gesucht ist
$$\sum_{k=2}^{10} Q_k(10^{12}).$$
Eine direkte Suche bis \(10^{12}\) ist ausgeschlossen. Deshalb arbeitet die Lösung nicht mit den Zahlen selbst, sondern mit den Exponenten ihrer Primfaktorzerlegung.
Schreibe
$$n=\prod_{i=1}^r p_i^{e_i}.$$
Die entscheidende Beobachtung lautet: \(b(n)\) hängt nur von den Exponenten \(e_i\) ab, und für die kleinen Zielwerte \(2k\in\{4,6,\dots,20\}\) kommen nur sehr wenige Exponentenmuster überhaupt in Frage.
Für \(p^e\) sind die gewöhnlichen Teiler \(1,p,p^2,\dots,p^e\). Im bi-unitären Fall bleibt jeder Teiler erhalten, außer dem mittleren Teiler \(p^{e/2}\), falls \(e\) gerade ist. Daher gilt
$$b(p^e)= \begin{cases} e, & e \text{ gerade ist},\\ e+1, & e \text{ ungerade ist}, \end{cases}$$
also kompakt
$$b(p^e)=e+(e\bmod 2).$$
Da verschiedene Primzahlpotenzen unabhängig beitragen, ist \(b(n)\) bezüglich der Primzahlpotenzfaktoren multiplikativ:
$$b(n)=\prod_{i=1}^r \bigl(e_i+(e_i\bmod 2)\bigr).$$
Trenne die Primzahlen mit Exponent mindestens \(2\) von den Primzahlen mit Exponent \(1\):
$$n=\left(\prod_{i=1}^s p_i^{e_i}\right)\left(\prod_{j=1}^t q_j\right),\qquad e_i\ge 2,$$
wobei die \(q_j\) paarweise verschieden und von allen \(p_i\) verschieden sind. Dann folgt
$$b(n)=\left(\prod_{i=1}^s \bigl(e_i+(e_i\bmod 2)\bigr)\right)2^t.$$
Den ersten Faktor nennen wir \(c\). Sind die schweren Exponenten fest, bleibt nur noch die Anzahl \(t\) der Primzahlen mit Exponent \(1\). Um \(b(n)=2k\) zu erzwingen, braucht man
$$2k=c\,2^t.$$
Somit muss \(2k/c\) eine Zweierpotenz sein. Ist das nicht der Fall, kann der gewählte schwere Teil nie zu \(Q_k(N)\) beitragen.
Jede schwere Primzahl trägt mindestens einen Faktor \(p^2\) zu \(n\) bei, deshalb wächst das Zahlenprodukt sehr schnell. Gleichzeitig liefert jeder schwere Exponent mindestens den Faktor \(2\) zu \(b(n)\), also wächst auch die bi-unitäre Teileranzahl rasch.
Da hier der größte Zielwert nur \(2k=20\) ist, sind nur sehr kleine Werte von \(c\) relevant. Die Implementierung führt daher eine Tiefensuche über Primzahlpotenzen \(p^e\) mit \(e\ge 2\) aus, multipliziert ihre Beiträge in den schweren Zahlenteil und in \(c\) hinein und schneidet den Ast sofort ab, sobald entweder
$$\text{schwerer Teil}>N$$
oder der aktuelle Wert von \(c\) keinen Zielwert \(2k\) mit \(2\le k\le 10\) mehr teilen kann.
Fixiere einen schweren Teil
$$a=\prod_{i=1}^s p_i^{e_i}$$
und nehme an, dass \(2k=c\,2^t\) gilt. Dann hat jede zugehörige Zahl die Form
$$n=a\,q_1q_2\cdots q_t,$$
mit verschiedenen Primzahlen
$$q_1<q_2<\cdots<q_t,\qquad q_j\notin\{p_1,\dots,p_s\},$$
und der Nebenbedingung
$$a\,q_1q_2\cdots q_t\le N.$$
Für \(t=0\) liefert der schwere Teil selbst genau eine Lösung. Für \(t=1\) müssen nur Primzahlen \(q\le N/a\) gezählt werden, wobei die schon im schweren Teil verwendeten Primzahlen ausgeschlossen werden. Für \(t\ge 2\) wählt die Implementierung die Primzahlen rekursiv in aufsteigender Reihenfolge und aktualisiert nach jeder Wahl die verbleibende Schranke.
Die wichtigste Optimierung liegt im Fall \(t=1\): Statt Primzahlen einzeln zu durchlaufen, fragt der Algorithmus die Primzahlzählfunktion \(\pi(x)\) ab. Damit diese Abfragen schnell sind, wird \(\pi(x)\) auf der Standardmenge von Argumenten vorab berechnet:
$$x\in\{1,2,\dots,\lfloor\sqrt N\rfloor\}\cup\left\{\left\lfloor\frac{N}{i}\right\rfloor:1\le i\le \lfloor\sqrt N\rfloor\right\}.$$
Statt für jedes \(k\) den Suchbaum neu aufzubauen, berechnet die Implementierung zuerst die kumulative Größe
$$C(k)=\sum_{j=2}^k Q_j(N).$$
Jedes Muster des schweren Teils kann zu mehreren Zielwerten \(2j\) beitragen, deshalb lohnt es sich, denselben Suchbaum beim Aufbau von \(C(k)\) wiederzuverwenden. Danach erhält man die exakte Zahl durch
$$Q_k(N)=C(k)-C(k-1).$$
Gerade hier ist das sehr effektiv, weil die Zielwerte klein sind und stark überlappen.
Hier lautet die Zielbedingung \(b(n)=4\). Wir klassifizieren nach dem schweren Faktor \(c\).
Falls \(c=1\), dann ist \(t=2\), also \(n=pq\) mit verschiedenen Primzahlen und \(pq\le 100\). Das sind die quadratfreien Semiprime, insgesamt \(30\) Stück.
Falls \(c=2\), dann ist \(t=1\). Der einzige schwere Exponent mit Beitrag \(2\) ist \(p^2\), also zählen wir Zahlen der Form \(p^2q\) mit \(p\ne q\) prim und \(p^2q\le 100\). Nach \(p\) gruppiert erhält man
$$8+4+2+1=15,$$
entsprechend \(p=2,3,5,7\).
Falls \(c=4\), dann ist \(t=0\), also muss schon der schwere Teil allein \(b(n)=4\) erfüllen. Die möglichen Formen sind
$$p^3,\qquad p^4,\qquad p^2q^2.$$
Unter \(100\) liefern diese jeweils \(2\), \(2\) und \(2\) Fälle, zusammen also \(6\).
Damit folgt
$$Q_2(100)=30+15+6=51,$$
genau der Kontrollwert aus der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen derselben zahlentheoretischen Strategie. Die vollständige kombinatorische Suche steckt in den C++- und Java-Versionen; die Python-Version delegiert an die kompilierte Implementierung, sodass das beobachtbare Verhalten in allen drei Sprachen identisch ist.
Zuerst erzeugt die Implementierung alle Primzahlen bis etwa \(2\sqrt N\) und baut eine schnelle Tabelle für \(\pi(x)\) auf den komplementären Ganzzahlwerten der Form \(\lfloor N/i\rfloor\) auf. Danach enumeriert sie alle zulässigen schweren Teile aus Primzahlpotenzen \(p^e\) mit \(e\ge 2\) und verfolgt dabei sowohl den numerischen Wert dieses Teils als auch seinen multiplikativen Beitrag zu \(b(n)\).
Für jeden schweren Teil prüft die Implementierung alle Zielwerte \(2j\) bis zur geforderten Schranke. Ist der verbleibende Quotient eine Zweierpotenz, steht damit exakt fest, wie viele Primzahlen mit Exponent \(1\) noch ergänzt werden müssen. Diese quadratfreien Ergänzungen werden rekursiv mit aufsteigenden Primzahlen gezählt; der letzte Ein-Primzahl-Fall wird nicht durch Iteration, sondern durch die vorbereitete Primzahlzählfunktion behandelt.
Am Ende werden kumulative Werte zwischengespeichert, die einzelnen \(Q_k(N)\) durch Differenzen gewonnen und schließlich die geforderte Summe über \(k=2,\dots,10\) ausgegeben.
Sei \(R=\lfloor\sqrt N\rfloor\). Primzahlsieb und Primzahlzählfunktionstabelle benötigen beide \(O(R)\) Speicher und ungefähr \(O(R\log\log R)\) Zeit. Die Suche über die schweren Teile ist viel kleiner als ein vollständiger Faktorisierungsdurchlauf, weil jede zusätzliche schwere Primzahl mindestens einen Quadratsfaktor kostet und jeder zusätzliche schwere Exponent den bi-unitären Teilerfaktor mindestens verdoppelt.
Für dieses Problem ist die Rekursion über den quadratfreien Rest besonders flach: Da \(2k\le 20\) gilt, ist der verbleibende Zweierpotenzquotient höchstens \(16\), also müssen höchstens vier Primzahlen mit Exponent \(1\) ergänzt werden. Praktisch wird die Laufzeit daher von der Primvorbereitung und einer überschaubaren Zahl von \(\pi(x)\)-Abfragen dominiert, während der Speicherverbrauch \(O(\sqrt N)\) bleibt.
Pozitif bir \(n\) tamsayısı için \(b(n)\), \(n\)'in bi-unitary bölenlerinin sayısı olsun. Tüm bi-unitary bölenlerin çarpımı \(n^{b(n)/2}\) biçimindedir; dolayısıyla
$$Q_k(N)=\#\{1\le n\le N : b(n)=2k\}$$
tam olarak bi-unitary bölenlerinin çarpımı \(n^k\) olan sayıları sayar. Amaç
$$\sum_{k=2}^{10} Q_k(10^{12})$$
değerini hesaplamaktır. \(10^{12}\)'ye kadar doğrudan tarama mümkün olmadığından çözüm, sayıları tek tek denemek yerine asal üs örüntülerini sayar.
\(n\)'nin asal çarpanlara ayrılışını
$$n=\prod_{i=1}^r p_i^{e_i}$$
şeklinde yazalım. Temel gözlem şudur: \(b(n)\) yalnızca üsler \(e_i\)'lere bağlıdır ve burada hedef değerler \(2k\in\{4,6,\dots,20\}\) kadar küçük olduğu için mümkün üs desenleri çok sınırlıdır.
\(p^e\) için sıradan bölenler \(1,p,p^2,\dots,p^e\) olur. Bi-unitary durumda, \(e\) çiftken tam ortadaki bölen \(p^{e/2}\) dışında hepsi geçerlidir. Bu yüzden
$$b(p^e)= \begin{cases} e, & e \text{ çiftse},\\ e+1, & e \text{ tekse}, \end{cases}$$
ya da daha kısa biçimde
$$b(p^e)=e+(e\bmod 2).$$
Farklı asal kuvvetlerin katkıları bağımsız olduğundan, \(b(n)\) asal kuvvet çarpanları üzerinde çarpımsaldır:
$$b(n)=\prod_{i=1}^r \bigl(e_i+(e_i\bmod 2)\bigr).$$
Üssü en az \(2\) olan asalları, üssü tam \(1\) olan asallardan ayıralım:
$$n=\left(\prod_{i=1}^s p_i^{e_i}\right)\left(\prod_{j=1}^t q_j\right),\qquad e_i\ge 2,$$
burada \(q_j\)'ler birbirinden farklı asallardır ve hiçbirisi \(p_i\)'lerden biri değildir. O zaman
$$b(n)=\left(\prod_{i=1}^s \bigl(e_i+(e_i\bmod 2)\bigr)\right)2^t.$$
İlk çarpana \(c\) diyelim. Ağır üsler sabitlendiğinde geriye sadece üs \(1\) olan asal sayısı \(t\) kalır. \(b(n)=2k\) olması için
$$2k=c\,2^t$$
olmalıdır. Yani \(2k/c\) mutlaka 2'nin kuvveti olmalıdır. Bu sağlanmıyorsa seçilen ağır kısım \(Q_k(N)\)'ye hiç katkı yapamaz.
Her ağır asal, \(n\)'ye en az \(p^2\) çarpanı getirir; dolayısıyla sayısal değer çok hızlı büyür. Aynı anda her ağır üs, \(b(n)\)'ye en az \(2\) katsayısı ekler; yani bi-unitary bölen sayısı da hızla artar.
Burada en büyük hedef sadece \(2k=20\) olduğu için, ancak çok küçük \(c\) değerleri anlamlıdır. Bu nedenle uygulama \(e\ge 2\) olan asal kuvvetler üzerinde derinlik öncelikli bir arama yapar, bunların hem sayısal çarpımını hem de \(c\) katkısını günceller ve şu iki durumdan biri ortaya çıkar çıkmaz dalı budar:
$$\text{ağır kısım}>N$$
veya mevcut \(c\) değeri artık \(2\le k\le 10\) aralığındaki hiçbir hedef \(2k\)'yi bölemez.
Şimdi sabit bir ağır kısım alalım:
$$a=\prod_{i=1}^s p_i^{e_i}$$
ve \(2k=c\,2^t\) olsun. O zaman ilgili her sayı şu biçimdedir:
$$n=a\,q_1q_2\cdots q_t,$$
burada asallar birbirinden farklıdır ve artan sıradadır:
$$q_1<q_2<\cdots<q_t,\qquad q_j\notin\{p_1,\dots,p_s\},$$
ayrıca ürün koşulu
$$a\,q_1q_2\cdots q_t\le N$$
sağlanmalıdır. \(t=0\) ise ağır kısım tek başına bir çözümdür. \(t=1\) ise sadece \(q\le N/a\) olan asalları, ağır kısımda kullanılmış asalları dışlayarak saymak gerekir. \(t\ge 2\) olduğunda uygulama artan asalları özyinelemeli olarak seçer ve her seçimden sonra kalan sınırı günceller.
Asıl hızlandırma \(t=1\) taban durumunda gelir: asalları tek tek gezmek yerine algoritma doğrudan \(\pi(x)\) asal sayma fonksiyonunu sorgular. Bu sorguların hızlı olması için \(\pi(x)\), standart şu değer kümesi üzerinde önceden hesaplanır:
$$x\in\{1,2,\dots,\lfloor\sqrt N\rfloor\}\cup\left\{\left\lfloor\frac{N}{i}\right\rfloor:1\le i\le \lfloor\sqrt N\rfloor\right\}.$$
Uygulama her \(k\) için aramayı baştan kurmak yerine önce
$$C(k)=\sum_{j=2}^k Q_j(N)$$
kümülatif büyüklüğünü hesaplar. Aynı ağır-kısım ağacı birden fazla hedef \(2j\)'ye katkı verebildiğinden, bu ağaç \(C(k)\) oluşturulurken tekrar kullanılır. Sonra tam değer şu farkla elde edilir:
$$Q_k(N)=C(k)-C(k-1).$$
Hedefler küçük ve birbirine yakın olduğundan bu yeniden kullanım burada oldukça etkilidir.
Burada hedef koşul \(b(n)=4\)'tür. Olasılıkları ağır katsayı \(c\)'ye göre ayıralım.
\(c=1\) ise \(t=2\) olur; yani \(n=pq\), burada \(p\) ve \(q\) farklı asallar ve \(pq\le 100\). Bunlar karefree yarı-asallardır ve sayıları \(30\)'dur.
\(c=2\) ise \(t=1\) olur. Ağır kısımdan \(c=2\) üretmenin tek yolu \(p^2\)'dir. Dolayısıyla \(p\ne q\) asal ve \(p^2q\le 100\) olan \(p^2q\) biçimindeki sayıları sayarız. \(p\)'ye göre gruplayınca
$$8+4+2+1=15$$
elde edilir; bunlar sırasıyla \(p=2,3,5,7\) durumlarından gelir.
\(c=4\) ise \(t=0\) olur; yani ağır kısım tek başına \(b(n)=4\) üretmelidir. Mümkün şekiller
$$p^3,\qquad p^4,\qquad p^2q^2$$
olur. \(100\) altında bunlar sırasıyla \(2\), \(2\) ve \(2\) örnek verir; toplam katkı \(6\)'dır.
Sonuç olarak
$$Q_2(100)=30+15+6=51,$$
ve bu değer uygulamadaki kontrol sonucu ile aynıdır.
C++, Python ve Java uygulamaları aynı sayı kuramsal planı izler. Tam kombinatoryal arama C++ ve Java sürümlerinde yer alır; Python sürümü ise derlenmiş uygulamayı çağırır. Bu nedenle gözlenen algoritma üç dilde de aynıdır.
Önce yaklaşık \(2\sqrt N\)'ye kadar tüm asallar üretilir ve özyineleme sırasında gereken tamamlayıcı taban bölme değerleri için hızlı bir \(\pi(x)\) tablosu kurulur. Ardından \(e\ge 2\) olan asal kuvvetlerden oluşan bütün geçerli ağır kısımlar gezilir; bu sırada hem bu kısmın sayısal değeri hem de \(b(n)\)'ye yaptığı çarpımsal katkı birlikte taşınır.
Her ağır kısım için uygulama gerekli üst sınıra kadar bütün hedef \(2j\) değerlerini dener. Kalan bölüm 2'nin kuvveti ise, kaç tane üs-\(1\) asalın eklenmesi gerektiği tam olarak belirlenmiş olur. Bu karefree tamamlamalar artan asallarla özyinelemeli biçimde sayılır; son tek-asal durumu ise açık döngüyle değil, önceden hazırlanmış asal sayma tablosuyla çözülür.
Son aşamada kümülatif değerler önbelleğe alınır, tek tek \(Q_k(N)\) sonuçları fark alınarak elde edilir ve istenen \(k=2,\dots,10\) toplamı üretilir.
\(R=\lfloor\sqrt N\rfloor\) olsun. Asal eleği ve asal sayma tablosu \(O(R)\) bellek ve yaklaşık \(O(R\log\log R)\) zaman kullanır. Ağır kısımlar üzerindeki arama, tam bir çarpanlara ayırma taramasına göre çok daha küçüktür; çünkü her yeni ağır asal en az bir kare çarpanı getirir ve her yeni ağır üs bi-unitary bölen katsayısını en az \(2\) ile çarpar.
Bu problemde karefree tamamlama özyinelemesi çok sığdır: \(2k\le 20\) olduğundan, geriye kalan 2-kuvveti bölüm en fazla \(16\) olabilir; dolayısıyla en fazla dört tane üs-\(1\) asal eklenir. Pratikte süreyi asıl belirleyen şey asal ön işlemesi ve sınırlı sayıdaki \(\pi(x)\) sorgusudur; bellek tüketimi ise \(O(\sqrt N)\) düzeyinde kalır.
Para un entero positivo \(n\), sea \(b(n)\) el número de divisores bi-unitarios de \(n\). El producto de todos los divisores bi-unitarios tiene la forma \(n^{b(n)/2}\), así que
$$Q_k(N)=\#\{1\le n\le N : b(n)=2k\}$$
cuenta exactamente los enteros cuyo producto de divisores bi-unitarios es \(n^k\). El objetivo es calcular
$$\sum_{k=2}^{10} Q_k(10^{12}).$$
Recorrer todos los enteros hasta \(10^{12}\) no es viable, por lo que la solución trabaja directamente con los exponentes primos y solo cuenta los patrones que pueden producir los pequeños valores \(2k\in\{4,6,\dots,20\}\).
Escribimos la factorización prima de \(n\) como
$$n=\prod_{i=1}^r p_i^{e_i}.$$
La observación central es que \(b(n)\) depende únicamente de los exponentes \(e_i\), y las implementaciones aprovechan esa estructura de forma directa.
Para \(p^e\), los divisores ordinarios son \(1,p,p^2,\dots,p^e\). En el caso bi-unitario, todos sobreviven salvo el divisor central \(p^{e/2}\) cuando \(e\) es par. Por tanto,
$$b(p^e)= \begin{cases} e, & e \text{ es par},\\ e+1, & e \text{ es impar}, \end{cases}$$
lo cual equivale a
$$b(p^e)=e+(e\bmod 2).$$
Como las contribuciones de distintas potencias primas son independientes, \(b(n)\) es multiplicativa respecto a esos factores:
$$b(n)=\prod_{i=1}^r \bigl(e_i+(e_i\bmod 2)\bigr).$$
Separamos los primos con exponente al menos \(2\) de los primos que aparecen exactamente una vez:
$$n=\left(\prod_{i=1}^s p_i^{e_i}\right)\left(\prod_{j=1}^t q_j\right),\qquad e_i\ge 2,$$
donde los \(q_j\) son primos distintos entre sí y también distintos de todos los \(p_i\). Entonces
$$b(n)=\left(\prod_{i=1}^s \bigl(e_i+(e_i\bmod 2)\bigr)\right)2^t.$$
Llamemos \(c\) al primer factor. Una vez fijados los exponentes pesados, solo queda decidir cuántos primos de exponente \(1\) se añaden. Para imponer \(b(n)=2k\), debe cumplirse
$$2k=c\,2^t.$$
Así, el cociente \(2k/c\) tiene que ser una potencia de \(2\). Si no lo es, esa parte pesada nunca puede contribuir a \(Q_k(N)\).
Cada primo pesado aporta al menos un factor \(p^2\) al valor de \(n\), de modo que el producto numérico crece con rapidez. Al mismo tiempo, cada exponente pesado aporta al menos un factor \(2\) a \(b(n)\), así que el conteo de divisores bi-unitarios también crece rápidamente.
Como aquí el mayor objetivo es solo \(2k=20\), únicamente importan valores muy pequeños de \(c\). Por eso la implementación hace una búsqueda en profundidad sobre potencias primas \(p^e\) con \(e\ge 2\), multiplicando sus contribuciones tanto en la parte pesada como en \(c\), y poda la rama en cuanto ocurre una de estas dos cosas:
$$\text{parte pesada}>N$$
o bien el valor actual de \(c\) ya no puede dividir a ningún objetivo \(2k\) con \(2\le k\le 10\).
Fijemos una parte pesada
$$a=\prod_{i=1}^s p_i^{e_i}$$
y supongamos que \(2k=c\,2^t\). Entonces cualquier entero correspondiente tiene la forma
$$n=a\,q_1q_2\cdots q_t,$$
con primos distintos
$$q_1<q_2<\cdots<q_t,\qquad q_j\notin\{p_1,\dots,p_s\},$$
y restricción
$$a\,q_1q_2\cdots q_t\le N.$$
Si \(t=0\), la propia parte pesada aporta una solución. Si \(t=1\), solo hay que contar primos \(q\le N/a\), excluyendo los primos ya usados en la parte pesada. Si \(t\ge 2\), la implementación elige recursivamente primos crecientes y actualiza la cota restante después de cada elección.
La optimización decisiva aparece en el caso base \(t=1\): en vez de recorrer los primos uno por uno, el algoritmo consulta la función contadora de primos \(\pi(x)\). Para que esas consultas sean rápidas, se precalcula \(\pi(x)\) en el conjunto estándar de argumentos
$$x\in\{1,2,\dots,\lfloor\sqrt N\rfloor\}\cup\left\{\left\lfloor\frac{N}{i}\right\rfloor:1\le i\le \lfloor\sqrt N\rfloor\right\}.$$
En lugar de reconstruir la búsqueda para cada \(k\), la implementación calcula primero la cantidad acumulada
$$C(k)=\sum_{j=2}^k Q_j(N).$$
Un mismo patrón de parte pesada puede contribuir a varios objetivos \(2j\), así que conviene reutilizar el mismo árbol de búsqueda al formar \(C(k)\). Después, el valor exacto se obtiene mediante
$$Q_k(N)=C(k)-C(k-1).$$
Esta reutilización es especialmente útil aquí porque los objetivos son pequeños y muy cercanos entre sí.
Aquí la condición objetivo es \(b(n)=4\). Clasificamos los casos según el factor pesado \(c\).
Si \(c=1\), entonces \(t=2\), así que \(n=pq\) con primos distintos y \(pq\le 100\). Estos son los semiprimos libres de cuadrados, y hay \(30\).
Si \(c=2\), entonces \(t=1\). La única forma de obtener \(c=2\) desde la parte pesada es \(p^2\), de modo que contamos números de la forma \(p^2q\) con \(p\ne q\) primo y \(p^2q\le 100\). Agrupando por \(p\), obtenemos
$$8+4+2+1=15,$$
procedentes de \(p=2,3,5,7\).
Si \(c=4\), entonces \(t=0\), así que la parte pesada por sí sola debe producir \(b(n)=4\). Las formas posibles son
$$p^3,\qquad p^4,\qquad p^2q^2.$$
Bajo \(100\), estas aportan \(2\), \(2\) y \(2\) casos respectivamente; en total, \(6\).
Por tanto,
$$Q_2(100)=30+15+6=51,$$
que coincide con el valor de comprobación usado por la implementación.
Las implementaciones en C++, Python y Java siguen el mismo plan de teoría de números. Las versiones en C++ y Java contienen la búsqueda combinatoria completa; la versión en Python delega en la implementación compilada, por lo que el comportamiento observado es el mismo en los tres lenguajes.
Primero, la implementación genera todos los primos hasta aproximadamente \(2\sqrt N\) y construye una tabla rápida para \(\pi(x)\) sobre los valores complementarios de tipo \(\lfloor N/i\rfloor\) que aparecen en la recursión. Después enumera todas las partes pesadas admisibles formadas por potencias primas \(p^e\) con \(e\ge 2\), llevando a la vez el valor numérico de esa parte y su contribución multiplicativa a \(b(n)\).
Para cada parte pesada, la implementación prueba todos los objetivos \(2j\) hasta la cota requerida. Si el cociente restante es una potencia de \(2\), ya se sabe exactamente cuántos primos de exponente \(1\) faltan. Esas completaciones libres de cuadrados se cuentan recursivamente con primos crecientes, y el caso final de un solo primo se resuelve con la tabla de conteo de primos ya precalculada.
Al final se almacenan en caché los acumulados, se recuperan los \(Q_k(N)\) individuales por diferencia y se forma la suma pedida para \(k=2,\dots,10\).
Sea \(R=\lfloor\sqrt N\rfloor\). La criba de primos y la tabla de conteo de primos usan \(O(R)\) memoria y tiempo cercano a \(O(R\log\log R)\). La búsqueda sobre las partes pesadas es mucho menor que un barrido completo de factorizaciones, porque cada nuevo primo pesado cuesta al menos un factor cuadrático y cada nuevo exponente pesado multiplica el factor de divisores bi-unitarios por al menos \(2\).
En este problema, la recursión de completación libre de cuadrados es especialmente poco profunda: como \(2k\le 20\), el cociente potencia de dos restante es como máximo \(16\), así que nunca hay que añadir más de cuatro primos de exponente \(1\). En la práctica, el tiempo está dominado por el preprocesamiento de primos y por un número moderado de consultas a \(\pi(x)\), mientras que la memoria permanece en \(O(\sqrt N)\).
对正整数 \(n\)，记 \(b(n)\) 为 \(n\) 的 bi-unitary 因子个数。所有 bi-unitary 因子的乘积可写成 \(n^{b(n)/2}\)，因此
$$Q_k(N)=\#\{1\le n\le N : b(n)=2k\}$$
恰好统计那些 bi-unitary 因子乘积等于 \(n^k\) 的整数。题目要求计算
$$\sum_{k=2}^{10} Q_k(10^{12}).$$
显然不可能把 \(1\) 到 \(10^{12}\) 的所有整数逐个分解再判断，所以真正可行的方法是直接研究素因子分解中的指数结构，只枚举那些可能产生 \(2k\in\{4,6,\dots,20\}\) 的模式。
把 \(n\) 写成素因子分解
$$n=\prod_{i=1}^r p_i^{e_i}.$$
核心事实是：\(b(n)\) 只取决于指数 \(e_i\)，而与具体是哪些素数无关。实现正是利用了这一点，先决定指数形状，再统计能落在上界 \(N\) 之内的素数选择。
对 \(p^e\) 来说，普通因子是 \(1,p,p^2,\dots,p^e\)。在 bi-unitary 的情形下，若 \(e\) 为偶数，则正中间那个因子 \(p^{e/2}\) 不被计入；除此以外其余都保留。因此
$$b(p^e)= \begin{cases} e, & e \text{ 为偶数},\\ e+1, & e \text{ 为奇数}, \end{cases}$$
也就是
$$b(p^e)=e+(e\bmod 2).$$
不同素数幂的选择彼此独立，所以 \(b(n)\) 对素数幂因子是乘法性的：
$$b(n)=\prod_{i=1}^r \bigl(e_i+(e_i\bmod 2)\bigr).$$
这一步把问题从“数本身”彻底转成了“指数组合”。
把指数至少为 \(2\) 的素数与指数恰好为 \(1\) 的素数分开写：
$$n=\left(\prod_{i=1}^s p_i^{e_i}\right)\left(\prod_{j=1}^t q_j\right),\qquad e_i\ge 2,$$
其中 \(q_j\) 两两不同，并且不与任何 \(p_i\) 重合。于是
$$b(n)=\left(\prod_{i=1}^s \bigl(e_i+(e_i\bmod 2)\bigr)\right)2^t.$$
把前面的乘积记作 \(c\)。这样一来，重指数部分一旦确定，剩下的不确定性只在于还要附加多少个指数为 \(1\) 的素数，也就是 \(t\)。若目标是 \(b(n)=2k\)，就必须满足
$$2k=c\,2^t.$$
所以 \(2k/c\) 必须是 \(2\) 的幂。如果这个商不是 \(2\) 的幂，那么当前这组重指数根本不可能贡献到 \(Q_k(N)\)。
每增加一个重素数，\(n\) 的数值至少要乘上一个平方因子 \(p^2\)，因此数值会很快变大。同时，每个重指数对 \(b(n)\) 的贡献至少是 \(2\)，所以 bi-unitary 因子个数也会迅速增长。
由于本题最大的目标只是 \(2k=20\)，可行的 \(c\) 值其实很少。实现因此对所有 \(e\ge 2\) 的素数幂做深度优先搜索，一边维护当前重指数部分的数值，一边维护它对 \(b(n)\) 的乘法贡献 \(c\)。只要出现下面任一情况，就立刻停止向下扩展：
$$\text{重指数部分}>N$$
或者当前的 \(c\) 已经不可能整除任何 \(2\le k\le 10\) 的目标值 \(2k\)。
这就是程序能把搜索空间压得很小的原因。
固定一个重指数部分
$$a=\prod_{i=1}^s p_i^{e_i}$$
并假设 \(2k=c\,2^t\)。那么所有对应的整数都可写成
$$n=a\,q_1q_2\cdots q_t,$$
其中
$$q_1<q_2<\cdots<q_t,\qquad q_j\notin\{p_1,\dots,p_s\},$$
并满足乘积约束
$$a\,q_1q_2\cdots q_t\le N.$$
当 \(t=0\) 时，不需要再附加任何素数，重指数部分本身就是一个合法整数。当 \(t=1\) 时，只需要统计不在重指数集合中的素数 \(q\le N/a\)。当 \(t\ge 2\) 时，就递归选择下一个更大的素数，并同步缩小剩余乘积上界。
这里最关键的优化是 \(t=1\) 的基例：程序并不会把所有候选素数逐个扫描，而是直接查询素数计数函数 \(\pi(x)\)。为了让这种查询足够快，它预先在如下标准参数集合上构造了 \(\pi(x)\) 表：
$$x\in\{1,2,\dots,\lfloor\sqrt N\rfloor\}\cup\left\{\left\lfloor\frac{N}{i}\right\rfloor:1\le i\le \lfloor\sqrt N\rfloor\right\}.$$
这样，最后一个素数的计数就能在常数时间内完成。
与其对每个 \(k\) 都重新做一遍完整搜索，不如先计算累计函数
$$C(k)=\sum_{j=2}^k Q_j(N).$$
同一棵重指数搜索树往往会同时对多个目标 \(2j\) 有贡献，因此先求 \(C(k)\) 可以把这些公共工作复用起来。随后再通过
$$Q_k(N)=C(k)-C(k-1)$$
把精确的单项计数恢复出来。由于这里的目标范围很小，这种做法特别划算。
这里目标条件是 \(b(n)=4\)。按重指数贡献 \(c\) 分类即可。
若 \(c=1\)，则 \(t=2\)，所以 \(n=pq\)，其中 \(p,q\) 是不同素数且 \(pq\le 100\)。这就是平方自由半素数，一共有 \(30\) 个。
若 \(c=2\)，则 \(t=1\)。重指数部分想得到贡献 \(2\)，唯一可能是 \(p^2\)。因此我们要数形如 \(p^2q\) 的整数，其中 \(p\ne q\) 都是素数，且 \(p^2q\le 100\)。按 \(p\) 分组后得到
$$8+4+2+1=15,$$
分别对应 \(p=2,3,5,7\)。
若 \(c=4\)，则 \(t=0\)，说明重指数部分本身就必须满足 \(b(n)=4\)。可能的形状只有
$$p^3,\qquad p^4,\qquad p^2q^2.$$
在 \(100\) 以内，这三类分别贡献 \(2\)、\(2\)、\(2\) 个，一共 \(6\) 个。
因此
$$Q_2(100)=30+15+6=51,$$
正好与实现中的校验结果一致。
C++、Python 和 Java 实现遵循完全相同的数论思路。完整的组合计数逻辑位于 C++ 与 Java 实现中；Python 版本只是调用编译后的实现，因此三种语言对外呈现的算法行为是一致的。
程序首先生成大约到 \(2\sqrt N\) 为止的所有素数，并在递归需要的那些互补整除值上构造快速的 \(\pi(x)\) 查询表。随后，它枚举所有由 \(p^e\)（其中 \(e\ge 2\)）组成的合法重指数部分，同时携带这个部分的数值以及它对 \(b(n)\) 的乘法贡献。
对每一个重指数部分，程序都会检查所有需要的目标 \(2j\)。如果剩余商是 \(2\) 的幂，就说明还需要补上确切数量的指数为 \(1\) 的素数。这样的平方自由补全通过递归、按素数递增顺序完成；最后只差一个素数时，则利用预处理好的素数计数表，而不是显式枚举。
最后，程序缓存累计值，用差分得到单独的 \(Q_k(N)\)，再把 \(k=2,\dots,10\) 的结果相加得到最终答案。
设 \(R=\lfloor\sqrt N\rfloor\)。素数筛和素数计数表都需要 \(O(R)\) 内存，时间大致为 \(O(R\log\log R)\)。重指数部分的搜索远小于“对所有整数逐个分解”的做法，因为每多加入一个重素数，数值至少要乘上一个平方因子，而每多增加一个重指数，对 bi-unitary 因子个数的贡献至少再乘 \(2\)。
对本题而言，平方自由补全的递归深度特别小：由于 \(2k\le 20\)，剩余的 \(2\) 的幂最多只有 \(16\)，所以最多只需要再补四个指数为 \(1\) 的素数。实际运行时间主要消耗在素数预处理和数量不多的 \(\pi(x)\) 查询上，而总内存仍保持在 \(O(\sqrt N)\) 量级。
Для положительного целого \(n\) обозначим через \(b(n)\) число bi-unitary делителей числа \(n\). Произведение всех bi-unitary делителей имеет вид \(n^{b(n)/2}\), поэтому
$$Q_k(N)=\#\{1\le n\le N : b(n)=2k\}$$
считает в точности те числа, для которых произведение всех bi-unitary делителей равно \(n^k\). Требуется вычислить
$$\sum_{k=2}^{10} Q_k(10^{12}).$$
Перебирать все числа до \(10^{12}\) невозможно, поэтому решение работает напрямую с показателями в разложении на простые множители и перебирает только те шаблоны показателей, которые могут дать маленькие цели \(2k\in\{4,6,\dots,20\}\).
Пусть
$$n=\prod_{i=1}^r p_i^{e_i}.$$
Главный факт состоит в том, что \(b(n)\) зависит только от показателей \(e_i\), а не от конкретных простых чисел. Именно на этом и строится вся оптимизация.
Для \(p^e\) обычные делители имеют вид \(1,p,p^2,\dots,p^e\). В bi-unitary случае сохраняются все, кроме среднего делителя \(p^{e/2}\), когда \(e\) чётно. Поэтому
$$b(p^e)= \begin{cases} e, & e \text{ чётно},\\ e+1, & e \text{ нечётно}, \end{cases}$$
или, что то же самое,
$$b(p^e)=e+(e\bmod 2).$$
Поскольку разные простые степени работают независимо, функция \(b(n)\) мультипликативна по этим множителям:
$$b(n)=\prod_{i=1}^r \bigl(e_i+(e_i\bmod 2)\bigr).$$
Выделим простые с показателем не меньше \(2\) и простые, входящие ровно в первой степени:
$$n=\left(\prod_{i=1}^s p_i^{e_i}\right)\left(\prod_{j=1}^t q_j\right),\qquad e_i\ge 2,$$
где числа \(q_j\) попарно различны и не совпадают ни с одним из \(p_i\). Тогда
$$b(n)=\left(\prod_{i=1}^s \bigl(e_i+(e_i\bmod 2)\bigr)\right)2^t.$$
Обозначим первый множитель через \(c\). Как только тяжёлая часть зафиксирована, вся оставшаяся свобода сводится к числу \(t\) простых с показателем \(1\). Чтобы получить \(b(n)=2k\), необходимо
$$2k=c\,2^t.$$
Следовательно, отношение \(2k/c\) должно быть степенью двойки. Если это не так, выбранная тяжёлая часть не может дать вклад в \(Q_k(N)\).
Каждый тяжёлый простой множитель добавляет в \(n\) как минимум фактор \(p^2\), поэтому численное значение произведения растёт очень быстро. Одновременно каждый тяжёлый показатель даёт вклад не меньше \(2\) в значение \(b(n)\), так что и число bi-unitary делителей быстро выходит за пределы нужных целей.
Поскольку максимальная цель здесь равна всего лишь \(2k=20\), допустимые значения \(c\) очень малы. Поэтому реализация делает поиск в глубину по простым степеням \(p^e\) с \(e\ge 2\), накапливает и численное значение тяжёлой части, и её вклад в \(c\), и немедленно обрезает ветку, как только выполняется одно из условий:
$$\text{тяжёлая часть}>N$$
или текущее значение \(c\) уже не может делить ни одну цель \(2k\) при \(2\le k\le 10\).
Зафиксируем тяжёлую часть
$$a=\prod_{i=1}^s p_i^{e_i}$$
и предположим, что \(2k=c\,2^t\). Тогда любое подходящее число имеет вид
$$n=a\,q_1q_2\cdots q_t,$$
где
$$q_1<q_2<\cdots<q_t,\qquad q_j\notin\{p_1,\dots,p_s\},$$
и выполняется ограничение
$$a\,q_1q_2\cdots q_t\le N.$$
Если \(t=0\), то сама тяжёлая часть уже даёт одно решение. Если \(t=1\), нужно просто посчитать простые \(q\le N/a\), исключив те простые, которые уже использованы в тяжёлой части. Если \(t\ge 2\), реализация рекурсивно выбирает следующий больший простой и обновляет оставшуюся границу для произведения.
Ключевое ускорение находится в базовом случае \(t=1\): вместо перебора простых по одному алгоритм сразу обращается к функции подсчёта простых \(\pi(x)\). Чтобы такие запросы были быстрыми, \(\pi(x)\) заранее строится на стандартном множестве аргументов
$$x\in\{1,2,\dots,\lfloor\sqrt N\rfloor\}\cup\left\{\left\lfloor\frac{N}{i}\right\rfloor:1\le i\le \lfloor\sqrt N\rfloor\right\}.$$
Вместо того чтобы заново запускать весь поиск для каждого \(k\), реализация сначала вычисляет накопленную функцию
$$C(k)=\sum_{j=2}^k Q_j(N).$$
Одна и та же ветвь тяжёлой части может давать вклад сразу в несколько целей \(2j\), поэтому выгодно использовать это общее дерево поиска при построении \(C(k)\). После этого точное значение восстанавливается как
$$Q_k(N)=C(k)-C(k-1).$$
В данной задаче это особенно полезно, потому что все цели малы и сильно перекрываются.
Здесь целевое условие равно \(b(n)=4\). Разобьём случаи по тяжёлому множителю \(c\).
Если \(c=1\), то \(t=2\), значит \(n=pq\), где \(p\) и \(q\) — разные простые и \(pq\le 100\). Это квадратсвободные полупростые числа; их \(30\).
Если \(c=2\), то \(t=1\). Единственный тяжёлый вклад, дающий \(2\), это \(p^2\). Значит, считаются числа вида \(p^2q\), где \(p\ne q\) — простые и \(p^2q\le 100\). Если сгруппировать по \(p\), получаем
$$8+4+2+1=15,$$
что соответствует \(p=2,3,5,7\).
Если \(c=4\), то \(t=0\), то есть сама тяжёлая часть уже должна удовлетворять \(b(n)=4\). Возможные формы здесь таковы:
$$p^3,\qquad p^4,\qquad p^2q^2.$$
При ограничении \(100\) эти три типа дают соответственно \(2\), \(2\) и \(2\) случая, всего \(6\).
Следовательно,
$$Q_2(100)=30+15+6=51,$$
что совпадает с контрольным значением, используемым реализацией.
Реализации на C++, Python и Java используют одну и ту же теоретико-числовую схему. Полный комбинаторный поиск находится в версиях на C++ и Java; версия на Python вызывает скомпилированную реализацию, поэтому с точки зрения результата алгоритм одинаков во всех трёх языках.
Сначала программа генерирует все простые числа примерно до \(2\sqrt N\) и строит быструю таблицу значений \(\pi(x)\) на дополнительных целочисленных аргументах вида \(\lfloor N/i\rfloor\), которые нужны рекурсии. Затем перечисляются все допустимые тяжёлые части, состоящие из простых степеней \(p^e\) с \(e\ge 2\); при этом одновременно отслеживаются и численное значение этой части, и её мультипликативный вклад в \(b(n)\).
Для каждой тяжёлой части реализация проверяет все нужные цели \(2j\). Если оставшийся множитель является степенью двойки, то сразу известно, сколько простых с показателем \(1\) ещё нужно добавить. Эти квадратсвободные дополнения считаются рекурсивно по возрастающим простым, а финальный случай с одним простым обрабатывается через заранее подготовленную таблицу подсчёта простых, без явного перебора.
В конце накопленные значения кешируются, отдельные \(Q_k(N)\) получаются вычитанием, и затем формируется требуемая сумма по \(k=2,\dots,10\).
Пусть \(R=\lfloor\sqrt N\rfloor\). Решето простых и таблица подсчёта простых требуют \(O(R)\) памяти и времени порядка \(O(R\log\log R)\). Поиск по тяжёлым частям намного меньше, чем полный перебор факторизаций, поскольку каждый новый тяжёлый простой даёт как минимум квадратный множитель, а каждый новый тяжёлый показатель увеличивает bi-unitary-фактор как минимум вдвое.
В этой задаче рекурсия для квадратсвободного дополнения особенно неглубока: так как \(2k\le 20\), оставшаяся степень двойки не превосходит \(16\), то есть никогда не нужно добавлять более четырёх простых с показателем \(1\). На практике время работы определяется в основном предварительной обработкой простых и умеренным числом запросов к \(\pi(x)\), а память остаётся \(O(\sqrt N)\).
لكل عدد صحيح موجب \(n\)، نرمز بـ \(b(n)\) إلى عدد القواسم bi-unitary للعدد \(n\). حاصل ضرب جميع هذه القواسم يساوي \(n^{b(n)/2}\)، ولذلك فإن
$$Q_k(N)=\#\{1\le n\le N : b(n)=2k\}$$
يعد بالضبط الأعداد التي يكون فيها حاصل ضرب القواسم bi-unitary مساويًا لـ \(n^k\). المطلوب هو حساب
$$\sum_{k=2}^{10} Q_k(10^{12}).$$
من المستحيل عمليًا فحص جميع الأعداد حتى \(10^{12}\) واحدًا واحدًا، لذلك تعتمد الفكرة على تحليل أسس العوامل الأولية مباشرة، وحصر أنماط الأسس القادرة أصلًا على إنتاج القيم الصغيرة \(2k\in\{4,6,\dots,20\}\).
لنكتب تحليل \(n\) إلى عوامل أولية على الصورة
$$n=\prod_{i=1}^r p_i^{e_i}.$$
الملاحظة الأساسية هي أن \(b(n)\) يعتمد فقط على الأسس \(e_i\)، لا على هوية الأعداد الأولية نفسها. ومن هنا تأتي كل قوة الاختصار في الحل.
بالنسبة إلى \(p^e\)، فإن القواسم العادية هي \(1,p,p^2,\dots,p^e\). في الحالة bi-unitary تبقى كل هذه القواسم ما عدا القاسم الأوسط \(p^{e/2}\) عندما يكون \(e\) زوجيًا. إذن
$$b(p^e)= \begin{cases} e, & e \equiv 0 \pmod 2,\\ e+1, & e \equiv 1 \pmod 2, \end{cases}$$
وبشكل مكافئ
$$b(p^e)=e+(e\bmod 2).$$
وبما أن مساهمات القوى الأولية المختلفة مستقلة، فإن \(b(n)\) دالة ضربية بالنسبة إلى هذه العوامل:
$$b(n)=\prod_{i=1}^r \bigl(e_i+(e_i\bmod 2)\bigr).$$
نفصل الأعداد الأولية ذات الأس الأكبر أو المساوي لـ \(2\) عن الأعداد الأولية التي تظهر مرة واحدة فقط:
$$n=\left(\prod_{i=1}^s p_i^{e_i}\right)\left(\prod_{j=1}^t q_j\right),\qquad e_i\ge 2,$$
حيث إن \(q_j\) أعداد أولية متميزة ولا يساوي أي منها أحد \(p_i\). عندئذ
$$b(n)=\left(\prod_{i=1}^s \bigl(e_i+(e_i\bmod 2)\bigr)\right)2^t.$$
لنسَمِّ العامل الأول \(c\). بعد تثبيت الجزء الثقيل، لا يبقى سوى عدد العوامل الأولية ذات الأس \(1\)، أي \(t\). ولكي يتحقق الشرط \(b(n)=2k\) يجب أن يكون
$$2k=c\,2^t.$$
إذًا لا بد أن يكون الكسر \(2k/c\) قوة للعدد \(2\). وإذا لم يكن كذلك، فالجزء الثقيل المختار لا يمكن أن يساهم أبدًا في \(Q_k(N)\).
كل عدد أولي ثقيل يضيف إلى \(n\) عاملًا لا يقل عن \(p^2\)، لذلك ينمو حاصل الضرب العددي بسرعة كبيرة. وفي الوقت نفسه، كل أس ثقيل يضيف إلى \(b(n)\) عاملًا لا يقل عن \(2\)، لذلك يكبر عدد القواسم bi-unitary بسرعة أيضًا.
وبما أن أكبر هدف هنا هو فقط \(2k=20\)، فإن القيم الممكنة لـ \(c\) قليلة جدًا. ولهذا تنفذ الخوارزمية بحثًا عمقيًا على القوى الأولية \(p^e\) مع \(e\ge 2\)، وتحدِّث في كل خطوة قيمة الجزء الثقيل وقيمته الضربية داخل \(c\)، ثم تقطع الفرع فورًا إذا تحقق أحد الشرطين:
$$\prod_{i=1}^s p_i^{e_i}>N$$
أو أصبحت القيمة الحالية لـ \(c\) غير قادرة على قسمة أي هدف \(2k\) مع \(2\le k\le 10\).
لنثبت جزءًا ثقيلًا
$$a=\prod_{i=1}^s p_i^{e_i}$$
ولنفترض أن \(2k=c\,2^t\). عندئذ يكون كل عدد مناسب على الصورة
$$n=a\,q_1q_2\cdots q_t,$$
حيث
$$q_1<q_2<\cdots<q_t,\qquad q_j\notin\{p_1,\dots,p_s\},$$
ومع القيد
$$a\,q_1q_2\cdots q_t\le N.$$
إذا كان \(t=0\)، فالجزء الثقيل نفسه يعطي حلًا واحدًا. وإذا كان \(t=1\)، فيكفي عدّ الأعداد الأولية \(q\le N/a\) مع استبعاد تلك التي استُخدمت في الجزء الثقيل. أما إذا كان \(t\ge 2\)، فتختار الخوارزمية الأعداد الأولية تصاعديًا بشكل عودي مع تحديث الحد المتبقي بعد كل اختيار.
أهم تسريع يظهر في حالة الأساس \(t=1\): فبدل المرور على الأعداد الأولية واحدًا واحدًا، تستعلم الخوارزمية مباشرة من دالة عدّ الأعداد الأولية \(\pi(x)\). ولجعل هذه الاستعلامات سريعة، تُبنى القيم مسبقًا على المجموعة القياسية
$$x\in\{1,2,\dots,\lfloor\sqrt N\rfloor\}\cup\left\{\left\lfloor\frac{N}{i}\right\rfloor:1\le i\le \lfloor\sqrt N\rfloor\right\}.$$
بدل إعادة بناء البحث كاملًا لكل قيمة \(k\)، تحسب الخوارزمية أولًا الكمية التراكمية
$$C(k)=\sum_{j=2}^k Q_j(N).$$
ذلك لأن الشجرة نفسها الخاصة بالجزء الثقيل قد تسهم في عدة أهداف \(2j\) في آن واحد. وبعد الحصول على \(C(k)\)، نستعيد القيمة الدقيقة بواسطة
$$Q_k(N)=C(k)-C(k-1).$$
وهذا مفيد جدًا هنا لأن الأهداف صغيرة ومتداخلة بشكل كبير.
هنا الشرط المطلوب هو \(b(n)=4\). نقسم الحالات بحسب العامل الثقيل \(c\).
إذا كان \(c=1\)، فلدينا \(t=2\)، ومن ثم \(n=pq\) حيث \(p\) و\(q\) أوليان مختلفان و\(pq\le 100\). هذه هي الأعداد نصف الأولية الخالية من المربعات، وعددها \(30\).
إذا كان \(c=2\)، فلدينا \(t=1\). والطريقة الوحيدة للحصول على \(c=2\) من الجزء الثقيل هي الشكل \(p^2\). لذا نعد الأعداد من الصورة \(p^2q\) حيث \(p\ne q\) أوليان و\(p^2q\le 100\). وعند التجميع حسب \(p\) نحصل على
$$8+4+2+1=15,$$
وهي الحالات القادمة من \(p=2,3,5,7\).
إذا كان \(c=4\)، فلدينا \(t=0\)، أي إن الجزء الثقيل وحده يجب أن يحقق \(b(n)=4\). الأشكال الممكنة هي
$$p^3,\qquad p^4,\qquad p^2q^2.$$
تحت الحد \(100\) تعطي هذه الأنماط \(2\) و\(2\) و\(2\) حالة على الترتيب، أي ما مجموعه \(6\).
ومن ثم
$$Q_2(100)=30+15+6=51,$$
وهو نفس مقدار التحقق المستخدم داخل التنفيذ.
تنفذ إصدارات C++ وPython وJava الفكرة العددية نفسها. النسختان C++ وJava تحتويان على البحث التوافقي الكامل، أما نسخة Python فتستدعي التنفيذ المترجم، لذلك يكون السلوك الخوارزمي الظاهر واحدًا في اللغات الثلاث.
تبدأ الخوارزمية بتوليد جميع الأعداد الأولية حتى نحو \(2\sqrt N\)، ثم تبني جدولًا سريعًا لقيم \(\pi(x)\) على القيم التكميلية من الشكل \(\lfloor N/i\rfloor\) التي تظهر داخل العودية. بعد ذلك تُعدِّد كل الأجزاء الثقيلة الصالحة المؤلفة من قوى أولية \(p^e\) حيث \(e\ge 2\)، مع تتبع القيمة العددية لهذه الأجزاء ومساهمتها الضربية في \(b(n)\) في الوقت نفسه.
وبالنسبة إلى كل جزء ثقيل، يختبر التنفيذ جميع الأهداف \(2j\) حتى الحد المطلوب. فإذا كان الجزء المتبقي قوة للعدد \(2\)، أصبح معلومًا بالضبط كم عدد الأعداد الأولية ذات الأس \(1\) التي يجب إلحاقها. تُحسب هذه الإكمالات الخالية من المربعات عوديًا بترتيب تصاعدي، أما حالة العدد الأولي الأخير فتُعالج باستعمال جدول عدّ الأعداد الأولية المسبق بدل التكرار الصريح.
وفي النهاية تُخزَّن القيم التراكمية، وتُسترجع قيم \(Q_k(N)\) الفردية بالطرح، ثم تُجمع النتائج من \(k=2\) إلى \(10\).
لنكتب \(R=\lfloor\sqrt N\rfloor\). يستخدم منخل الأعداد الأولية وجدول عدّ الأعداد الأولية معًا ذاكرة \(O(R)\) وزمنًا قريبًا من \(O(R\log\log R)\). أما البحث في الأجزاء الثقيلة فهو أصغر بكثير من مسح شامل لجميع التحليلات الأولية، لأن كل عدد أولي ثقيل جديد يضيف على الأقل عاملًا تربيعيًا، وكل أس ثقيل جديد يضاعف عامل القواسم bi-unitary على الأقل.
وفي هذه المسألة تحديدًا تكون عودية الإكمال الخالي من المربعات سطحية جدًا: بما أن \(2k\le 20\)، فإن القوة الثنائية المتبقية لا تتجاوز \(16\)، وبالتالي لا نحتاج أبدًا إلى أكثر من أربعة أعداد أولية ذات أس \(1\). عمليًا، يهيمن على زمن التنفيذ التحضير الأولي للأعداد الأولية وعدد محدود من استعلامات \(\pi(x)\)، بينما يبقى استهلاك الذاكرة في حدود \(O(\sqrt N)\).