For each positive integer \(n\), the problem assigns a weight \(A(n)\). The convention is \(A(1)=1\); for every prime \(p\), \(A(p)=1\); and for composite products the rule is Leibniz-like:
$$A(ab)=aA(b)+bA(a).$$
If \(\lambda=(\lambda_1,\dots,\lambda_k)\) is a partition of \(s\), its weight is the product of the part-weights:
$$w(\lambda)=\prod_{i=1}^{k} A(\lambda_i).$$
Let \(P(s)\) be the sum of these weights over all integer partitions of \(s\). The required result is the cumulative total
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{999676999}.$$
The published implementations evaluate this for \(N=50000\), so the main challenge is to compute every \(P(s)\) up to that bound without enumerating partitions explicitly.
The recurrence for \(A(n)\) is exactly the arithmetic-derivative rule on all \(n\ge 2\), with the extra convention \(A(1)=1\) so that parts equal to \(1\) contribute a neutral factor instead of killing the product.
Writing
$$n=\prod_{j=1}^{r} p_j^{\alpha_j},$$
the product rule gives the closed form
$$A(n)=\sum_{j=1}^{r}\alpha_j p_j^{\alpha_j-1}\prod_{\ell\ne j} p_\ell^{\alpha_\ell}=n\sum_{j=1}^{r}\frac{\alpha_j}{p_j}\qquad (n\ge 2).$$
Examples are immediate:
$$A(2)=1,\qquad A(4)=4,\qquad A(6)=6\left(\frac{1}{2}+\frac{1}{3}\right)=5,\qquad A(12)=12\left(\frac{2}{2}+\frac{1}{3}\right)=16.$$
This formula explains why the implementations can fill the entire weight table once the smallest prime factor of each number is known.
For each \(s\ge 0\), define
$$P(s)=\sum_{\lambda\vdash s} w(\lambda),\qquad P(0)=1,$$
where \(\lambda\vdash s\) means that \(\lambda\) is an integer partition of \(s\).
If a part size \(m\) appears \(c\) times, it contributes the factor \(A(m)^c x^{cm}\). Summing over all multiplicities \(c\ge 0\) gives a geometric series, so the ordinary generating function is
$$\sum_{s\ge 0} P(s)x^s=\prod_{m\ge 1}\left(1+A(m)x^m+A(m)^2x^{2m}+\cdots\right)=\prod_{m\ge 1}\frac{1}{1-A(m)x^m}.$$
This is the central structural observation: the problem is a weighted partition problem, not a search over factorizations or compositions.
Let \(P_m(s)\) denote the weighted partition total for \(s\) using only part sizes at most \(m\). Then
$$P_0(0)=1,\qquad P_0(s)=0\ \text{for}\ s>0,$$
and for each \(m\ge 1\) we split partitions into those that use no part \(m\) and those that use at least one part \(m\):
$$P_m(s)=P_{m-1}(s)+A(m)P_m(s-m)\qquad (s\ge m).$$
The term \(P_{m-1}(s)\) covers partitions that skip \(m\), while \(A(m)P_m(s-m)\) removes one copy of \(m\) from a partition that uses it. This is exactly the recurrence of an unbounded knapsack or complete-partition DP.
After processing all part sizes up to \(N\), the coefficient table contains \(P(0),P(1),\dots,P(N)\). The requested answer is then only a prefix sum:
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{M},\qquad M=999676999.$$
No separate combinatorial argument is needed at the end. Once the coefficients are known, the final accumulation is straightforward.
The needed part-weights are
$$A(1)=1,\qquad A(2)=1,\qquad A(3)=1,\qquad A(4)=4.$$
The partitions of \(4\) and their weights are
$$\begin{aligned} (4) &\longrightarrow 4,\\ (3+1) &\longrightarrow 1\cdot 1=1,\\ (2+2) &\longrightarrow 1\cdot 1=1,\\ (2+1+1) &\longrightarrow 1,\\ (1+1+1+1) &\longrightarrow 1. \end{aligned}$$
Therefore
$$P(4)=4+1+1+1+1=8.$$
Continuing the same process gives a useful checkpoint:
$$P(10)=164,\qquad \sum_{s=1}^{10} P(s)=396.$$
The C++, Python, and Java implementations first build a smallest-prime-factor table up to \(N\). That table makes the weight computation linear after the sieve: if \(x\) is prime then its weight is \(1\), and if \(x=pq\) with \(p\) the smallest prime factor, then the product rule gives \(A(x)=pA(q)+q\), where \(q<x\) has already been processed.
Next the implementation runs a one-dimensional complete-partition DP. Part sizes are processed in increasing order, and target sums are scanned upward from the current part size to \(N\). That update order is what allows unlimited reuse of the same part size while still counting each partition only once, independent of the ordering of its parts.
After the coefficient table has been filled, the implementation accumulates the prefix total from \(1\) through \(N\), reducing after every arithmetic step modulo \(999676999\). The Python version follows the same numerical method by delegating to the compiled solver, so all three language versions share the same mathematics.
Let \(N\) be the target bound. Building the smallest-prime-factor sieve costs \(O(N\log\log N)\) time and \(O(N)\) memory. Filling the weight sequence from that sieve is \(O(N)\). The dominant phase is the weighted partition DP, whose nested loops over part size and target sum require \(O(N^2)\) modular operations. The full method therefore runs in \(O(N^2)\) time and uses \(O(N)\) memory.
Zu jeder positiven ganzen Zahl \(n\) wird ein Gewicht \(A(n)\) definiert. Es gilt \(A(1)=1\), für jede Primzahl \(p\) gilt \(A(p)=1\), und für zusammengesetzte Produkte gilt eine Leibniz-artige Regel:
$$A(ab)=aA(b)+bA(a).$$
Ist \(\lambda=(\lambda_1,\dots,\lambda_k)\) eine Partition von \(s\), dann ist ihr Gewicht das Produkt der Teilgewichte:
$$w(\lambda)=\prod_{i=1}^{k} A(\lambda_i).$$
Sei \(P(s)\) die Summe dieser Gewichte über alle ganzzahligen Partitionen von \(s\). Gesucht ist die kumulative Summe
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{999676999}.$$
Die veröffentlichten Implementierungen werten dies für \(N=50000\) aus. Man muss also alle Werte \(P(s)\) bis zu dieser Grenze effizient berechnen, ohne Partitionen direkt zu enumerieren.
Die Rekursion für \(A(n)\) ist für alle \(n\ge 2\) genau die Regel der arithmetischen Ableitung; nur \(A(1)=1\) wird zusätzlich festgesetzt, damit Teile der Größe \(1\) einen neutralen Faktor liefern.
Schreibt man
$$n=\prod_{j=1}^{r} p_j^{\alpha_j},$$
dann folgt aus der Produktregel die geschlossene Form
$$A(n)=\sum_{j=1}^{r}\alpha_j p_j^{\alpha_j-1}\prod_{\ell\ne j} p_\ell^{\alpha_\ell}=n\sum_{j=1}^{r}\frac{\alpha_j}{p_j}\qquad (n\ge 2).$$
Ein paar Beispiele:
$$A(2)=1,\qquad A(4)=4,\qquad A(6)=6\left(\frac{1}{2}+\frac{1}{3}\right)=5,\qquad A(12)=12\left(\frac{2}{2}+\frac{1}{3}\right)=16.$$
Damit wird klar, warum die Implementierungen nach Kenntnis des kleinsten Primteilers alle Gewichte in einem Vorwärtsdurchlauf berechnen können.
Für \(s\ge 0\) definieren wir
$$P(s)=\sum_{\lambda\vdash s} w(\lambda),\qquad P(0)=1,$$
wobei \(\lambda\vdash s\) bedeutet, dass \(\lambda\) eine ganzzahlige Partition von \(s\) ist.
Kommt eine Teilgröße \(m\) genau \(c\)-mal vor, so trägt sie den Faktor \(A(m)^c x^{cm}\) bei. Über alle Multiplizitäten \(c\ge 0\) summiert ergibt das eine geometrische Reihe, also
$$\sum_{s\ge 0} P(s)x^s=\prod_{m\ge 1}\left(1+A(m)x^m+A(m)^2x^{2m}+\cdots\right)=\prod_{m\ge 1}\frac{1}{1-A(m)x^m}.$$
Das ist die entscheidende Struktur: Es handelt sich um ein Problem über gewichtete Partitionen, nicht um eine Suche über geordnete Zerlegungen.
Sei \(P_m(s)\) die gewichtete Partitionssumme von \(s\), wenn nur Teilgrößen bis \(m\) erlaubt sind. Dann gilt
$$P_0(0)=1,\qquad P_0(s)=0\ \text{für}\ s>0,$$
und für jedes \(m\ge 1\) zerfällt die Menge der Partitionen in solche ohne Teil \(m\) und solche mit mindestens einem Teil \(m\):
$$P_m(s)=P_{m-1}(s)+A(m)P_m(s-m)\qquad (s\ge m).$$
Der Term \(P_{m-1}(s)\) überspringt die Teilgröße \(m\), während \(A(m)P_m(s-m)\) genau ein Exemplar von \(m\) abtrennt. Das ist exakt die Rekurrenz eines unbeschränkten Knapsack- beziehungsweise Partitions-DP.
Nachdem alle Teilgrößen bis \(N\) verarbeitet wurden, enthält die Koeffiziententabelle \(P(0),P(1),\dots,P(N)\). Die eigentliche Ausgabe ist dann nur noch die Präfixsumme
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{M},\qquad M=999676999.$$
Es ist also kein zusätzlicher kombinatorischer Trick am Ende nötig: Sobald die Koeffizienten vorliegen, ist der Rest reine Akkumulation.
Die benötigten Teilgewichte sind
$$A(1)=1,\qquad A(2)=1,\qquad A(3)=1,\qquad A(4)=4.$$
Die Partitionen von \(4\) und ihre Gewichte lauten
$$\begin{aligned} (4) &\longrightarrow 4,\\ (3+1) &\longrightarrow 1\cdot 1=1,\\ (2+2) &\longrightarrow 1\cdot 1=1,\\ (2+1+1) &\longrightarrow 1,\\ (1+1+1+1) &\longrightarrow 1. \end{aligned}$$
Daher ist
$$P(4)=4+1+1+1+1=8.$$
Setzt man das Verfahren fort, erhält man einen nützlichen Kontrollwert:
$$P(10)=164,\qquad \sum_{s=1}^{10} P(s)=396.$$
Die C++-, Python- und Java-Implementierungen bauen zunächst eine Tabelle der kleinsten Primteiler bis \(N\) auf. Damit lässt sich die Gewichtsfunktion nach dem Sieb in linearer Zeit füllen: Ist \(x\) prim, so ist sein Gewicht \(1\); ist \(x=pq\) mit \(p\) als kleinstem Primteiler, dann liefert die Produktregel \(A(x)=pA(q)+q\), wobei \(q<x\) bereits berechnet wurde.
Anschließend verwendet die Implementierung ein eindimensionales DP für unbeschränkte Partitionen. Die Teilgrößen werden aufsteigend verarbeitet, und die Zielsumme wird jeweils von der aktuellen Teilgröße bis \(N\) nach oben durchlaufen. Genau diese Reihenfolge erlaubt die beliebige Wiederverwendung derselben Teilgröße und sorgt gleichzeitig dafür, dass Partitionen ohne Berücksichtigung der Reihenfolge ihrer Teile gezählt werden.
Zum Schluss wird die Präfixsumme von \(1\) bis \(N\) gebildet, wobei jeder Rechenschritt modulo \(999676999\) reduziert wird. Die Python-Version folgt demselben numerischen Weg, indem sie den kompilierten Löser aufruft, daher teilen alle drei Sprachversionen dieselbe Mathematik.
Sei \(N\) die Zielgrenze. Das Sieb für die kleinsten Primteiler benötigt \(O(N\log\log N)\) Zeit und \(O(N)\) Speicher. Das Auffüllen der Gewichtsfunktion aus dieser Tabelle kostet \(O(N)\). Die dominierende Phase ist das gewichtete Partitions-DP mit seinen zwei Schleifen über Teilgröße und Zielsumme; es benötigt \(O(N^2)\) modulare Operationen. Insgesamt läuft das Verfahren also in \(O(N^2)\) Zeit und verwendet \(O(N)\) Speicher.
Her pozitif tamsayi \(n\) icin bir agirlik \(A(n)\) tanimlaniyor. Kural olarak \(A(1)=1\), her asal \(p\) icin \(A(p)=1\) ve bilesik carpimlarda Leibniz benzeri su baginti kullaniliyor:
$$A(ab)=aA(b)+bA(a).$$
\(\lambda=(\lambda_1,\dots,\lambda_k)\) sayi toplami \(s\) olan bir partition ise, bu partition'un agirligi parca agirliklarinin carpimidir:
$$w(\lambda)=\prod_{i=1}^{k} A(\lambda_i).$$
\(P(s)\), \(s\)'nin tum partition'lari uzerindeki bu agirliklarin toplami olsun. Istenen deger
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{999676999}$$
seklindeki kumevi toplamdir. Yayinlanan cozumler bunu \(N=50000\) icin hesapladigi icin, butun \(P(s)\) degerlerini partition'lari tek tek uretmeden bulmak gerekir.
\(A(n)\) icin verilen rekursiyon, \(n\ge 2\) icin aritmetik turevin aynisidir; sadece \(A(1)=1\) ozel olarak secilir ki \(1\) parcalari carpima notr bir faktor katsin.
$$n=\prod_{j=1}^{r} p_j^{\alpha_j}$$
yazilirsa, carpim kurali su kapali formu verir:
$$A(n)=\sum_{j=1}^{r}\alpha_j p_j^{\alpha_j-1}\prod_{\ell\ne j} p_\ell^{\alpha_\ell}=n\sum_{j=1}^{r}\frac{\alpha_j}{p_j}\qquad (n\ge 2).$$
Birkac ornek:
$$A(2)=1,\qquad A(4)=4,\qquad A(6)=6\left(\frac{1}{2}+\frac{1}{3}\right)=5,\qquad A(12)=12\left(\frac{2}{2}+\frac{1}{3}\right)=16.$$
Bu form, en kucuk asal carpan tablosu kuruldugunda agirlik dizisinin neden tek geciste doldurulabildigini da aciklar.
\(s\ge 0\) icin
$$P(s)=\sum_{\lambda\vdash s} w(\lambda),\qquad P(0)=1$$
tanimini yapalim; burada \(\lambda\vdash s\), \(\lambda\)'nin \(s\)'nin bir partition'u oldugunu belirtir.
Bir parca boyu \(m\), partition icinde \(c\) kez geciyorsa katkisi \(A(m)^c x^{cm}\) olur. Tum \(c\ge 0\) degerleri toplaninca geometrik seri cikar ve su uretici fonksiyon elde edilir:
$$\sum_{s\ge 0} P(s)x^s=\prod_{m\ge 1}\left(1+A(m)x^m+A(m)^2x^{2m}+\cdots\right)=\prod_{m\ge 1}\frac{1}{1-A(m)x^m}.$$
Temel gozlem budur: problem bir partition agirliklandirma problemidir; sirali dizilimleri ya da carpansal agaclari tek tek saymak gerekmez.
\(P_m(s)\), sadece en fazla \(m\) buyuklugunde parcalara izin verildiginde \(s\) icin elde edilen agirlikli partition toplami olsun. O zaman
$$P_0(0)=1,\qquad P_0(s)=0\ \text{eger}\ s>0$$
ve her \(m\ge 1\) icin partition'lari ikiye ayiririz: \(m\) parcasini hic kullanmayanlar ve en az bir kez kullananlar.
$$P_m(s)=P_{m-1}(s)+A(m)P_m(s-m)\qquad (s\ge m).$$
\(P_{m-1}(s)\) terimi \(m\)'yi atlar. \(A(m)P_m(s-m)\) ise bir adet \(m\) cikarip kalan partition'u sayar. Bu tam olarak sinirsiz knapsack ya da complete-partition DP bagintisidir.
Tum parca boylari \(N\)'ye kadar islendiginde katsayi tablosu \(P(0),P(1),\dots,P(N)\) degerlerini icerir. Sorudaki son cevap sadece su on ek toplamdir:
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{M},\qquad M=999676999.$$
Yani son asamada baska bir kombinatorik donusume gerek yoktur; katsayilar hazir oldugunda geriye sadece birikimli toplama kalir.
Bu durumda gereken parca agirliklari
$$A(1)=1,\qquad A(2)=1,\qquad A(3)=1,\qquad A(4)=4$$
olur. \(4\)'un partition'lari ve agirliklari soyledir:
$$\begin{aligned} (4) &\longrightarrow 4,\\ (3+1) &\longrightarrow 1\cdot 1=1,\\ (2+2) &\longrightarrow 1\cdot 1=1,\\ (2+1+1) &\longrightarrow 1,\\ (1+1+1+1) &\longrightarrow 1. \end{aligned}$$
Dolayisiyla
$$P(4)=4+1+1+1+1=8.$$
Ayni surec biraz daha ilerletilirse yararli bir kontrol noktasi da elde edilir:
$$P(10)=164,\qquad \sum_{s=1}^{10} P(s)=396.$$
C++, Python ve Java uygulamalari once \(N\)'ye kadar en kucuk asal carpan tablosu kurar. Bu tablo sayesinde agirlik dizisi eleme sonrasinda lineer surede doldurulur: \(x\) asalsa agirligi \(1\)'dir; \(x=pq\) ve \(p\) en kucuk asal carpan ise carpim kurali \(A(x)=pA(q)+q\) verir ve \(q<x\) oldugu icin gerekli onceki deger zaten hesaplanmistir.
Daha sonra uygulama tek boyutlu bir complete-partition DP calistirir. Parca boylari artan sirayla islenir, hedef toplam ise her adimda o parca boyundan \(N\)'ye kadar yukari dogru taranir. Bu guncelleme sirasi ayni parcanin sinirsiz kez kullanilmasina izin verirken her partition'u parcalarinin sirasindan bagimsiz olarak tam bir kez sayar.
Son olarak \(1\) ile \(N\) arasindaki katsayilar birikimli toplanir ve her aritmetik adim \(999676999\) modunda tutulur. Python surumu de ayni sayisal yontemi derlenmis cozum uzerinden izledigi icin uc dilde de kullanilan matematik aynidir.
\(N\) hedef siniri olsun. En kucuk asal carpan elemesi \(O(N\log\log N)\) zaman ve \(O(N)\) bellek kullanir. Bu tablodan agirlik dizisini doldurmak \(O(N)\) surer. Baskin asama, parca boyu ile hedef toplam uzerindeki iki donguden olusan agirlikli partition DP'sidir; bu kisim \(O(N^2)\) modular islem gerektirir. Dolayisiyla tum yontem \(O(N^2)\) zamanda calisir ve \(O(N)\) bellek kullanir.
A cada entero positivo \(n\) se le asigna un peso \(A(n)\). La convencion es \(A(1)=1\), para cada primo \(p\) se tiene \(A(p)=1\), y para productos compuestos se usa una regla del tipo Leibniz:
$$A(ab)=aA(b)+bA(a).$$
Si \(\lambda=(\lambda_1,\dots,\lambda_k)\) es una particion de \(s\), su peso es el producto de los pesos de sus partes:
$$w(\lambda)=\prod_{i=1}^{k} A(\lambda_i).$$
Sea \(P(s)\) la suma de estos pesos sobre todas las particiones enteras de \(s\). El valor pedido es el total acumulado
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{999676999}.$$
Las implementaciones publicadas lo evalúan para \(N=50000\), de modo que el problema real es obtener todos los \(P(s)\) hasta ese limite sin enumerar particiones de manera directa.
La recurrencia de \(A(n)\) coincide, para todo \(n\ge 2\), con la derivada aritmetica; la unica convencion adicional es \(A(1)=1\), para que las partes iguales a \(1\) aporten un factor neutro.
Si escribimos
$$n=\prod_{j=1}^{r} p_j^{\alpha_j},$$
la regla del producto da la forma cerrada
$$A(n)=\sum_{j=1}^{r}\alpha_j p_j^{\alpha_j-1}\prod_{\ell\ne j} p_\ell^{\alpha_\ell}=n\sum_{j=1}^{r}\frac{\alpha_j}{p_j}\qquad (n\ge 2).$$
Ejemplos inmediatos:
$$A(2)=1,\qquad A(4)=4,\qquad A(6)=6\left(\frac{1}{2}+\frac{1}{3}\right)=5,\qquad A(12)=12\left(\frac{2}{2}+\frac{1}{3}\right)=16.$$
Esto explica por que la implementacion puede llenar toda la tabla de pesos una vez que conoce el menor factor primo de cada numero.
Para \(s\ge 0\), definimos
$$P(s)=\sum_{\lambda\vdash s} w(\lambda),\qquad P(0)=1,$$
donde \(\lambda\vdash s\) significa que \(\lambda\) es una particion entera de \(s\).
Si una parte de tamaño \(m\) aparece \(c\) veces, aporta el factor \(A(m)^c x^{cm}\). Al sumar sobre todas las multiplicidades \(c\ge 0\) aparece una serie geometrica, por lo que la funcion generadora ordinaria es
$$\sum_{s\ge 0} P(s)x^s=\prod_{m\ge 1}\left(1+A(m)x^m+A(m)^2x^{2m}+\cdots\right)=\prod_{m\ge 1}\frac{1}{1-A(m)x^m}.$$
Esta es la observacion estructural clave: el problema es de particiones ponderadas, no de composiciones ordenadas ni de arboles de factorizacion.
Sea \(P_m(s)\) el total ponderado para \(s\) usando solo tamaños de parte a lo sumo \(m\). Entonces
$$P_0(0)=1,\qquad P_0(s)=0\ \text{si}\ s>0,$$
y para cada \(m\ge 1\) dividimos las particiones en las que no usan la parte \(m\) y las que si la usan al menos una vez:
$$P_m(s)=P_{m-1}(s)+A(m)P_m(s-m)\qquad (s\ge m).$$
El termino \(P_{m-1}(s)\) cubre las particiones que omiten \(m\); el termino \(A(m)P_m(s-m)\) quita una copia de \(m\) de una particion que si la contiene. Esta es exactamente la recurrencia de una DP de mochila no acotada.
Una vez procesados todos los tamaños de parte hasta \(N\), la tabla de coeficientes contiene \(P(0),P(1),\dots,P(N)\). La salida pedida es entonces solo un prefijo:
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{M},\qquad M=999676999.$$
No hace falta un argumento combinatorio adicional al final. Cuando los coeficientes ya estan calculados, el ultimo paso es una acumulacion simple.
Los pesos necesarios son
$$A(1)=1,\qquad A(2)=1,\qquad A(3)=1,\qquad A(4)=4.$$
Las particiones de \(4\) y sus pesos son
$$\begin{aligned} (4) &\longrightarrow 4,\\ (3+1) &\longrightarrow 1\cdot 1=1,\\ (2+2) &\longrightarrow 1\cdot 1=1,\\ (2+1+1) &\longrightarrow 1,\\ (1+1+1+1) &\longrightarrow 1. \end{aligned}$$
Por lo tanto,
$$P(4)=4+1+1+1+1=8.$$
Si se continua el mismo proceso, aparece un punto de control util:
$$P(10)=164,\qquad \sum_{s=1}^{10} P(s)=396.$$
Las implementaciones en C++, Python y Java construyen primero una tabla del menor factor primo hasta \(N\). Esa tabla permite completar la secuencia de pesos en una sola pasada despues de la criba: si \(x\) es primo, su peso es \(1\); y si \(x=pq\) con \(p\) igual al menor factor primo, la regla del producto da \(A(x)=pA(q)+q\), donde \(q<x\) ya fue calculado.
Despues, la implementacion ejecuta una DP unidimensional de particiones no acotadas. Los tamaños de parte se procesan en orden creciente, y las sumas objetivo se recorren hacia arriba desde el tamaño actual hasta \(N\). Ese orden de actualizacion permite reutilizar una parte cualquier numero de veces y, al mismo tiempo, contar cada particion una sola vez sin importar el orden de sus partes.
Al final se acumula el prefijo desde \(1\) hasta \(N\), reduciendo cada paso modulo \(999676999\). La version en Python sigue el mismo metodo numerico al delegar en el solucionador compilado, de modo que las tres versiones comparten exactamente la misma matematica.
Sea \(N\) el limite objetivo. Construir la criba del menor factor primo cuesta \(O(N\log\log N)\) tiempo y \(O(N)\) memoria. Llenar la secuencia de pesos a partir de esa criba es \(O(N)\). La fase dominante es la DP de particiones ponderadas, cuyas dos iteraciones anidadas sobre tamaño de parte y suma objetivo requieren \(O(N^2)\) operaciones modulares. En total, el metodo funciona en \(O(N^2)\) tiempo y usa \(O(N)\) memoria.
对每个正整数 \(n\)，题目赋予一个权重 \(A(n)\)。约定 \(A(1)=1\)，对任意素数 \(p\) 有 \(A(p)=1\)，而对复合乘积使用类似 Leibniz 规则的递推：
$$A(ab)=aA(b)+bA(a).$$
如果 \(\lambda=(\lambda_1,\dots,\lambda_k)\) 是 \(s\) 的一个整数拆分，那么它的权重定义为各部分权重的乘积：
$$w(\lambda)=\prod_{i=1}^{k} A(\lambda_i).$$
记 \(P(s)\) 为 \(s\) 的所有整数拆分权重之和，则题目要求的是累计值
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{999676999}.$$
现有实现把这个量计算到 \(N=50000\)。因此难点不在于写出定义，而在于怎样在不显式枚举所有拆分的前提下，把 \(P(1),P(2),\dots,P(N)\) 全部求出来。
对 \(n\ge 2\) 而言，\(A(n)\) 实际上满足标准的算术导数规则；只是额外规定了 \(A(1)=1\)，这样大小为 \(1\) 的部分会贡献乘法单位元，而不会把整个拆分的乘积压成零。
把
$$n=\prod_{j=1}^{r} p_j^{\alpha_j}$$
写成素因子分解后，由乘法求导规则可以推出闭式
$$A(n)=\sum_{j=1}^{r}\alpha_j p_j^{\alpha_j-1}\prod_{\ell\ne j} p_\ell^{\alpha_\ell}=n\sum_{j=1}^{r}\frac{\alpha_j}{p_j}\qquad (n\ge 2).$$
于是可以立刻算出一些小值：
$$A(2)=1,\qquad A(4)=4,\qquad A(6)=6\left(\frac{1}{2}+\frac{1}{3}\right)=5,\qquad A(12)=12\left(\frac{2}{2}+\frac{1}{3}\right)=16.$$
这也解释了为什么实现只要知道每个数的最小素因子，就能顺次填出整张权重表。
对每个 \(s\ge 0\)，定义
$$P(s)=\sum_{\lambda\vdash s} w(\lambda),\qquad P(0)=1,$$
其中 \(\lambda\vdash s\) 表示 \(\lambda\) 是 \(s\) 的一个整数拆分。
如果某个部分大小 \(m\) 在拆分里出现了 \(c\) 次，那么它对生成函数贡献
$$A(m)^c x^{cm}.$$
对所有 \(c\ge 0\) 求和会得到一个几何级数，因此普通生成函数为
$$\sum_{s\ge 0} P(s)x^s=\prod_{m\ge 1}\left(1+A(m)x^m+A(m)^2x^{2m}+\cdots\right)=\prod_{m\ge 1}\frac{1}{1-A(m)x^m}.$$
这一步非常关键，因为它说明问题本质上是一个“带权整数拆分”问题，而不是去枚举乘法分解、排列顺序或其他更复杂的对象。
设 \(P_m(s)\) 表示只允许使用不超过 \(m\) 的部分时，得到和为 \(s\) 的所有拆分权重总和。那么初始条件是
$$P_0(0)=1,\qquad P_0(s)=0\ \text{当}\ s>0.$$
处理某个固定部分大小 \(m\) 时，所有拆分可以分成两类：完全不用 \(m\) 的，和至少用一次 \(m\) 的。于是得到递推
$$P_m(s)=P_{m-1}(s)+A(m)P_m(s-m)\qquad (s\ge m).$$
第一项表示跳过大小 \(m\)；第二项表示先拿出一个 \(m\)，为它乘上权重 \(A(m)\)，剩下的 \(s-m\) 仍可继续使用大小 \(m\)。这正是完全背包型动态规划的标准结构。
当所有部分大小 \(1,2,\dots,N\) 都处理完以后，表中就已经包含了
$$P(0),P(1),P(2),\dots,P(N).$$
题目最终需要的只是它们的前缀和：
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{M},\qquad M=999676999.$$
因此最后一步没有额外的数学难点。真正的核心在于前面的权重构造和带权拆分 DP。
先列出所需的小权重：
$$A(1)=1,\qquad A(2)=1,\qquad A(3)=1,\qquad A(4)=4.$$
\(4\) 的所有整数拆分及其权重如下：
$$\begin{aligned} (4) &\longrightarrow 4,\\ (3+1) &\longrightarrow 1\cdot 1=1,\\ (2+2) &\longrightarrow 1\cdot 1=1,\\ (2+1+1) &\longrightarrow 1,\\ (1+1+1+1) &\longrightarrow 1. \end{aligned}$$
所以
$$P(4)=4+1+1+1+1=8.$$
如果继续推进同样的计算过程，还可以得到一个有用的核对值：
$$P(10)=164,\qquad \sum_{s=1}^{10} P(s)=396.$$
C++、Python 和 Java 实现都会先建立一个到 \(N\) 为止的最小素因子表。借助这张表，权重序列可以在线性扫描中完成：若某个数本身是素数，则权重为 \(1\)；若 \(x=pq\)，其中 \(p\) 是最小素因子，那么由乘法规则可得 \(A(x)=pA(q)+q\)，而此时 \(q<x\)，所需的较小值已经事先算好。
接下来实现使用一维数组执行完全背包式的拆分 DP。部分大小按从小到大的顺序处理，目标和也从当前部分大小向上扫描到 \(N\)。这种更新顺序正好允许同一种部分被重复使用任意次，同时又不会把不同顺序的同一拆分重复计数。
所有系数算完以后，实现再把 \(1\) 到 \(N\) 的结果做一次前缀求和，并且每一步都对 \(999676999\) 取模。Python 版本通过调用编译后的求解器走相同的数值流程，因此三种语言共享完全一致的数学内容。
设目标上界为 \(N\)。构建最小素因子筛需要 \(O(N\log\log N)\) 时间和 \(O(N)\) 空间。利用这张表填充权重序列是 \(O(N)\)。主导成本来自带权拆分 DP，它对部分大小和目标和做双重循环，因此需要 \(O(N^2)\) 次模运算。总时间复杂度为 \(O(N^2)\)，总空间复杂度为 \(O(N)\)。
Каждому положительному целому \(n\) сопоставляется вес \(A(n)\). По условию \(A(1)=1\), для любого простого \(p\) выполняется \(A(p)=1\), а для составных произведений используется правило типа Лейбница:
$$A(ab)=aA(b)+bA(a).$$
Если \(\lambda=(\lambda_1,\dots,\lambda_k)\) есть разбиение числа \(s\), то его вес равен произведению весов частей:
$$w(\lambda)=\prod_{i=1}^{k} A(\lambda_i).$$
Пусть \(P(s)\) обозначает сумму этих весов по всем разбиениям числа \(s\). Требуется вычислить накопленную сумму
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{999676999}.$$
Опубликованные реализации считают это значение для \(N=50000\), поэтому ключевая задача состоит в том, чтобы получить все \(P(s)\) до этой границы без явного перебора разбиений.
Рекурсия для \(A(n)\) при всех \(n\ge 2\) совпадает с правилом арифметической производной; дополнительное соглашение \(A(1)=1\) нужно лишь затем, чтобы части, равные \(1\), давали нейтральный множитель.
Если записать
$$n=\prod_{j=1}^{r} p_j^{\alpha_j},$$
то из правила произведения получается замкнутая формула
$$A(n)=\sum_{j=1}^{r}\alpha_j p_j^{\alpha_j-1}\prod_{\ell\ne j} p_\ell^{\alpha_\ell}=n\sum_{j=1}^{r}\frac{\alpha_j}{p_j}\qquad (n\ge 2).$$
Небольшие примеры:
$$A(2)=1,\qquad A(4)=4,\qquad A(6)=6\left(\frac{1}{2}+\frac{1}{3}\right)=5,\qquad A(12)=12\left(\frac{2}{2}+\frac{1}{3}\right)=16.$$
Именно поэтому после построения таблицы наименьших простых делителей можно заполнить всю последовательность весов одним проходом.
Для \(s\ge 0\) определим
$$P(s)=\sum_{\lambda\vdash s} w(\lambda),\qquad P(0)=1,$$
где \(\lambda\vdash s\) означает, что \(\lambda\) является целочисленным разбиением числа \(s\).
Если часть размера \(m\) встречается \(c\) раз, то ее вклад равен \(A(m)^c x^{cm}\). Суммирование по всем \(c\ge 0\) дает геометрический ряд, поэтому обычная производящая функция имеет вид
$$\sum_{s\ge 0} P(s)x^s=\prod_{m\ge 1}\left(1+A(m)x^m+A(m)^2x^{2m}+\cdots\right)=\prod_{m\ge 1}\frac{1}{1-A(m)x^m}.$$
Это главный структурный факт: задача является задачей о взвешенных разбиениях, а не о переборе упорядоченных композиций.
Пусть \(P_m(s)\) обозначает суммарный вес разбиений числа \(s\), в которых разрешены только части не больше \(m\). Тогда
$$P_0(0)=1,\qquad P_0(s)=0\ \text{при}\ s>0,$$
а для каждого \(m\ge 1\) разбиваем все варианты на два класса: без части \(m\) и с хотя бы одной частью \(m\).
$$P_m(s)=P_{m-1}(s)+A(m)P_m(s-m)\qquad (s\ge m).$$
Первое слагаемое отвечает за разбиения, где размер \(m\) не используется, второе удаляет одну часть \(m\) и умножает на ее вес. Это в точности рекурсия динамики неограниченного рюкзака.
После обработки всех размеров частей от \(1\) до \(N\) таблица уже содержит значения
$$P(0),P(1),P(2),\dots,P(N).$$
Окончательный ответ задачи - это просто префиксная сумма
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{M},\qquad M=999676999.$$
Никакого дополнительного комбинаторного преобразования в конце не требуется: как только коэффициенты вычислены, остается лишь аккуратно сложить их по модулю.
Нужные веса частей таковы:
$$A(1)=1,\qquad A(2)=1,\qquad A(3)=1,\qquad A(4)=4.$$
Все разбиения числа \(4\) и их веса:
$$\begin{aligned} (4) &\longrightarrow 4,\\ (3+1) &\longrightarrow 1\cdot 1=1,\\ (2+2) &\longrightarrow 1\cdot 1=1,\\ (2+1+1) &\longrightarrow 1,\\ (1+1+1+1) &\longrightarrow 1. \end{aligned}$$
Следовательно,
$$P(4)=4+1+1+1+1=8.$$
Если продолжить тот же процесс, получается удобная контрольная точка:
$$P(10)=164,\qquad \sum_{s=1}^{10} P(s)=396.$$
Реализации на C++, Python и Java сначала строят таблицу наименьших простых делителей до \(N\). Благодаря ей последовательность весов вычисляется линейным проходом после решета: если число \(x\) простое, его вес равен \(1\); если \(x=pq\), где \(p\) - наименьший простой делитель, то правило произведения дает \(A(x)=pA(q)+q\), причем \(q<x\) уже обработано раньше.
После этого реализация запускает одномерное DP для взвешенных неограниченных разбиений. Размеры частей рассматриваются в возрастающем порядке, а целевые суммы просматриваются вверх от текущего размера до \(N\). Именно такой порядок обновления позволяет использовать одну и ту же часть сколько угодно раз и при этом не считать одну и ту же разбиение несколько раз из-за перестановки частей.
В финале коэффициенты от \(1\) до \(N\) накапливаются в префиксную сумму, а каждое арифметическое действие сразу сокращается по модулю \(999676999\). Версия на Python следует той же численной схеме, передавая вычисление скомпилированному решателю, поэтому математика во всех трех языках полностью совпадает.
Пусть \(N\) - целевая верхняя граница. Построение решета наименьших простых делителей занимает \(O(N\log\log N)\) времени и \(O(N)\) памяти. Заполнение последовательности весов по этой таблице требует \(O(N)\). Доминирующая часть - DP по размерам частей и целевым суммам, то есть \(O(N^2)\) модульных операций. Итого весь метод работает за \(O(N^2)\) времени и использует \(O(N)\) памяти.
تسند المسألة وزنا \(A(n)\) إلى كل عدد صحيح موجب \(n\). الاتفاق هو أن \(A(1)=1\)، ولكل عدد أولي \(p\) يكون \(A(p)=1\)، أما في حالة الجداءات المركبة فتستعمل قاعدة شبيهة بقاعدة لايبنتز:
$$A(ab)=aA(b)+bA(a).$$
إذا كانت \(\lambda=(\lambda_1,\dots,\lambda_k)\) تجزئة للعدد \(s\)، فإن وزنها هو حاصل ضرب أوزان أجزائها:
$$w(\lambda)=\prod_{i=1}^{k} A(\lambda_i).$$
ولتكن \(P(s)\) مجموع هذه الأوزان على جميع تجزئات \(s\). المطلوب هو المجموع التراكمي
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{999676999}.$$
التنفيذات المنشورة تحسب هذه القيمة عند \(N=50000\)، ولذلك فالتحدي الحقيقي هو استخراج كل القيم \(P(s)\) حتى هذا الحد من غير تعداد جميع التجزئات صراحة.
العلاقة التعاقبية الخاصة بـ \(A(n)\) تطابق، لكل \(n\ge 2\)، قاعدة المشتقة الحسابية. أما الشرط الإضافي \(A(1)=1\) فوظيفته أن يجعل الجزء \(1\) عنصرا محايدا في الضرب.
إذا كتبنا
$$n=\prod_{j=1}^{r} p_j^{\alpha_j},$$
فإن قاعدة اشتقاق الجداء تعطي الصيغة المغلقة
$$A(n)=\sum_{j=1}^{r}\alpha_j p_j^{\alpha_j-1}\prod_{\ell\ne j} p_\ell^{\alpha_\ell}=n\sum_{j=1}^{r}\frac{\alpha_j}{p_j}\qquad (n\ge 2).$$
ومن ثم نحصل على أمثلة صغيرة مباشرة:
$$A(2)=1,\qquad A(4)=4,\qquad A(6)=6\left(\frac{1}{2}+\frac{1}{3}\right)=5,\qquad A(12)=12\left(\frac{2}{2}+\frac{1}{3}\right)=16.$$
وهذا يوضح لماذا يستطيع التنفيذ ملء جدول الأوزان كله بعد معرفة أصغر عامل أولي لكل عدد.
لكل \(s\ge 0\) نعرف
$$P(s)=\sum_{\lambda\vdash s} w(\lambda),\qquad P(0)=1,$$
حيث إن \(\lambda\vdash s\) تعني أن \(\lambda\) تجزئة صحيحة للعدد \(s\).
إذا ظهر الجزء \(m\) بعدد تكرارات يساوي \(c\)، فمساهمته في الدالة المولدة هي
$$A(m)^c x^{cm}.$$
وعند الجمع على جميع \(c\ge 0\) نحصل على متسلسلة هندسية، وبالتالي تكون الدالة المولدة العادية
$$\sum_{s\ge 0} P(s)x^s=\prod_{m\ge 1}\left(1+A(m)x^m+A(m)^2x^{2m}+\cdots\right)=\prod_{m\ge 1}\frac{1}{1-A(m)x^m}.$$
هذه هي الفكرة البنيوية الأساسية: المسألة هي مسألة تجزئات موزونة، وليست بحثا مباشرا في ترتيبات أو تفكيكات مرتبة.
لنرمز بـ \(P_m(s)\) إلى مجموع أوزان تجزئات \(s\) عندما نسمح فقط بالأجزاء التي لا تتجاوز \(m\). عندئذ
$$P_0(0)=1,\qquad P_0(s)=0\quad (s>0).$$
ولكل \(m\ge 1\) نقسم التجزئات إلى نوعين: تجزئات لا تستخدم الجزء \(m\) مطلقا، وتجزئات تستخدمه مرة واحدة على الأقل.
$$P_m(s)=P_{m-1}(s)+A(m)P_m(s-m)\qquad (s\ge m).$$
الحد الأول يمثل تجاهل الجزء \(m\)، أما الحد الثاني فينزع نسخة واحدة من \(m\) ويضرب في وزنها. وهذه بالضبط بنية برمجة ديناميكية من نوع الحقيبة غير المحدودة.
بعد معالجة جميع أحجام الأجزاء من \(1\) إلى \(N\)، يصبح لدينا الجدول الكامل
$$P(0),P(1),P(2),\dots,P(N).$$
والجواب النهائي للمسألة ليس إلا مجموعا بادئيا لهذه القيم:
$$S(N)=\sum_{s=1}^{N} P(s)\pmod{M},\qquad M=999676999.$$
إذن لا توجد حيلة إضافية في نهاية الحل؛ ما إن تحسب المعاملات حتى يبقى جمعها فقط مع الاختزال المعياري.
الأوزان الصغيرة اللازمة هي
$$A(1)=1,\qquad A(2)=1,\qquad A(3)=1,\qquad A(4)=4.$$
تجزئات العدد \(4\) وأوزانها هي
$$\begin{aligned} (4) &\longrightarrow 4,\\ (3+1) &\longrightarrow 1\cdot 1=1,\\ (2+2) &\longrightarrow 1\cdot 1=1,\\ (2+1+1) &\longrightarrow 1,\\ (1+1+1+1) &\longrightarrow 1. \end{aligned}$$
ومن ثم
$$P(4)=4+1+1+1+1=8.$$
وبالاستمرار في العملية نفسها نحصل على نقطة تحقق مفيدة:
$$P(10)=164,\qquad \sum_{s=1}^{10} P(s)=396.$$
تنشئ تنفيذات C++ و Python و Java أولا جدولا لأصغر عامل أولي حتى \(N\). وبالاعتماد على هذا الجدول يمكن ملء متتالية الأوزان بتمرير واحد: إذا كان \(x\) أوليا فوزنه \(1\)، وإذا كان \(x=pq\) حيث \(p\) هو أصغر عامل أولي، فإن قاعدة الجداء تعطي \(A(x)=pA(q)+q\)، والعدد \(q<x\) يكون قد عولج مسبقا.
بعد ذلك ينفذ البرنامج برمجة ديناميكية أحادية البعد للتجزئات غير المحدودة. تعالج أحجام الأجزاء بترتيب تصاعدي، وتمسح المجاميع الهدف صعودا من الحجم الحالي حتى \(N\). هذا الترتيب هو الذي يسمح بإعادة استعمال الجزء نفسه عددا غير محدود من المرات، وفي الوقت نفسه يضمن عد كل تجزئة مرة واحدة فقط بغض النظر عن ترتيب أجزائها.
في النهاية يجمع التنفيذ القيم من \(1\) إلى \(N\) في مجموع بادئ، مع الاختزال بعد كل عملية حسابية بترديد \(999676999\). أما نسخة Python فتتبع المسار العددي نفسه عبر استدعاء المحلل المترجم، ولذلك تشترك اللغات الثلاث في الرياضيات نفسها تماما.
إذا كان \(N\) هو الحد المطلوب، فإن بناء غربال أصغر عامل أولي يكلف \(O(N\log\log N)\) زمنا و \(O(N)\) ذاكرة. وملء متتالية الأوزان انطلاقا من هذا الغربال يكلف \(O(N)\). أما المرحلة المهيمنة فهي برمجة التجزئات الموزونة، إذ توجد حلقتان متداخلتان على حجم الجزء والمجموع الهدف، وهذا يعني \(O(N^2)\) عملية معيارية. لذلك فإن التعقيد الكلي هو \(O(N^2)\) زمنا و \(O(N)\) ذاكرة.