For each nonnegative integer \(k\), let \(S(k)\) be the sum of all positive integers whose prime factors, counted with multiplicity, add up to \(k\). If
$$n=\prod_{p} p^{a_p},$$
then \(n\) contributes to \(S(k)\) exactly when
$$\sum_{p} a_p p = k,$$
where only finitely many exponents \(a_p\) are nonzero. Its contribution is the number itself, namely
$$n=\prod_{p} p^{a_p}.$$
The task is to evaluate
$$\sum_{i=2}^{24} S(F_i)\pmod{10^9},$$
with Fibonacci numbers defined by \(F_1=F_2=1\). The largest required argument is \(F_{24}=46368\), so one precomputation up to that bound is enough.
The three implementations all exploit the same idea: instead of enumerating integers directly, they compute the coefficients of a generating function whose coefficient of \(x^k\) is exactly \(S(k)\).
Every positive integer has a unique prime factorization, so \(S(k)\) can be written as
$$S(k)=\sum_{\substack{a_p\ge 0\\ \sum_p a_p p = k}} \prod_p p^{a_p}.$$
Each choice of exponents \((a_p)\) corresponds to one integer, and the weighted sum condition \(\sum_p a_p p = k\) says that each copy of the prime \(p\) contributes \(p\) units to the target total. The product \(\prod_p p^{a_p}\) is the value of the integer produced by that prime multiset.
Fix a prime \(p\). If it is used \(r\) times, then it contributes
$$p^r x^{rp}=(p x^p)^r$$
to the generating series: \(x^{rp}\) records that the prime-factor sum increases by \(rp\), and \(p^r\) records the multiplicative value contributed by those \(r\) copies of \(p\). Summing over all \(r\ge 0\) gives a geometric series:
$$\sum_{r\ge 0}(p x^p)^r=\frac{1}{1-px^p}.$$
Taking the product over all primes yields
$$G(x)=\sum_{k\ge 0} S(k)x^k=\prod_{p}\frac{1}{1-px^p}.$$
The constant term is \(1\), which corresponds to choosing no primes at all. This gives the convenient base value \(S(0)=1\); the requested values all have positive index, so this is only a bookkeeping device.
Assume we already know the coefficients of the partial product over some set of primes, and denote the current coefficient of \(x^t\) by \(A(t)\). When a new prime \(q\) is introduced, the series is multiplied by
$$1+q x^q+q^2 x^{2q}+q^3 x^{3q}+\cdots.$$
Therefore the updated coefficient is
$$A_{\text{new}}(t)=\sum_{r\ge 0} q^r A_{\text{old}}(t-rq).$$
This can be implemented in place by scanning \(t\) upward and applying
$$A(t)\leftarrow A(t)+q\,A(t-q)\pmod{10^9}\qquad (t\ge q).$$
That single formula is enough to reproduce the whole geometric series for the prime \(q\).
When the degrees are processed in increasing order, the entry at \(t-q\) has already been updated for the current prime. So it already includes the cases with zero, one, two, and more copies of \(q\). Multiplying by \(q\) and adding into degree \(t\) appends one extra copy of the same prime.
Because each prime is introduced only once, the method counts multisets of prime factors, not ordered sequences. That matches the number-theoretic definition exactly: \(2\cdot 3\cdot 3\) is one integer, not three different arrangements.
To compute \(S(8)\), only primes up to \(8\) matter, so we may truncate the product at degree \(8\):
$$G(x)=\frac{1}{(1-2x^2)(1-3x^3)(1-5x^5)(1-7x^7)}+O(x^9).$$
The coefficient of \(x^8\) comes from exactly three choices:
$$ (2x^2)^4,\qquad (2x^2)(3x^3)^2,\qquad (3x^3)(5x^5). $$
These correspond to the integers
$$16,\qquad 18,\qquad 15,$$
so
$$S(8)=16+18+15=49.$$
Likewise, the degree \(5\) terms are \(5x^5\) and \((2x^2)(3x^3)\), giving
$$S(5)=5+6=11.$$
Both values agree with the checkpoints used by the implementation.
Once all coefficients up to \(F_{24}\) have been computed, the problem is finished: we just read off the values at Fibonacci indices and add them:
$$\text{Answer}=\sum_{i=2}^{24} S(F_i)\pmod{10^9}.$$
No separate recomputation is needed for each \(F_i\). The same coefficient table serves every target value at once.
The C++, Python, and Java implementations follow the same pipeline. First they generate the Fibonacci numbers up to \(F_{24}\), then they take \(46368\) as the global bound because that is the largest prime-factor sum that will ever be queried.
Next they generate every prime up to that bound with a sieve. After that they allocate one coefficient table of length \(46369\), set the degree-\(0\) entry to \(1\), and leave every other entry at \(0\).
For each prime, the implementation sweeps the table from low degree to high degree and applies the recurrence from the previous section modulo \(10^9\). When the sweep is complete, the entry at index \(k\) is the value of \(S(k)\) modulo \(10^9\).
Finally the implementation adds the entries at indices \(F_2,F_3,\dots,F_{24}\), reduces the total modulo \(10^9\), and prints the result as a 9-digit value with leading zeros if necessary.
Let \(B=F_{24}=46368\). The sieve step takes \(O(B\log\log B)\) time and \(O(B)\) memory. The coefficient update then processes every prime \(q\le B\) across all degrees \(q,q+1,\dots,B\), so its running time is \(O(B\,\pi(B))\), where \(\pi(B)\) is the number of primes up to \(B\). The memory usage remains \(O(B)\) because only one sieve structure and one coefficient table are stored.
Für jede nichtnegative ganze Zahl \(k\) sei \(S(k)\) die Summe aller positiven ganzen Zahlen, deren Primfaktoren mit Vielfachheit addiert genau \(k\) ergeben. Gilt
$$n=\prod_{p} p^{a_p},$$
dann trägt \(n\) genau dann zu \(S(k)\) bei, wenn
$$\sum_{p} a_p p = k,$$
wobei nur endlich viele Exponenten \(a_p\) ungleich \(0\) sind. Der Beitrag ist die Zahl selbst, also
$$n=\prod_{p} p^{a_p}.$$
Gesucht ist
$$\sum_{i=2}^{24} S(F_i)\pmod{10^9},$$
wobei \(F_1=F_2=1\) die Fibonacci-Zahlen sind. Da der größte benötigte Index \(F_{24}=46368\) ist, reicht eine einzige Vorberechnung bis zu dieser Schranke.
Alle drei Implementierungen benutzen dieselbe Grundidee: Statt die gesuchten Zahlen direkt zu erzeugen, bestimmen sie die Koeffizienten einer erzeugenden Funktion, deren Koeffizient von \(x^k\) genau \(S(k)\) ist.
Wegen der eindeutigen Primfaktorzerlegung kann man \(S(k)\) so schreiben:
$$S(k)=\sum_{\substack{a_p\ge 0\\ \sum_p a_p p = k}} \prod_p p^{a_p}.$$
Jede Exponentenwahl \((a_p)\) beschreibt genau eine ganze Zahl. Die Bedingung \(\sum_p a_p p=k\) bedeutet, dass jede Kopie der Primzahl \(p\) genau \(p\) Einheiten zur Primfaktor-Summe beiträgt. Das Produkt \(\prod_p p^{a_p}\) ist der Zahlenwert, der aus diesem Primzahl-Multiset entsteht.
Fixiere eine Primzahl \(p\). Wird sie \(r\)-mal verwendet, dann ist ihr Beitrag zur Reihe
$$p^r x^{rp}=(p x^p)^r.$$
Der Exponent \(rp\) bei \(x\) speichert die Primfaktor-Summe, der Faktor \(p^r\) speichert den multiplikativen Zahlenwert. Summiert man über alle \(r\ge 0\), erhält man eine geometrische Reihe:
$$\sum_{r\ge 0}(p x^p)^r=\frac{1}{1-px^p}.$$
Über alle Primzahlen multipliziert ergibt das
$$G(x)=\sum_{k\ge 0} S(k)x^k=\prod_{p}\frac{1}{1-px^p}.$$
Der konstante Term ist \(1\) und entspricht der leeren Auswahl von Primzahlen. Damit erhält man den praktischen Startwert \(S(0)=1\); für die eigentliche Aufgabenstellung ist das nur ein technischer Anker.
Angenommen, die Koeffizienten des bisherigen Teilprodukts sind bekannt, und \(A(t)\) bezeichnet den aktuellen Koeffizienten von \(x^t\). Fügt man eine neue Primzahl \(q\) hinzu, wird mit
$$1+q x^q+q^2 x^{2q}+q^3 x^{3q}+\cdots$$
multipliziert. Also gilt
$$A_{\text{neu}}(t)=\sum_{r\ge 0} q^r A_{\text{alt}}(t-rq).$$
Das lässt sich in place umsetzen, indem man \(t\) aufsteigend durchläuft und
$$A(t)\leftarrow A(t)+q\,A(t-q)\pmod{10^9}\qquad (t\ge q)$$
anwendet. Diese eine Aktualisierung reproduziert bereits die gesamte geometrische Reihe der Primzahl \(q\).
Wird \(t\) aufsteigend verarbeitet, dann ist der Eintrag bei \(t-q\) für die aktuelle Primzahl schon aktualisiert worden. Dort stecken also bereits die Fälle mit null, einer, zwei oder mehr Kopien von \(q\). Durch Multiplikation mit \(q\) und Addition zu Grad \(t\) hängt man genau eine weitere Kopie derselben Primzahl an.
Da jede Primzahl nur einmal eingeführt wird, zählt das Verfahren Primzahl-Multisets und nicht geordnete Folgen. Genau das verlangt die Zahlentheorie hinter der Aufgabe: \(2\cdot 3\cdot 3\) ist eine Zahl und nicht drei verschiedene Anordnungen.
Für \(S(8)\) sind nur Primzahlen bis \(8\) relevant. Bis Grad \(8\) darf man also schreiben
$$G(x)=\frac{1}{(1-2x^2)(1-3x^3)(1-5x^5)(1-7x^7)}+O(x^9).$$
Der Koeffizient von \(x^8\) entsteht genau aus drei Möglichkeiten:
$$ (2x^2)^4,\qquad (2x^2)(3x^3)^2,\qquad (3x^3)(5x^5). $$
Sie entsprechen den Zahlen
$$16,\qquad 18,\qquad 15,$$
also
$$S(8)=16+18+15=49.$$
Für Grad \(5\) erhält man analog die Terme \(5x^5\) und \((2x^2)(3x^3)\), also
$$S(5)=5+6=11.$$
Beide Werte stimmen mit den Kontrollpunkten der Implementierung überein.
Sobald alle Koeffizienten bis \(F_{24}\) berechnet sind, ist die Aufgabe praktisch gelöst. Man liest nur noch die Werte an den Fibonacci-Positionen aus und addiert sie:
$$\text{Antwort}=\sum_{i=2}^{24} S(F_i)\pmod{10^9}.$$
Für jedes \(F_i\) ist also keine neue Rechnung nötig; dieselbe Koeffiziententabelle liefert alle gesuchten Werte.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst erzeugen sie die Fibonacci-Zahlen bis \(F_{24}\), dann nehmen sie \(46368\) als globale Obergrenze, weil keine größere Primfaktor-Summe abgefragt wird.
Danach bestimmen sie mit einem Sieb alle Primzahlen bis zu dieser Grenze. Anschließend legen sie eine eindimensionale Koeffiziententabelle der Länge \(46369\) an, setzen den Eintrag zu Grad \(0\) auf \(1\) und lassen alle übrigen Einträge bei \(0\).
Für jede Primzahl wird die Tabelle von kleinen zu großen Graden durchlaufen, und dabei wird die Rekurrenz aus dem mathematischen Teil jeweils modulo \(10^9\) angewendet. Nach Abschluss dieses Durchlaufs enthält der Eintrag an Position \(k\) genau den Wert \(S(k)\) modulo \(10^9\).
Am Ende addiert die Implementierung die Einträge an den Positionen \(F_2,F_3,\dots,F_{24}\), reduziert erneut modulo \(10^9\) und gibt den Wert bei Bedarf mit führenden Nullen auf 9 Stellen formatiert aus.
Sei \(B=F_{24}=46368\). Das Sieb benötigt \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Danach verarbeitet die Koeffizientenaktualisierung jede Primzahl \(q\le B\) über alle Grade \(q,q+1,\dots,B\), also insgesamt \(O(B\,\pi(B))\) Zeit, wobei \(\pi(B)\) die Anzahl der Primzahlen bis \(B\) bezeichnet. Der Speicherverbrauch bleibt \(O(B)\), weil nur eine Siebstruktur und eine Koeffiziententabelle gehalten werden.
Her negatif olmayan \(k\) tamsayısı için \(S(k)\), asal çarpanları tekrarlarıyla birlikte toplandığında \(k\) eden tüm pozitif tamsayıların toplamı olsun. Eğer
$$n=\prod_{p} p^{a_p},$$
ise \(n\) sayısı ancak şu durumda \(S(k)\)'ye katkı verir:
$$\sum_{p} a_p p = k,$$
ve burada yalnızca sonlu sayıda \(a_p\) değeri sıfırdan farklıdır. Katkı değeri sayının kendisidir:
$$n=\prod_{p} p^{a_p}.$$
İstenen değer
$$\sum_{i=2}^{24} S(F_i)\pmod{10^9}$$
ifadesidir; burada \(F_1=F_2=1\) Fibonacci sayılarıdır. Gereken en büyük argüman \(F_{24}=46368\) olduğundan, bu sınıra kadar tek bir ön hesaplama yeterlidir.
Üç uygulama da aynı temel fikri kullanır: Sayıları tek tek üretmek yerine, \(x^k\) katsayısı tam olarak \(S(k)\) olan bir üreteç fonksiyonunun katsayılarını hesaplarlar.
Asal çarpanlara ayırmanın tekilliği sayesinde \(S(k)\) şu şekilde yazılabilir:
$$S(k)=\sum_{\substack{a_p\ge 0\\ \sum_p a_p p = k}} \prod_p p^{a_p}.$$
Her üs seçimi \((a_p)\) tam olarak bir pozitif tamsayıya karşılık gelir. \(\sum_p a_p p = k\) koşulu, asal \(p\)'nin her bir kopyasının hedef toplama \(p\) kadar katkı verdiğini söyler. \(\prod_p p^{a_p}\) çarpımı da bu asal çoklu kümesinin ürettiği sayının kendisidir.
Bir asal \(p\)'yi sabitleyelim. Bu asal \(r\) kez kullanılırsa seriye katkısı
$$p^r x^{rp}=(p x^p)^r$$
olur. Burada \(x^{rp}\) terimi asal çarpan toplamının \(rp\) arttığını, \(p^r\) katsayısı ise çarpımsal değerin ne kadar büyüdüğünü kaydeder. Tüm \(r\ge 0\) değerleri toplanınca bir geometrik seri elde edilir:
$$\sum_{r\ge 0}(p x^p)^r=\frac{1}{1-px^p}.$$
Tüm asallar üzerinden çarpınca
$$G(x)=\sum_{k\ge 0} S(k)x^k=\prod_{p}\frac{1}{1-px^p}$$
eşitliği çıkar. Sabit terim \(1\)'dir; bu, hiç asal seçmemeye karşılık gelir. Böylece pratik başlangıç değeri olarak \(S(0)=1\) kullanılır; istenen cevaplar için bu sadece teknik bir taban durumudur.
Diyelim ki belirli bir asal kümesi için kısmi çarpımın katsayıları biliniyor ve \(x^t\)'nin mevcut katsayısına \(A(t)\) diyelim. Yeni bir asal \(q\) eklendiğinde seri
$$1+q x^q+q^2 x^{2q}+q^3 x^{3q}+\cdots$$
ile çarpılır. Dolayısıyla güncellenmiş katsayı
$$A_{\text{yeni}}(t)=\sum_{r\ge 0} q^r A_{\text{eski}}(t-rq)$$
olur. Bu, \(t\) değeri küçükten büyüğe gezilerek yerinde şu güncelleme ile uygulanabilir:
$$A(t)\leftarrow A(t)+q\,A(t-q)\pmod{10^9}\qquad (t\ge q).$$
Bu tek formül, \(q\) asalı için gerekli sonsuz geometrik serinin tamamını üretir.
\(t\) değerleri artan sırada işlendiğinde, \(t-q\) konumundaki katsayı aynı asal için zaten güncellenmiş olur. Yani orada \(q\)'nun sıfır, bir, iki veya daha fazla kez kullanılabildiği tüm durumlar bulunur. Onu \(q\) ile çarpıp derece \(t\)'ye eklemek, aynı asaldan bir kopya daha eklemek demektir.
Her asal yalnızca bir kez sisteme sokulduğu için yöntem sıralı dizileri değil, asal çarpan çoklu kümelerini sayar. Bu da problem tanımıyla tam uyumludur: \(2\cdot 3\cdot 3\) tek bir sayıdır, farklı sıralamalar halinde tekrar sayılmaz.
\(S(8)\) için yalnızca \(8\)'e kadar olan asallar önemlidir. Bu yüzden derece \(8\)'e kadar ürün
$$G(x)=\frac{1}{(1-2x^2)(1-3x^3)(1-5x^5)(1-7x^7)}+O(x^9)$$
şeklinde kesilebilir. \(x^8\) katsayısı yalnızca şu üç seçimden gelir:
$$ (2x^2)^4,\qquad (2x^2)(3x^3)^2,\qquad (3x^3)(5x^5). $$
Bunların karşılık geldiği sayılar
$$16,\qquad 18,\qquad 15$$
olduğundan
$$S(8)=16+18+15=49$$
elde edilir. Benzer biçimde derece \(5\) için \(5x^5\) ve \((2x^2)(3x^3)\) terimleri vardır; dolayısıyla
$$S(5)=5+6=11.$$
Bu iki değer, uygulamadaki kontrol sonuçlarıyla aynıdır.
\(F_{24}\)'e kadar tüm katsayılar hesaplandıktan sonra geriye sadece Fibonacci indislerindeki değerleri okumak kalır:
$$\text{Cevap}=\sum_{i=2}^{24} S(F_i)\pmod{10^9}.$$
Her \(F_i\) için ayrı hesap yapılmaz; aynı katsayı tablosu bütün hedefleri bir kerede sağlar.
C++, Python ve Java uygulamaları aynı akışı izler. Önce Fibonacci sayıları \(F_{24}\)'e kadar üretilir; sonra sorgulanacak en büyük asal çarpan toplamı bu olduğu için üst sınır \(46368\) alınır.
Daha sonra bu sınıra kadar tüm asallar bir elek yöntemiyle bulunur. Ardından uzunluğu \(46369\) olan tek boyutlu bir katsayı tablosu ayrılır; derece \(0\) için başlangıç değeri \(1\) yapılır ve diğer tüm girişler \(0\) kalır.
Her asal için tablo düşük dereceden yüksek dereceye doğru taranır ve önceki bölümdeki bağıntı her adımda \(10^9\) modunda uygulanır. Tarama tamamlandığında \(k\) konumundaki değer tam olarak \(S(k)\)'nin \(10^9\) modundaki halidir.
Son aşamada \(F_2,F_3,\dots,F_{24}\) indislerindeki girişler toplanır, toplam tekrar \(10^9\) modunda azaltılır ve gerekiyorsa başına sıfır eklenerek 9 basamaklı biçimde yazdırılır.
\(B=F_{24}=46368\) olsun. Elek aşaması \(O(B\log\log B)\) zaman ve \(O(B)\) bellek kullanır. Katsayı güncellemesi ise her \(q\le B\) asalı için \(q,q+1,\dots,B\) derecelerini gezer; dolayısıyla çalışma süresi \(O(B\,\pi(B))\) olur. Burada \(\pi(B)\), \(B\)'ye kadar olan asal sayısıdır. Toplam bellek kullanımı \(O(B)\) seviyesinde kalır; çünkü yalnızca bir elek yapısı ve bir katsayı tablosu tutulur.
Para cada entero no negativo \(k\), definimos \(S(k)\) como la suma de todos los enteros positivos cuyos factores primos, contados con multiplicidad, suman \(k\). Si
$$n=\prod_{p} p^{a_p},$$
entonces \(n\) contribuye a \(S(k)\) exactamente cuando
$$\sum_{p} a_p p = k,$$
donde solo un número finito de exponentes \(a_p\) es distinto de \(0\). Su contribución es el propio número:
$$n=\prod_{p} p^{a_p}.$$
La tarea es calcular
$$\sum_{i=2}^{24} S(F_i)\pmod{10^9},$$
donde \(F_1=F_2=1\) son los números de Fibonacci. Como el mayor argumento necesario es \(F_{24}=46368\), basta una sola precomputación hasta ese límite.
Las tres implementaciones parten de la misma idea: en lugar de enumerar directamente los enteros válidos, calculan los coeficientes de una función generadora cuyo coeficiente de \(x^k\) es exactamente \(S(k)\).
Por la unicidad de la factorización prima, \(S(k)\) puede escribirse como
$$S(k)=\sum_{\substack{a_p\ge 0\\ \sum_p a_p p = k}} \prod_p p^{a_p}.$$
Cada elección de exponentes \((a_p)\) describe un único entero positivo. La restricción \(\sum_p a_p p=k\) indica que cada copia del primo \(p\) aporta \(p\) unidades a la suma pedida. El producto \(\prod_p p^{a_p}\) es el valor del entero construido a partir de ese multiconjunto de primos.
Fijemos un primo \(p\). Si aparece \(r\) veces, su contribución a la serie es
$$p^r x^{rp}=(p x^p)^r.$$
La potencia \(x^{rp}\) registra que la suma de factores primos aumenta en \(rp\), y el coeficiente \(p^r\) registra el valor multiplicativo aportado por esas \(r\) copias. Al sumar sobre todos los \(r\ge 0\) obtenemos una serie geométrica:
$$\sum_{r\ge 0}(p x^p)^r=\frac{1}{1-px^p}.$$
Multiplicando sobre todos los primos resulta
$$G(x)=\sum_{k\ge 0} S(k)x^k=\prod_{p}\frac{1}{1-px^p}.$$
El término constante vale \(1\) y representa la elección vacía de primos. Eso fija el caso base conveniente \(S(0)=1\); los valores pedidos empiezan en índices positivos, así que aquí solo sirve como punto de arranque combinatorio.
Supongamos que ya conocemos los coeficientes del producto parcial para cierto conjunto de primos y llamemos \(A(t)\) al coeficiente actual de \(x^t\). Al incorporar un nuevo primo \(q\), la serie se multiplica por
$$1+q x^q+q^2 x^{2q}+q^3 x^{3q}+\cdots.$$
Por lo tanto, el coeficiente actualizado satisface
$$A_{\text{nuevo}}(t)=\sum_{r\ge 0} q^r A_{\text{anterior}}(t-rq).$$
Esto puede implementarse in situ recorriendo \(t\) en orden creciente y aplicando
$$A(t)\leftarrow A(t)+q\,A(t-q)\pmod{10^9}\qquad (t\ge q).$$
Esa sola actualización reproduce toda la serie geométrica asociada al primo \(q\).
Cuando los grados se procesan en orden creciente, la entrada en \(t-q\) ya fue actualizada para el primo actual. Por eso ya contiene los casos con cero, una, dos o más copias de \(q\). Multiplicar por \(q\) y sumar al grado \(t\) equivale a añadir una copia adicional del mismo primo.
Como cada primo se introduce una sola vez, el método cuenta multiconjuntos de factores primos y no secuencias ordenadas. Eso coincide exactamente con la definición aritmética: \(2\cdot 3\cdot 3\) es un solo entero, no varias permutaciones distintas.
Para calcular \(S(8)\), solo importan los primos menores o iguales que \(8\). Por tanto, hasta grado \(8\) podemos truncar el producto como
$$G(x)=\frac{1}{(1-2x^2)(1-3x^3)(1-5x^5)(1-7x^7)}+O(x^9).$$
El coeficiente de \(x^8\) procede exactamente de tres elecciones:
$$ (2x^2)^4,\qquad (2x^2)(3x^3)^2,\qquad (3x^3)(5x^5). $$
Estas corresponden a los enteros
$$16,\qquad 18,\qquad 15,$$
así que
$$S(8)=16+18+15=49.$$
De manera similar, en grado \(5\) aparecen \(5x^5\) y \((2x^2)(3x^3)\), de modo que
$$S(5)=5+6=11.$$
Ambos valores coinciden con los puntos de control usados por la implementación.
Una vez calculados todos los coeficientes hasta \(F_{24}\), el problema queda resuelto: basta leer los valores en los índices de Fibonacci y sumarlos:
$$\text{Respuesta}=\sum_{i=2}^{24} S(F_i)\pmod{10^9}.$$
No hace falta recomputar nada para cada \(F_i\); la misma tabla de coeficientes sirve para todos los objetivos.
Las implementaciones en C++, Python y Java siguen exactamente la misma secuencia. Primero generan los números de Fibonacci hasta \(F_{24}\) y toman \(46368\) como cota global, porque esa es la mayor suma de factores primos que se necesita consultar.
Después generan todos los primos hasta ese límite mediante un tamiz. A continuación reservan una tabla unidimensional de coeficientes de longitud \(46369\), ponen el valor \(1\) en el grado \(0\) y dejan el resto en \(0\).
Para cada primo, la implementación recorre la tabla desde grados pequeños hasta grados grandes y aplica la recurrencia de la sección anterior módulo \(10^9\). Cuando termina ese proceso, la entrada de índice \(k\) contiene el valor \(S(k)\) módulo \(10^9\).
Por último se suman las entradas en los índices \(F_2,F_3,\dots,F_{24}\), se reduce el total módulo \(10^9\) y se imprime como un valor de 9 cifras, añadiendo ceros iniciales si hace falta.
Sea \(B=F_{24}=46368\). El tamiz cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. Luego, la actualización de coeficientes procesa cada primo \(q\le B\) sobre todos los grados \(q,q+1,\dots,B\), lo que da \(O(B\,\pi(B))\) tiempo, donde \(\pi(B)\) es el número de primos hasta \(B\). El consumo de memoria sigue siendo \(O(B)\), porque solo se almacenan la estructura del tamiz y una tabla de coeficientes.
对每个非负整数 \(k\)，定义 \(S(k)\) 为所有满足“质因数之和等于 \(k\)”的正整数之和，这里的质因数要按重数计算。如果
$$n=\prod_{p} p^{a_p},$$
那么 \(n\) 恰好在下面这个条件成立时计入 \(S(k)\)：
$$\sum_{p} a_p p = k,$$
其中只有有限多个指数 \(a_p\) 不为 \(0\)。它对总和的贡献就是这个整数本身，也就是
$$n=\prod_{p} p^{a_p}.$$
题目要求计算
$$\sum_{i=2}^{24} S(F_i)\pmod{10^9},$$
其中 Fibonacci 数列满足 \(F_1=F_2=1\)。因为真正会被查询到的最大参数是 \(F_{24}=46368\)，所以只要把所有 \(S(k)\) 预处理到这个上界即可。
三种实现的核心思想完全一致：不直接枚举满足条件的整数，而是构造一个生成函数，使得 \(x^k\) 的系数恰好等于 \(S(k)\)，然后用动态规划逐项提取这些系数。
由于正整数的质因数分解唯一，\(S(k)\) 可以写成
$$S(k)=\sum_{\substack{a_p\ge 0\\ \sum_p a_p p = k}} \prod_p p^{a_p}.$$
这里每一组指数 \((a_p)\) 都对应唯一的一个正整数。条件 \(\sum_p a_p p=k\) 表示：每出现一次质数 \(p\)，就向“质因数和”贡献 \(p\)；而乘积 \(\prod_p p^{a_p}\) 则是这个质数多重集合对应的整数值。
这样一来，问题就从“找整数”变成了“统计满足加权和条件的指数选择，并把对应的乘积加起来”。
先固定一个质数 \(p\)。如果它被使用了 \(r\) 次，那么对生成函数的贡献就是
$$p^r x^{rp}=(p x^p)^r.$$
其中 \(x^{rp}\) 用来记录质因数和增加了 \(rp\)，而前面的系数 \(p^r\) 用来记录这些质数在乘积中的实际数值贡献。对所有 \(r\ge 0\) 求和，就得到一个几何级数：
$$\sum_{r\ge 0}(p x^p)^r=\frac{1}{1-px^p}.$$
再把所有质数的贡献相乘，就有
$$G(x)=\sum_{k\ge 0} S(k)x^k=\prod_{p}\frac{1}{1-px^p}.$$
这个乘积的常数项是 \(1\)，代表“一个质数都不选”的空选择，因此自然给出基值 \(S(0)=1\)。题目真正要用的是正整数位置上的值，所以这个常数项只是为了让递推起步更方便。
假设某一时刻我们已经处理完一部分质数，并把当前级数中 \(x^t\) 的系数记为 \(A(t)\)。现在加入一个新的质数 \(q\)，等价于把级数再乘上
$$1+q x^q+q^2 x^{2q}+q^3 x^{3q}+\cdots.$$
因此更新后的系数满足
$$A_{\text{new}}(t)=\sum_{r\ge 0} q^r A_{\text{old}}(t-rq).$$
这个式子可以通过一维数组原地完成。只要把 \(t\) 从小到大扫描，并执行
$$A(t)\leftarrow A(t)+q\,A(t-q)\pmod{10^9}\qquad (t\ge q),$$
就能把质数 \(q\) 的全部幂次贡献一次性并入系数表中。
关键点在于：当处理到位置 \(t\) 时，位置 \(t-q\) 已经针对当前质数 \(q\) 完成了更新。也就是说，\(A(t-q)\) 里面已经包含了使用 \(0\) 次、\(1\) 次、\(2\) 次，乃至更多次 \(q\) 的所有情况。
于是把它乘上一个 \(q\) 再加到 \(A(t)\) 里，恰好表示“在原有方案后面再补上一枚质数 \(q\)”。这样不断向前推进，就自动实现了同一个质数可以无限次使用的效果。
同时，每个质数只会被引入一次，所以算法统计的是质因数的多重集合，而不是排列顺序。比如 \(2\cdot 3\cdot 3\) 只代表一个整数，不会因为因子的顺序不同而被重复计算。
计算 \(S(8)\) 时，只需要考虑不超过 \(8\) 的质数，所以在 \(8\) 次项以内可以把生成函数截断成
$$G(x)=\frac{1}{(1-2x^2)(1-3x^3)(1-5x^5)(1-7x^7)}+O(x^9).$$
\(x^8\) 的系数只来自三种选法：
$$ (2x^2)^4,\qquad (2x^2)(3x^3)^2,\qquad (3x^3)(5x^5). $$
它们分别对应整数
$$16,\qquad 18,\qquad 15,$$
所以
$$S(8)=16+18+15=49.$$
同理，\(x^5\) 的来源只有 \(5x^5\) 与 \((2x^2)(3x^3)\)，因此
$$S(5)=5+6=11.$$
这两个数值都和实现中的校验点一致，说明生成函数与递推关系是正确的。
当所有 \(0\) 到 \(F_{24}\) 的系数都算出来后，题目实际上已经完成。我们只需要从表中取出 Fibonacci 下标对应的那些值并求和：
$$\text{Answer}=\sum_{i=2}^{24} S(F_i)\pmod{10^9}.$$
因此整道题的重心不是分别计算很多个 \(S(k)\)，而是一次性构造完整的系数表，然后在需要的位置读取结果。
C++、Python 和 Java 的实现流程完全相同。首先生成 Fibonacci 数列直到 \(F_{24}\)，并把 \(46368\) 作为全局上界，因为不会查询更大的质因数和。
接着用筛法求出所有不超过这个上界的质数。然后建立一个长度为 \(46369\) 的一维系数表，把 \(0\) 次项初始化为 \(1\)，其余位置全部初始化为 \(0\)。
之后对每个质数做一次从低下标到高下标的扫描，并在扫描过程中按上一节的递推式对系数取模 \(10^9\) 更新。所有质数处理完以后，表中下标 \(k\) 的值就是 \(S(k)\bmod 10^9\)。
最后，实现把 \(F_2,F_3,\dots,F_{24}\) 这些位置上的值累加，再对 \(10^9\) 取模，并按 9 位数字的形式输出；如果前面有缺位，就补前导零。
设 \(B=F_{24}=46368\)。筛法部分的时间复杂度是 \(O(B\log\log B)\)，空间复杂度是 \(O(B)\)。随后的一维系数更新会对每个质数 \(q\le B\) 扫描区间 \(q,q+1,\dots,B\)，因此总时间复杂度为 \(O(B\,\pi(B))\)，其中 \(\pi(B)\) 表示不超过 \(B\) 的质数个数。空间方面始终只需要一个筛结构和一个系数表，所以仍然是 \(O(B)\)。
Для каждого неотрицательного целого \(k\) обозначим через \(S(k)\) сумму всех положительных целых чисел, у которых сумма простых множителей с учетом кратности равна \(k\). Если
$$n=\prod_{p} p^{a_p},$$
то число \(n\) входит в \(S(k)\) ровно тогда, когда
$$\sum_{p} a_p p = k,$$
причем лишь конечное число показателей \(a_p\) отлично от нуля. Вкладом служит само число, то есть
$$n=\prod_{p} p^{a_p}.$$
Нужно вычислить
$$\sum_{i=2}^{24} S(F_i)\pmod{10^9},$$
где \(F_1=F_2=1\) — числа Фибоначчи. Поскольку максимальный нужный аргумент равен \(F_{24}=46368\), достаточно одного предварительного вычисления до этой границы.
Все три реализации используют одну и ту же идею: вместо прямого перебора чисел они вычисляют коэффициенты производящей функции, у которой коэффициент при \(x^k\) равен \(S(k)\).
Благодаря единственности разложения на простые множители можно записать
$$S(k)=\sum_{\substack{a_p\ge 0\\ \sum_p a_p p = k}} \prod_p p^{a_p}.$$
Каждый набор показателей \((a_p)\) задает ровно одно положительное целое число. Условие \(\sum_p a_p p=k\) означает, что каждая копия простого числа \(p\) добавляет \(p\) к сумме простых множителей, а произведение \(\prod_p p^{a_p}\) дает численное значение соответствующего целого.
Зафиксируем простое число \(p\). Если оно используется \(r\) раз, то его вклад в ряд равен
$$p^r x^{rp}=(p x^p)^r.$$
Степень \(x^{rp}\) хранит увеличение суммы простых множителей на \(rp\), а коэффициент \(p^r\) хранит мультипликативный вклад. Суммируя по всем \(r\ge 0\), получаем геометрический ряд:
$$\sum_{r\ge 0}(p x^p)^r=\frac{1}{1-px^p}.$$
Перемножая такие множители по всем простым, получаем
$$G(x)=\sum_{k\ge 0} S(k)x^k=\prod_{p}\frac{1}{1-px^p}.$$
Свободный член равен \(1\) и соответствует пустому выбору простых чисел. Это дает удобное базовое значение \(S(0)=1\); для самой задачи это лишь техническая отправная точка.
Пусть коэффициенты частичного произведения уже известны, и \(A(t)\) обозначает текущий коэффициент при \(x^t\). Если добавить новое простое число \(q\), нужно умножить ряд на
$$1+q x^q+q^2 x^{2q}+q^3 x^{3q}+\cdots.$$
Следовательно, обновленный коэффициент удовлетворяет формуле
$$A_{\text{new}}(t)=\sum_{r\ge 0} q^r A_{\text{old}}(t-rq).$$
Это можно выполнить на месте, проходя значения \(t\) по возрастанию и применяя
$$A(t)\leftarrow A(t)+q\,A(t-q)\pmod{10^9}\qquad (t\ge q).$$
Одной такой операции достаточно, чтобы восстановить весь геометрический вклад простого числа \(q\).
Если степени обрабатываются слева направо, то к моменту обновления позиции \(t\) значение в позиции \(t-q\) уже содержит все случаи с нулем, одной, двумя и большим числом копий простого \(q\). Умножение на \(q\) и перенос в степень \(t\) означает добавление еще одной копии того же простого.
Поскольку каждое простое число вводится в алгоритм только один раз, подсчитываются именно мультисеты простых множителей, а не упорядоченные последовательности. Это полностью совпадает с арифметическим смыслом задачи: \(2\cdot 3\cdot 3\) — одно число, а не несколько перестановок.
Для вычисления \(S(8)\) важны только простые числа, не превосходящие \(8\). Поэтому до степени \(8\) можно обрезать произведение так:
$$G(x)=\frac{1}{(1-2x^2)(1-3x^3)(1-5x^5)(1-7x^7)}+O(x^9).$$
Коэффициент при \(x^8\) возникает ровно из трех выборов:
$$ (2x^2)^4,\qquad (2x^2)(3x^3)^2,\qquad (3x^3)(5x^5). $$
Им соответствуют числа
$$16,\qquad 18,\qquad 15,$$
поэтому
$$S(8)=16+18+15=49.$$
Аналогично для степени \(5\) получаем слагаемые \(5x^5\) и \((2x^2)(3x^3)\), откуда
$$S(5)=5+6=11.$$
Обе проверки совпадают с контрольными значениями, заложенными в реализации.
После вычисления всех коэффициентов до \(F_{24}\) задача по сути решена. Остается только взять значения в позициях Фибоначчи и сложить их:
$$\text{Ответ}=\sum_{i=2}^{24} S(F_i)\pmod{10^9}.$$
Никаких отдельных пересчетов для каждого \(F_i\) не требуется: одна и та же таблица коэффициентов обслуживает все нужные индексы.
Реализации на C++, Python и Java выполняют один и тот же конвейер. Сначала они генерируют числа Фибоначчи до \(F_{24}\) и используют \(46368\) как общую верхнюю границу, потому что более крупная сумма простых множителей нигде не понадобится.
Затем при помощи решета находятся все простые числа до этой границы. После этого создается одномерная таблица коэффициентов длины \(46369\): значение при степени \(0\) инициализируется единицей, а все остальные значения — нулями.
Для каждого простого числа реализация проходит таблицу от меньших степеней к большим и применяет рекуррентное обновление из предыдущего раздела по модулю \(10^9\). После обработки всех простых значение в позиции \(k\) равно \(S(k)\bmod 10^9\).
В финале программа суммирует элементы в позициях \(F_2,F_3,\dots,F_{24}\), снова берет остаток по модулю \(10^9\) и выводит результат в виде 9-значной строки, добавляя ведущие нули при необходимости.
Пусть \(B=F_{24}=46368\). Решето работает за \(O(B\log\log B)\) времени и требует \(O(B)\) памяти. Затем обновление коэффициентов для каждого простого \(q\le B\) проходит по всем степеням \(q,q+1,\dots,B\), поэтому общая трудоемкость этого этапа равна \(O(B\,\pi(B))\), где \(\pi(B)\) — число простых, не превосходящих \(B\). Память остается \(O(B)\), так как одновременно хранятся только структура решета и одна таблица коэффициентов.
لكل عدد صحيح غير سالب \(k\)، نعرّف \(S(k)\) بأنه مجموع كل الأعداد الصحيحة الموجبة التي يكون مجموع عواملها الأولية، مع احتساب التكرار، مساويًا لـ \(k\). إذا كان
$$n=\prod_{p} p^{a_p},$$
فإن العدد \(n\) يساهم في \(S(k)\) إذا وفقط إذا تحقق الشرط
$$\sum_{p} a_p p = k,$$
مع ملاحظة أن عددًا محدودًا فقط من الأسس \(a_p\) يكون غير صفري. وقيمة مساهمته هي العدد نفسه، أي
$$n=\prod_{p} p^{a_p}.$$
المطلوب هو حساب
$$\sum_{i=2}^{24} S(F_i)\pmod{10^9},$$
حيث \(F_1=F_2=1\) هما بدايتا متتالية فيبوناتشي. وبما أن أكبر قيمة مطلوبة هي \(F_{24}=46368\)، فإن تجهيزًا واحدًا حتى هذا الحد يكفي لحل المسألة كاملة.
تعتمد التطبيقات الثلاثة على الفكرة نفسها: بدل تعداد الأعداد الممكنة مباشرة، نحسب معاملات دالة مولدة يكون معامل \(x^k\) فيها مساويًا تمامًا لـ \(S(k)\).
بفضل فرادة التحليل إلى عوامل أولية، يمكن كتابة \(S(k)\) بالشكل
$$S(k)=\sum_{\substack{a_p\ge 0\\ \sum_p a_p p = k}} \prod_p p^{a_p}.$$
كل اختيار للأسس \((a_p)\) يحدد عددًا صحيحًا موجبًا واحدًا فقط. والشرط \(\sum_p a_p p = k\) يعني أن كل نسخة من العدد الأولي \(p\) تضيف مقدار \(p\) إلى مجموع العوامل الأولية. أما الضرب \(\prod_p p^{a_p}\) فهو القيمة الفعلية للعدد الناتج عن هذا المتعدد من العوامل الأولية.
لنثبت عددًا أوليًا \(p\). إذا استُخدم هذا الأولي \(r\) مرات، فإن مساهمته في السلسلة تكون
$$p^r x^{rp}=(p x^p)^r.$$
القوة \(x^{rp}\) تسجل أن مجموع العوامل الأولية ازداد بمقدار \(rp\)، بينما المعامل \(p^r\) يسجل الأثر الضربي لتكرار هذا الأولي \(r\) مرات. بجمع جميع القيم \(r\ge 0\) نحصل على متسلسلة هندسية:
$$\sum_{r\ge 0}(p x^p)^r=\frac{1}{1-px^p}.$$
ثم بأخذ حاصل الضرب على جميع الأعداد الأولية نحصل على
$$G(x)=\sum_{k\ge 0} S(k)x^k=\prod_{p}\frac{1}{1-px^p}.$$
الحد الثابت يساوي \(1\)، وهو يمثل اختيارًا فارغًا لا يحتوي على أي عدد أولي. لذلك نحصل طبيعيًا على قيمة البداية \(S(0)=1\)، وهي مجرد نقطة انطلاق حسابية لأن القيم المطلوبة في المسألة تقع عند مؤشرات موجبة.
افترض أننا نعرف معاملات حاصل الضرب الجزئي الحالي، ولنرمز إلى معامل \(x^t\) بالرمز \(A(t)\). عند إدخال عدد أولي جديد \(q\)، فإننا نضرب السلسلة في
$$1+q x^q+q^2 x^{2q}+q^3 x^{3q}+\cdots.$$
وبالتالي فإن المعامل الجديد يحقق
$$A_{\text{new}}(t)=\sum_{r\ge 0} q^r A_{\text{old}}(t-rq).$$
يمكن تنفيذ ذلك في المكان نفسه إذا مررنا على القيم \(t\) تصاعديًا وطبقنا التحديث
$$A(t)\leftarrow A(t)+q\,A(t-q)\pmod{10^9}\qquad (t\ge q).$$
هذا التحديث الواحد يكفي لإدخال جميع قوى العدد الأولي \(q\) كما تفرضها المتسلسلة الهندسية.
عندما نعالج الدرجات بترتيب تصاعدي، تكون الخانة عند \(t-q\) قد حُدِّثت بالفعل بالنسبة إلى الأولي الحالي \(q\). وهذا يعني أنها تحتوي سلفًا على الحالات التي تستخدم \(q\) صفر مرة أو مرة واحدة أو مرتين أو أكثر.
لذلك فإن ضربها في \(q\) ثم إضافتها إلى الدرجة \(t\) يعني ببساطة إضافة نسخة جديدة من الأولي نفسه. وهكذا يتحقق السماح باستعمال الأولي الواحد عددًا غير محدود من المرات.
ولأن كل عدد أولي يدخل إلى العملية مرة واحدة فقط، فإن ما يتم عده هو متعددات العوامل الأولية، لا الترتيبات المختلفة لها. وهذا يطابق تعريف المسألة تمامًا: العدد \(2\cdot 3\cdot 3\) يمثل عددًا واحدًا، وليس عدة ترتيبات منفصلة.
لحساب \(S(8)\)، لا نحتاج إلا إلى الأعداد الأولية التي لا تتجاوز \(8\). لذلك يمكن قطع الدالة المولدة حتى الدرجة \(8\) على الصورة
$$G(x)=\frac{1}{(1-2x^2)(1-3x^3)(1-5x^5)(1-7x^7)}+O(x^9).$$
معامل \(x^8\) يأتي من ثلاث اختيارات فقط:
$$ (2x^2)^4,\qquad (2x^2)(3x^3)^2,\qquad (3x^3)(5x^5). $$
وهذه تقابل الأعداد
$$16,\qquad 18,\qquad 15,$$
ومن ثم
$$S(8)=16+18+15=49.$$
وبالطريقة نفسها، تأتي درجة \(5\) من الحدين \(5x^5\) و\((2x^2)(3x^3)\)، وبالتالي
$$S(5)=5+6=11.$$
وهاتان القيمتان تتطابقان مع نقاط التحقق المستخدمة في التنفيذ.
بعد حساب جميع المعاملات حتى \(F_{24}\)، تنتهي الناحية الرياضية من المسألة. عندها نقرأ فقط القيم الواقعة عند مؤشرات فيبوناتشي ونجمعها:
$$\sum_{i=2}^{24} S(F_i)\pmod{10^9}.$$
لا حاجة إلى إعادة الحساب لكل \(F_i\) على حدة؛ فالجدول نفسه يخدم جميع القيم المطلوبة دفعة واحدة.
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولًا تُولَّد أعداد فيبوناتشي حتى \(F_{24}\)، ثم يُستخدم العدد \(46368\) كحد أعلى عام لأنه أكبر مجموع لعوامل أولية سيجري الاستعلام عنه.
بعد ذلك تُولَّد جميع الأعداد الأولية حتى هذا الحد باستخدام غربال. ثم يُنشأ جدول معاملات أحادي البعد طوله \(46369\)، وتُضبط خانة الدرجة \(0\) على القيمة \(1\)، بينما تبقى بقية الخانات صفرية.
لكل عدد أولي، ينفذ التطبيق مسحًا من الدرجات الصغيرة إلى الدرجات الكبيرة، ويطبق في كل خطوة علاقة التحديث السابقة بترديد \(10^9\). وبعد اكتمال معالجة جميع الأعداد الأولية، تصبح القيمة الموجودة في الموضع \(k\) مساوية لـ \(S(k)\bmod 10^9\).
في النهاية، يجمع التطبيق القيم الموجودة عند المواضع \(F_2,F_3,\dots,F_{24}\)، ثم يأخذ الباقي modulo \(10^9\)، ويطبع النتيجة في صورة عدد من 9 خانات مع إضافة أصفار بادئة إذا لزم الأمر.
لنضع \(B=F_{24}=46368\). خطوة الغربال تحتاج إلى زمن \(O(B\log\log B)\) وذاكرة \(O(B)\). بعد ذلك، تمر عملية تحديث المعاملات على كل عدد أولي \(q\le B\) وعلى جميع الدرجات من \(q\) حتى \(B\)، ولذلك يكون الزمن الكلي \(O(B\,\pi(B))\)، حيث \(\pi(B)\) هو عدد الأعداد الأولية التي لا تتجاوز \(B\). أما الذاكرة فتبقى \(O(B)\)، لأن التنفيذ لا يحتفظ إلا ببنية الغربال وجدول معاملات واحد.