For each positive integer \(n\), let \(f(n)\) be the largest product obtainable from a partition of \(n\) into distinct positive integers, and let \(m(n)\) be the number of parts in an optimal partition. Project Euler 374 asks for
$$M(N)=\sum_{n=1}^{N} f(n)m(n)$$
at \(N=10^{14}\), reduced modulo
$$P=982451653.$$
The local C++, Python, and Java solutions all exploit the same fact: optimal partitions fall into simple \(\Theta(\sqrt{n})\)-sized blocks, so the program never searches over partitions explicitly.
Write an optimal partition with \(k\) parts as
$$a_1 \lt a_2 \lt \cdots \lt a_k,\qquad a_1+\cdots+a_k=n.$$
If some adjacent gap is at least \(3\), say \(a_{i+1}-a_i\ge 3\), then replacing \((a_i,a_{i+1})\) by \((a_i+1,a_{i+1}-1)\) keeps the sum fixed, preserves distinctness, and increases the product because
$$ (a_i+1)(a_{i+1}-1)-a_i a_{i+1} = a_{i+1}-a_i-1 \gt 0. $$
Therefore every optimal partition has adjacent differences only \(1\) or \(2\). For \(n\ge 2\), the maximizing partitions are thus “near-consecutive”: a run of consecutive integers with at most one missing value.
The baseline near-consecutive partition with \(m\) parts is
$$\{2,3,\dots,m+1\},$$
whose sum is
$$T_m = 2+3+\cdots+(m+1)=\frac{m(m+3)}{2}.$$
This is the left endpoint of the block where the optimal partition has exactly \(m\) parts. Hence the correct block index for a given \(n\) is
$$m=\max\left\{r:\frac{r(r+3)}{2}\le n\right\}.$$
The code computes this with the integer-square-root estimate
$$m\approx \frac{\sqrt{8n+9}-3}{2},$$
and then adjusts by at most a couple of integer steps to remove rounding issues.
Write
$$n=T_m+s,\qquad 0\le s\le m+1.$$
Since
$$T_{m+1}=\frac{(m+1)(m+4)}{2}=T_m+m+2,$$
the full \(m\)-block is the interval
$$T_m \le n \le T_{m+1}-1=\frac{(m+1)(m+4)}{2}-1.$$
Throughout this whole interval the optimal partition size is constant:
$$m(n)=m.$$
If \(0\le s\le m\), the optimal partition is obtained from the consecutive set \(\{2,3,\dots,m+2\}\) by deleting exactly one value:
$$\{2,3,\dots,m+2\}\setminus\{m+2-s\}.$$
Its sum is
$$ \left(\sum_{j=2}^{m+2} j\right)-(m+2-s) = \frac{m(m+3)}{2}+s = n, $$
and its product is
$$f(n)=\frac{(m+2)!}{m+2-s}.$$
Multiplying by the part count gives
$$f(n)m(n)=m\frac{(m+2)!}{m+2-s},\qquad 0\le s\le m.$$
If \(s=m+1\), the “deleted value” would have to be \(1\), so the shape changes to
$$\{3,4,\dots,m+1,m+3\}.$$
Its product is
$$f(n)=\frac{(m+3)!}{2(m+2)},$$
hence
$$f(n)m(n)=m\frac{(m+3)!}{2(m+2)}.$$
This is exactly the piecewise formula implemented by all three solution files. The code keeps the middle case \(s=m\) as a separate branch, but mathematically it is simply the denominator-\(2\) instance of the first formula.
We have
$$T_3=\frac{3\cdot 6}{2}=9,\qquad T_4=\frac{4\cdot 7}{2}=14,$$
so \(m=3\) and \(s=10-9=1\). Therefore the optimal partition is
$$\{2,3,4,5\}\setminus\{4\}=\{2,3,5\}.$$
Thus
$$f(10)=2\cdot 3\cdot 5=30,\qquad m(10)=3,\qquad f(10)m(10)=90,$$
which matches the checkpoint in the C++ verifier.
For a complete block, first sum the \(m+1\) terms with \(0\le s\le m\):
$$ \sum_{s=0}^{m} m\frac{(m+2)!}{m+2-s} = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d}, $$
where we reindexed with \(d=m+2-s\). The final point of the block contributes
$$m\frac{(m+3)!}{2(m+2)}.$$
So the complete \(m\)-block contribution is
$$ B_m = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d} + m\frac{(m+3)!}{2(m+2)}. $$
This is why the implementation only needs a running factorial and a running harmonic-style sum of modular inverses.
Because \(P\) is prime and every denominator satisfies \(2\le d\le m_{\max}+3 \lt P\), all required inverses exist modulo \(P\). The code precomputes them in linear time via
$$\mathrm{inv}[1]=1,\qquad \mathrm{inv}[i]=-\left\lfloor\frac{P}{i}\right\rfloor\mathrm{inv}[P\bmod i]\pmod{P}.$$
This follows from writing \(P=qi+r\), so \(r\equiv -qi\pmod P\), then multiplying by \(r^{-1}i^{-1}\). Once the inverse table is built, every full block is processed in \(O(1)\) modular arithmetic.
The C++, Python, and Java implementations are structurally identical. They first compute \(m_{\max}=\max\{m:T_m\le N\}\), then precompute modular inverses up to \(m_{\max}+3\). During the main loop they maintain
$$\texttt{fact}=(m+2)!\pmod P,\qquad \texttt{harmonic}=\sum_{d=2}^{m+2}\frac{1}{d}\pmod P.$$
For each \(m\), the code knows the block start \(T_m\), the block end \(T_{m+1}-1\), and how much of that block is still inside the target range. All fully covered blocks use the closed form above; only the last block may be truncated, and the code handles that by summing the needed inverse segment explicitly.
The C++ file also checks the derivation against small exact values:
$$f(5)m(5)=12,\qquad f(10)m(10)=90,\qquad \sum_{n=1}^{100} f(n)m(n)=1683550844462.$$
Since \(T_m\sim m^2/2\), the maximal block index satisfies \(m_{\max}=\Theta(\sqrt{N})\). Precomputing inverses, advancing the running factorial, and iterating over all blocks therefore costs \(O(\sqrt{N})\) time. The inverse table uses \(O(\sqrt{N})\) memory. Only the final block can be partial, so there is no hidden extra logarithmic factor.
Für jede positive ganze Zahl \(n\) sei \(f(n)\) das größte Produkt, das man aus einer Zerlegung von \(n\) in paarweise verschiedene positive Summanden erhält, und \(m(n)\) die Anzahl der Summanden in einer optimalen Zerlegung. Gesucht ist in Euler 374
$$M(N)=\sum_{n=1}^{N} f(n)m(n)$$
für \(N=10^{14}\), reduziert modulo
$$P=982451653.$$
Die lokalen Lösungen in C++, Python und Java enumerieren keine Partitionen, sondern nutzen eine blockweise geschlossene Form der optimalen Zerlegungen.
Schreibe eine optimale Partition mit \(k\) Teilen als
$$a_1 \lt a_2 \lt \cdots \lt a_k,\qquad a_1+\cdots+a_k=n.$$
Falls eine Lücke mindestens \(3\) groß ist, also \(a_{i+1}-a_i\ge 3\), dann erhöht die Ersetzung \((a_i,a_{i+1})\mapsto(a_i+1,a_{i+1}-1)\) das Produkt, erhält aber Summe und Verschiedenheit, denn
$$ (a_i+1)(a_{i+1}-1)-a_i a_{i+1} = a_{i+1}-a_i-1 \gt 0. $$
Also können in einer optimalen Partition benachbarte Differenzen nur \(1\) oder \(2\) sein. Die Gewinnerform ist daher eine fast zusammenhängende Folge ganzer Zahlen mit höchstens einem fehlenden Wert.
Die Grundform mit \(m\) Teilen ist
$$\{2,3,\dots,m+1\},$$
deren Summe
$$T_m = 2+3+\cdots+(m+1)=\frac{m(m+3)}{2}$$
beträgt. Dieser Wert ist der linke Rand des Blocks, in dem die optimale Partition genau \(m\) Teile besitzt. Also ist
$$m=\max\left\{r:\frac{r(r+3)}{2}\le n\right\}.$$
Im Code wird zunächst die Näherung
$$m\approx \frac{\sqrt{8n+9}-3}{2}$$
berechnet und dann mit wenigen Ganzzahlschritten korrigiert.
Setze
$$n=T_m+s,\qquad 0\le s\le m+1.$$
Wegen
$$T_{m+1}=\frac{(m+1)(m+4)}{2}=T_m+m+2$$
ist der vollständige \(m\)-Block das Intervall
$$T_m \le n \le T_{m+1}-1=\frac{(m+1)(m+4)}{2}-1.$$
Innerhalb dieses ganzen Intervalls bleibt die optimale Teilanzahl konstant:
$$m(n)=m.$$
Für \(0\le s\le m\) entsteht die optimale Partition aus \(\{2,3,\dots,m+2\}\), indem genau ein Wert entfernt wird:
$$\{2,3,\dots,m+2\}\setminus\{m+2-s\}.$$
Die Summe ist
$$ \left(\sum_{j=2}^{m+2} j\right)-(m+2-s) = \frac{m(m+3)}{2}+s = n, $$
und das Produkt lautet
$$f(n)=\frac{(m+2)!}{m+2-s}.$$
Damit folgt
$$f(n)m(n)=m\frac{(m+2)!}{m+2-s},\qquad 0\le s\le m.$$
Für \(s=m+1\) müsste der entfernte Wert gleich \(1\) sein; dann ändert sich die Form zu
$$\{3,4,\dots,m+1,m+3\}.$$
Deren Produkt ist
$$f(n)=\frac{(m+3)!}{2(m+2)},$$
also
$$f(n)m(n)=m\frac{(m+3)!}{2(m+2)}.$$
Genau diese Fallunterscheidung setzen die drei Implementierungen um. Der Sonderfall \(s=m\) ist mathematisch nur der Nenner-\(2\)-Fall der ersten Formel.
Es gilt
$$T_3=\frac{3\cdot 6}{2}=9,\qquad T_4=\frac{4\cdot 7}{2}=14,$$
also \(m=3\) und \(s=1\). Die optimale Partition ist damit
$$\{2,3,4,5\}\setminus\{4\}=\{2,3,5\}.$$
Folglich
$$f(10)=2\cdot 3\cdot 5=30,\qquad m(10)=3,\qquad f(10)m(10)=90,$$
genau wie im C++-Checkpoint.
Für einen vollständigen Block summieren wir zunächst die \(m+1\) Terme mit \(0\le s\le m\):
$$ \sum_{s=0}^{m} m\frac{(m+2)!}{m+2-s} = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d}, $$
wobei \(d=m+2-s\) substituiert wurde. Der letzte Blockwert liefert zusätzlich
$$m\frac{(m+3)!}{2(m+2)}.$$
Damit ist der gesamte Blockbeitrag
$$ B_m = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d} + m\frac{(m+3)!}{2(m+2)}. $$
Darum benötigt das Programm nur ein laufendes Fakultätsprodukt und eine laufende harmonische Inversensumme.
Da \(P\) prim ist und alle Nenner \(2\le d\le m_{\max}+3 \lt P\) erfüllen, existieren alle benötigten Inversen modulo \(P\). Der Code berechnet sie linear mit
$$\mathrm{inv}[1]=1,\qquad \mathrm{inv}[i]=-\left\lfloor\frac{P}{i}\right\rfloor\mathrm{inv}[P\bmod i]\pmod{P}.$$
Dies folgt aus \(P=qi+r\), also \(r\equiv -qi\pmod P\). Danach kostet jeder vollständige Block nur noch \(O(1)\)-Arbeit.
Die Implementierungen in C++, Python und Java sind logisch gleich aufgebaut. Zuerst wird \(m_{\max}=\max\{m:T_m\le N\}\) bestimmt, danach werden modulare Inversen bis \(m_{\max}+3\) vorab berechnet. Während der Hauptschleife hält der Code
$$\texttt{fact}=(m+2)!\pmod P,\qquad \texttt{harmonic}=\sum_{d=2}^{m+2}\frac{1}{d}\pmod P.$$
Für jedes \(m\) sind Blockanfang, Blockende und die noch im Suchbereich liegende Blocklänge sofort bekannt. Vollständig enthaltene Blöcke nutzen direkt die geschlossene Form; nur der letzte Block kann abgeschnitten sein und wird dann über das passende inverse Teilstück behandelt.
Die C++-Datei prüft außerdem die Herleitung mit kleinen exakten Werten:
$$f(5)m(5)=12,\qquad f(10)m(10)=90,\qquad \sum_{n=1}^{100} f(n)m(n)=1683550844462.$$
Aus \(T_m\sim m^2/2\) folgt \(m_{\max}=\Theta(\sqrt{N})\). Das Vorberechnen der Inversen, das Fortschreiben der Fakultät und die Schleife über alle Blöcke benötigen daher insgesamt \(O(\sqrt{N})\) Zeit. Der inverse Array verbraucht \(O(\sqrt{N})\) Speicher. Da nur der letzte Block unvollständig sein kann, entsteht kein zusätzlicher versteckter Faktor.
Her pozitif tamsayı \(n\) için, \(f(n)\) sayısını \(n\)'in farklı pozitif tamsayılara ayrılışları arasında elde edilebilen en büyük çarpım, \(m(n)\) sayısını da bu optimum ayrılıştaki terim sayısı olarak tanımlayalım. Euler 374'te istenen büyüklük
$$M(N)=\sum_{n=1}^{N} f(n)m(n)$$
olup \(N=10^{14}\) için
$$P=982451653$$
modunda hesaplanır. Depodaki C++, Python ve Java çözümleri doğrudan partition aramaz; bunun yerine optimum partitionların blok yapısını kullanır.
\(k\) terimli bir optimum partitionı
$$a_1 \lt a_2 \lt \cdots \lt a_k,\qquad a_1+\cdots+a_k=n$$
şeklinde yazalım. Eğer komşu iki terim arasında en az \(3\) fark varsa, yani \(a_{i+1}-a_i\ge 3\), o zaman \((a_i,a_{i+1})\) yerine \((a_i+1,a_{i+1}-1)\) koymak toplamı ve farklılık şartını korur, fakat çarpımı artırır; çünkü
$$ (a_i+1)(a_{i+1}-1)-a_i a_{i+1} = a_{i+1}-a_i-1 \gt 0. $$
Dolayısıyla optimum bir partitionda ardışık farklar sadece \(1\) veya \(2\) olabilir. Yani kazanan yapı, en fazla bir değeri eksik olan neredeyse ardışık bir sayı kümesidir.
\(m\) terimli temel yapı
$$\{2,3,\dots,m+1\}$$
olup toplamı
$$T_m = 2+3+\cdots+(m+1)=\frac{m(m+3)}{2}$$
şeklindedir. Bu değer, optimum partitionın tam olarak \(m\) terimli olduğu bloğun sol ucudur. Bu nedenle verilen \(n\) için doğru blok indisi
$$m=\max\left\{r:\frac{r(r+3)}{2}\le n\right\}$$
olur. Kod önce
$$m\approx \frac{\sqrt{8n+9}-3}{2}$$
yaklaşımını hesaplar, ardından tam sayı düzeltmeleriyle kesin değeri bulur.
Şimdi
$$n=T_m+s,\qquad 0\le s\le m+1$$
yazalım. Çünkü
$$T_{m+1}=\frac{(m+1)(m+4)}{2}=T_m+m+2,$$
tam \(m\)-bloğu
$$T_m \le n \le T_{m+1}-1=\frac{(m+1)(m+4)}{2}-1$$
aralığıdır. Bu aralık boyunca optimum terim sayısı sabittir:
$$m(n)=m.$$
Eğer \(0\le s\le m\) ise optimum partition, \(\{2,3,\dots,m+2\}\) kümesinden tek bir değer silinerek elde edilir:
$$\{2,3,\dots,m+2\}\setminus\{m+2-s\}.$$
Toplamı
$$ \left(\sum_{j=2}^{m+2} j\right)-(m+2-s) = \frac{m(m+3)}{2}+s = n, $$
çarpımı ise
$$f(n)=\frac{(m+2)!}{m+2-s}$$
olur. Böylece
$$f(n)m(n)=m\frac{(m+2)!}{m+2-s},\qquad 0\le s\le m.$$
\(s=m+1\) durumunda silinmesi gereken değer \(1\) olurdu; bu yüzden şekil
$$\{3,4,\dots,m+1,m+3\}$$
haline dönüşür. Bu partition için
$$f(n)=\frac{(m+3)!}{2(m+2)},$$
dolayısıyla
$$f(n)m(n)=m\frac{(m+3)!}{2(m+2)}.$$
Üç çözüm dosyasındaki parçalı formül tam olarak budur. Kodda \(s=m\) ayrıca yazılmıştır, fakat matematiksel olarak bu sadece ilk formülün paydası \(2\) olan özel halidir.
Burada
$$T_3=\frac{3\cdot 6}{2}=9,\qquad T_4=\frac{4\cdot 7}{2}=14,$$
dolayısıyla \(m=3\) ve \(s=1\). Optimum partition
$$\{2,3,4,5\}\setminus\{4\}=\{2,3,5\}$$
olur. Böylece
$$f(10)=2\cdot 3\cdot 5=30,\qquad m(10)=3,\qquad f(10)m(10)=90,$$
ki bu da C++ doğrulama kontrolüyle aynıdır.
Tam bir blok için önce \(0\le s\le m\) olan \(m+1\) terimi toplarız:
$$ \sum_{s=0}^{m} m\frac{(m+2)!}{m+2-s} = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d}, $$
burada \(d=m+2-s\) değişken dönüşümü kullanılmıştır. Bloğun son noktası ek olarak
$$m\frac{(m+3)!}{2(m+2)}$$
katkısı verir. Sonuçta tam blok katkısı
$$ B_m = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d} + m\frac{(m+3)!}{2(m+2)} $$
olur. Bu yüzden uygulama sadece akan bir faktöriyel değeri ve akan bir modüler harmonik toplam tutar.
\(P\) asal olduğundan ve tüm paydalar \(2\le d\le m_{\max}+3 \lt P\) sağladığından gerekli bütün tersler modulo \(P\) vardır. Kod bunları doğrusal sürede şu yineleme ile hesaplar:
$$\mathrm{inv}[1]=1,\qquad \mathrm{inv}[i]=-\left\lfloor\frac{P}{i}\right\rfloor\mathrm{inv}[P\bmod i]\pmod{P}.$$
Bu, \(P=qi+r\) yazılıp \(r\equiv -qi\pmod P\) eşitliği kullanılarak elde edilir. Ters tablo hazırlandıktan sonra her tam blok \(O(1)\) maliyetle işlenir.
C++, Python ve Java çözümleri aynı iskeleti takip eder. Önce \(m_{\max}=\max\{m:T_m\le N\}\) bulunur, sonra \(m_{\max}+3\)'e kadar modüler tersler önceden hesaplanır. Ana döngü boyunca kod
$$\texttt{fact}=(m+2)!\pmod P,\qquad \texttt{harmonic}=\sum_{d=2}^{m+2}\frac{1}{d}\pmod P$$
değerlerini güncel tutar. Her \(m\) için blok başlangıcı, blok sonu ve hedef aralıkta kalan blok uzunluğu bellidir. Tam kapsanan bloklar doğrudan kapalı formülle eklenir; yalnızca son blok eksik olabilir ve o durumda gereken ters parçalı toplamı açıkça toplanır.
C++ dosyası ayrıca küçük örneklerle formülü kontrol eder:
$$f(5)m(5)=12,\qquad f(10)m(10)=90,\qquad \sum_{n=1}^{100} f(n)m(n)=1683550844462.$$
\(T_m\sim m^2/2\) olduğundan \(m_{\max}=\Theta(\sqrt{N})\) olur. Terslerin hazırlanması, faktöriyel güncellemeleri ve tüm bloklar üzerinden geçiş toplamda \(O(\sqrt{N})\) zaman alır. Ters dizisi için \(O(\sqrt{N})\) bellek gerekir. Sadece son blok kısmi olabildiği için gizli ek bir çarpan oluşmaz.
Para cada entero positivo \(n\), sea \(f(n)\) el mayor producto que puede obtenerse a partir de una partición de \(n\) en enteros positivos distintos, y sea \(m(n)\) el número de partes de una partición óptima. En Euler 374 se pide
$$M(N)=\sum_{n=1}^{N} f(n)m(n)$$
para \(N=10^{14}\), reducido módulo
$$P=982451653.$$
Las soluciones locales en C++, Python y Java no enumeran particiones: usan una descripción cerrada de la forma óptima por bloques.
Escribamos una partición óptima con \(k\) partes como
$$a_1 \lt a_2 \lt \cdots \lt a_k,\qquad a_1+\cdots+a_k=n.$$
Si alguna diferencia adyacente satisface \(a_{i+1}-a_i\ge 3\), entonces sustituir \((a_i,a_{i+1})\) por \((a_i+1,a_{i+1}-1)\) conserva la suma y la distinción entre partes, pero aumenta el producto, ya que
$$ (a_i+1)(a_{i+1}-1)-a_i a_{i+1} = a_{i+1}-a_i-1 \gt 0. $$
Por tanto, en una partición óptima todas las diferencias vecinas son \(1\) o \(2\). La forma ganadora es entonces una corrida casi consecutiva de enteros, con a lo sumo un valor ausente.
La forma base con \(m\) partes es
$$\{2,3,\dots,m+1\},$$
cuya suma vale
$$T_m = 2+3+\cdots+(m+1)=\frac{m(m+3)}{2}.$$
Ese valor es el extremo izquierdo del bloque en el que la partición óptima tiene exactamente \(m\) partes. Así, el índice correcto para un \(n\) dado es
$$m=\max\left\{r:\frac{r(r+3)}{2}\le n\right\}.$$
El código lo aproxima primero con
$$m\approx \frac{\sqrt{8n+9}-3}{2},$$
y luego corrige con unos pocos ajustes enteros.
Escribimos
$$n=T_m+s,\qquad 0\le s\le m+1.$$
Como
$$T_{m+1}=\frac{(m+1)(m+4)}{2}=T_m+m+2,$$
el bloque completo de índice \(m\) es
$$T_m \le n \le T_{m+1}-1=\frac{(m+1)(m+4)}{2}-1.$$
En todo ese intervalo el número óptimo de partes permanece constante:
$$m(n)=m.$$
Si \(0\le s\le m\), la partición óptima se obtiene a partir de \(\{2,3,\dots,m+2\}\) eliminando un único valor:
$$\{2,3,\dots,m+2\}\setminus\{m+2-s\}.$$
Su suma es
$$ \left(\sum_{j=2}^{m+2} j\right)-(m+2-s) = \frac{m(m+3)}{2}+s = n, $$
y su producto es
$$f(n)=\frac{(m+2)!}{m+2-s}.$$
Por consiguiente,
$$f(n)m(n)=m\frac{(m+2)!}{m+2-s},\qquad 0\le s\le m.$$
Si \(s=m+1\), el valor eliminado tendría que ser \(1\), así que la forma cambia a
$$\{3,4,\dots,m+1,m+3\}.$$
En ese caso
$$f(n)=\frac{(m+3)!}{2(m+2)},$$
y por tanto
$$f(n)m(n)=m\frac{(m+3)!}{2(m+2)}.$$
Ésta es exactamente la fórmula por casos usada en las tres implementaciones. El caso \(s=m\) aparece separado en el código, pero matemáticamente no es más que el caso de denominador \(2\) de la primera expresión.
Tenemos
$$T_3=\frac{3\cdot 6}{2}=9,\qquad T_4=\frac{4\cdot 7}{2}=14,$$
de modo que \(m=3\) y \(s=1\). La partición óptima es
$$\{2,3,4,5\}\setminus\{4\}=\{2,3,5\}.$$
Así,
$$f(10)=2\cdot 3\cdot 5=30,\qquad m(10)=3,\qquad f(10)m(10)=90,$$
en acuerdo con el punto de control del archivo C++.
Para un bloque completo, primero se suman los \(m+1\) términos con \(0\le s\le m\):
$$ \sum_{s=0}^{m} m\frac{(m+2)!}{m+2-s} = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d}, $$
reindexando con \(d=m+2-s\). El último punto del bloque añade
$$m\frac{(m+3)!}{2(m+2)}.$$
Por ello, la contribución total del bloque es
$$ B_m = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d} + m\frac{(m+3)!}{2(m+2)}. $$
Ésta es la razón por la que el programa sólo necesita mantener un factorial acumulado y una suma armónica modular de inversos.
Como \(P\) es primo y todos los denominadores cumplen \(2\le d\le m_{\max}+3 \lt P\), todos los inversos existen módulo \(P\). El código los precalcula linealmente mediante
$$\mathrm{inv}[1]=1,\qquad \mathrm{inv}[i]=-\left\lfloor\frac{P}{i}\right\rfloor\mathrm{inv}[P\bmod i]\pmod{P}.$$
Esto proviene de escribir \(P=qi+r\), de donde \(r\equiv -qi\pmod P\). Una vez construida la tabla de inversos, cada bloque completo se procesa en \(O(1)\).
Las versiones en C++, Python y Java tienen la misma estructura. Primero calculan \(m_{\max}=\max\{m:T_m\le N\}\), luego precalculan los inversos modulares hasta \(m_{\max}+3\). En el bucle principal mantienen
$$\texttt{fact}=(m+2)!\pmod P,\qquad \texttt{harmonic}=\sum_{d=2}^{m+2}\frac{1}{d}\pmod P.$$
Para cada \(m\), el programa conoce el inicio del bloque, el final del bloque y cuánta parte de ese bloque queda dentro del rango objetivo. Los bloques completos usan directamente la fórmula cerrada; sólo el último bloque puede quedar truncado, y en ese caso se suma explícitamente el segmento necesario de inversos.
El archivo C++ además valida la derivación con valores pequeños exactos:
$$f(5)m(5)=12,\qquad f(10)m(10)=90,\qquad \sum_{n=1}^{100} f(n)m(n)=1683550844462.$$
Dado que \(T_m\sim m^2/2\), el mayor índice de bloque satisface \(m_{\max}=\Theta(\sqrt{N})\). El precálculo de inversos, la actualización del factorial y el recorrido de todos los bloques cuestan \(O(\sqrt{N})\) tiempo en total. La tabla de inversos usa \(O(\sqrt{N})\) memoria. Como sólo el bloque final puede ser parcial, no aparece ningún factor extra oculto.
对每个正整数 \(n\)，记 \(f(n)\) 为把 \(n\) 拆成若干个互不相同的正整数时所能得到的最大乘积， 记 \(m(n)\) 为达到该最大乘积时的项数。Euler 374 要求计算
$$M(N)=\sum_{n=1}^{N} f(n)m(n)$$
其中 \(N=10^{14}\)，并对
$$P=982451653$$
取模。仓库里的 C++、Python、Java 解法都不直接枚举拆分，而是利用最优拆分的分块闭式结构。
把一个最优拆分写成
$$a_1 \lt a_2 \lt \cdots \lt a_k,\qquad a_1+\cdots+a_k=n.$$
如果某个相邻间隔至少为 \(3\)，即 \(a_{i+1}-a_i\ge 3\)，那么把 \((a_i,a_{i+1})\) 替换成 \((a_i+1,a_{i+1}-1)\) 后，和不变、互异性不变，而乘积变大，因为
$$ (a_i+1)(a_{i+1}-1)-a_i a_{i+1} = a_{i+1}-a_i-1 \gt 0. $$
所以最优拆分中，相邻两项的差只能是 \(1\) 或 \(2\)。也就是说，最优形状一定是“几乎连续”的整数段， 最多缺失一个值。
具有 \(m\) 项的基础形状是
$$\{2,3,\dots,m+1\},$$
其和为
$$T_m = 2+3+\cdots+(m+1)=\frac{m(m+3)}{2}.$$
这个值正是“最优拆分恰有 \(m\) 项”这一块的左端点。因此，对给定 \(n\)，正确的块编号是
$$m=\max\left\{r:\frac{r(r+3)}{2}\le n\right\}.$$
代码先用
$$m\approx \frac{\sqrt{8n+9}-3}{2}$$
做整数平方根估计，再用少量整数修正消除舍入误差。
令
$$n=T_m+s,\qquad 0\le s\le m+1.$$
由于
$$T_{m+1}=\frac{(m+1)(m+4)}{2}=T_m+m+2,$$
完整的第 \(m\) 块就是区间
$$T_m \le n \le T_{m+1}-1=\frac{(m+1)(m+4)}{2}-1.$$
在整个区间里，最优拆分的项数保持不变：
$$m(n)=m.$$
若 \(0\le s\le m\)，最优拆分由 \(\{2,3,\dots,m+2\}\) 删除一个数得到：
$$\{2,3,\dots,m+2\}\setminus\{m+2-s\}.$$
它的和为
$$ \left(\sum_{j=2}^{m+2} j\right)-(m+2-s) = \frac{m(m+3)}{2}+s = n, $$
乘积为
$$f(n)=\frac{(m+2)!}{m+2-s}.$$
因此
$$f(n)m(n)=m\frac{(m+2)!}{m+2-s},\qquad 0\le s\le m.$$
若 \(s=m+1\)，那么“要删除的数”会变成 \(1\)，这不属于上面的模式，于是最优拆分变成
$$\{3,4,\dots,m+1,m+3\}.$$
此时
$$f(n)=\frac{(m+3)!}{2(m+2)},$$
从而
$$f(n)m(n)=m\frac{(m+3)!}{2(m+2)}.$$
这正是三个解法文件实现的分段公式。代码把 \(s=m\) 单独写成一个分支，但从数学上说，它只是第一条 公式中分母为 \(2\) 的特例。
有
$$T_3=\frac{3\cdot 6}{2}=9,\qquad T_4=\frac{4\cdot 7}{2}=14,$$
所以 \(m=3\)，\(s=1\)。最优拆分为
$$\{2,3,4,5\}\setminus\{4\}=\{2,3,5\}.$$
于是
$$f(10)=2\cdot 3\cdot 5=30,\qquad m(10)=3,\qquad f(10)m(10)=90,$$
这与 C++ 校验点完全一致。
对完整块，先求 \(0\le s\le m\) 的 \(m+1\) 项之和：
$$ \sum_{s=0}^{m} m\frac{(m+2)!}{m+2-s} = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d}, $$
这里用了重标记 \(d=m+2-s\)。块的最后一个点额外贡献
$$m\frac{(m+3)!}{2(m+2)}.$$
因此完整第 \(m\) 块的贡献是
$$ B_m = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d} + m\frac{(m+3)!}{2(m+2)}. $$
这就是为什么实现中只需要维护一个滚动阶乘和一个滚动的逆元调和和。
由于 \(P\) 是素数，且所有分母都满足 \(2\le d\le m_{\max}+3 \lt P\)，所以它们在模 \(P\) 下都可逆。 代码用如下递推在线性时间内预处理：
$$\mathrm{inv}[1]=1,\qquad \mathrm{inv}[i]=-\left\lfloor\frac{P}{i}\right\rfloor\mathrm{inv}[P\bmod i]\pmod{P}.$$
这来自于 \(P=qi+r\)，于是 \(r\equiv -qi\pmod P\)。逆元表建好后，每个完整块都只需 \(O(1)\) 的模运算。
C++、Python、Java 三个版本的结构完全一致。它们先求 \(m_{\max}=\max\{m:T_m\le N\}\)，再预处理到 \(m_{\max}+3\) 为止的模逆元。主循环中持续维护
$$\texttt{fact}=(m+2)!\pmod P,\qquad \texttt{harmonic}=\sum_{d=2}^{m+2}\frac{1}{d}\pmod P.$$
对每个 \(m\)，代码都知道块起点、块终点以及该块还有多少落在目标范围内。完整块直接套用闭式；只有最后一块可能不完整， 这时才显式累加所需的逆元区间。
C++ 文件还用小规模精确值验证推导：
$$f(5)m(5)=12,\qquad f(10)m(10)=90,\qquad \sum_{n=1}^{100} f(n)m(n)=1683550844462.$$
因为 \(T_m\sim m^2/2\)，所以最大块编号满足 \(m_{\max}=\Theta(\sqrt{N})\)。逆元预处理、阶乘推进和整块遍历总共需要 \(O(\sqrt{N})\) 时间。逆元数组占用 \(O(\sqrt{N})\) 空间。又因为只有最后一个块可能是部分块，因此不会出现额外的隐藏因子。
Для каждого положительного целого \(n\) обозначим через \(f(n)\) максимальное произведение, которое можно получить из разбиения числа \(n\) на различные положительные слагаемые, а через \(m(n)\) — число слагаемых в оптимальном разбиении. В задаче Euler 374 требуется вычислить
$$M(N)=\sum_{n=1}^{N} f(n)m(n)$$
при \(N=10^{14}\) по модулю
$$P=982451653.$$
Локальные реализации на C++, Python и Java не перебирают разбиения напрямую: они используют простую блочную структуру оптимальных наборов.
Запишем оптимальное разбиение с \(k\) частями в виде
$$a_1 \lt a_2 \lt \cdots \lt a_k,\qquad a_1+\cdots+a_k=n.$$
Если некоторый соседний разрыв не меньше \(3\), то есть \(a_{i+1}-a_i\ge 3\), то замена \((a_i,a_{i+1})\) на \((a_i+1,a_{i+1}-1)\) сохраняет сумму и различность частей, но увеличивает произведение, поскольку
$$ (a_i+1)(a_{i+1}-1)-a_i a_{i+1} = a_{i+1}-a_i-1 \gt 0. $$
Следовательно, в оптимальном разбиении разности соседних частей могут быть только \(1\) или \(2\). Значит, победитель имеет вид почти непрерывного отрезка целых чисел с не более чем одним пропуском.
Базовая форма с \(m\) частями равна
$$\{2,3,\dots,m+1\},$$
и её сумма равна
$$T_m = 2+3+\cdots+(m+1)=\frac{m(m+3)}{2}.$$
Именно это значение является левой границей блока, в котором оптимальное разбиение имеет ровно \(m\) частей. Поэтому
$$m=\max\left\{r:\frac{r(r+3)}{2}\le n\right\}.$$
В коде сначала берётся приближение
$$m\approx \frac{\sqrt{8n+9}-3}{2},$$
а затем оно исправляется несколькими целочисленными шагами.
Пишем
$$n=T_m+s,\qquad 0\le s\le m+1.$$
Так как
$$T_{m+1}=\frac{(m+1)(m+4)}{2}=T_m+m+2,$$
полный блок с индексом \(m\) — это интервал
$$T_m \le n \le T_{m+1}-1=\frac{(m+1)(m+4)}{2}-1.$$
На всём этом интервале число частей оптимального разбиения постоянно:
$$m(n)=m.$$
Если \(0\le s\le m\), оптимальное разбиение получается из множества \(\{2,3,\dots,m+2\}\) удалением ровно одного числа:
$$\{2,3,\dots,m+2\}\setminus\{m+2-s\}.$$
Его сумма равна
$$ \left(\sum_{j=2}^{m+2} j\right)-(m+2-s) = \frac{m(m+3)}{2}+s = n, $$
а произведение равно
$$f(n)=\frac{(m+2)!}{m+2-s}.$$
Следовательно,
$$f(n)m(n)=m\frac{(m+2)!}{m+2-s},\qquad 0\le s\le m.$$
Если \(s=m+1\), то удалять пришлось бы число \(1\), поэтому форма меняется на
$$\{3,4,\dots,m+1,m+3\}.$$
Тогда
$$f(n)=\frac{(m+3)!}{2(m+2)},$$
и потому
$$f(n)m(n)=m\frac{(m+3)!}{2(m+2)}.$$
Именно эта кусочная формула реализована во всех трёх файлах. Случай \(s=m\) в коде выделен отдельно, но математически это просто случай знаменателя \(2\) в первой формуле.
Имеем
$$T_3=\frac{3\cdot 6}{2}=9,\qquad T_4=\frac{4\cdot 7}{2}=14,$$
значит, \(m=3\) и \(s=1\). Оптимальное разбиение равно
$$\{2,3,4,5\}\setminus\{4\}=\{2,3,5\}.$$
Отсюда
$$f(10)=2\cdot 3\cdot 5=30,\qquad m(10)=3,\qquad f(10)m(10)=90,$$
что совпадает с проверкой в C++-версии.
Для полного блока сначала суммируются \(m+1\) значений при \(0\le s\le m\):
$$ \sum_{s=0}^{m} m\frac{(m+2)!}{m+2-s} = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d}, $$
где сделана замена \(d=m+2-s\). Последняя точка блока добавляет ещё
$$m\frac{(m+3)!}{2(m+2)}.$$
Поэтому полный вклад блока равен
$$ B_m = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d} + m\frac{(m+3)!}{2(m+2)}. $$
Именно поэтому реализации достаточно поддерживать бегущий факториал и бегущую гармоническую сумму обратных по модулю.
Так как \(P\) — простое число и все знаменатели удовлетворяют \(2\le d\le m_{\max}+3 \lt P\), все нужные обратные существуют по модулю \(P\). Код вычисляет их линейно по рекуррентной формуле
$$\mathrm{inv}[1]=1,\qquad \mathrm{inv}[i]=-\left\lfloor\frac{P}{i}\right\rfloor\mathrm{inv}[P\bmod i]\pmod{P}.$$
Она следует из разложения \(P=qi+r\), то есть \(r\equiv -qi\pmod P\). После построения таблицы каждый полный блок обрабатывается за \(O(1)\) модульных операций.
Структура решений на C++, Python и Java одинакова. Сначала вычисляется \(m_{\max}=\max\{m:T_m\le N\}\), затем предвычисляются обратные элементы до \(m_{\max}+3\). В главном цикле поддерживаются величины
$$\texttt{fact}=(m+2)!\pmod P,\qquad \texttt{harmonic}=\sum_{d=2}^{m+2}\frac{1}{d}\pmod P.$$
Для каждого \(m\) программе известны начало блока, конец блока и длина части блока, которая ещё лежит в нужном диапазоне. Полные блоки используют закрытую формулу сразу; только последний блок может оказаться неполным, и тогда код явно суммирует нужный отрезок обратных.
Файл C++ дополнительно проверяет вывод на малых точных значениях:
$$f(5)m(5)=12,\qquad f(10)m(10)=90,\qquad \sum_{n=1}^{100} f(n)m(n)=1683550844462.$$
Поскольку \(T_m\sim m^2/2\), максимальный индекс блока удовлетворяет \(m_{\max}=\Theta(\sqrt{N})\). Предвычисление обратных, обновление факториала и проход по всем блокам занимают \(O(\sqrt{N})\) времени. Таблица обратных требует \(O(\sqrt{N})\) памяти. Поскольку неполным может быть только последний блок, скрытого дополнительного множителя не возникает.
لكل عدد صحيح موجب \(n\)، نرمز بـ \(f(n)\) إلى أكبر حاصل ضرب يمكن الحصول عليه من تجزئة \(n\) إلى أعداد صحيحة موجبة متميزة، ونرمز بـ \(m(n)\) إلى عدد الأجزاء في تجزئة مثلى. المطلوب في Euler 374 هو حساب
$$M(N)=\sum_{n=1}^{N} f(n)m(n)$$
عند \(N=10^{14}\)، مع أخذ النتيجة بترديد
$$P=982451653.$$
حلول C++ وPython وJava الموجودة محليًا لا تبحث في جميع التجزئات، بل تعتمد على أن التجزئة المثلى تقع داخل كتل بسيطة ذات صيغة مغلقة.
لنكتب تجزئة مثلى فيها \(k\) أجزاء على الصورة
$$a_1 \lt a_2 \lt \cdots \lt a_k,\qquad a_1+\cdots+a_k=n.$$
إذا وُجد فرق متجاور لا يقل عن \(3\)، أي \(a_{i+1}-a_i\ge 3\)، فإن استبدال \((a_i,a_{i+1})\) بـ \((a_i+1,a_{i+1}-1)\) يحافظ على المجموع وعلى تميّز الأجزاء، لكنه يزيد حاصل الضرب لأن
$$ (a_i+1)(a_{i+1}-1)-a_i a_{i+1} = a_{i+1}-a_i-1 \gt 0. $$
إذًا في التجزئة المثلى لا يمكن أن تكون الفروق المتجاورة إلا \(1\) أو \(2\). وهذا يعني أن الشكل الرابح هو مقطع من أعداد متقاربة جدًا مع احتمال وجود قيمة واحدة مفقودة فقط.
الشكل الأساسي الذي يحتوي على \(m\) أجزاء هو
$$\{2,3,\dots,m+1\},$$
ومجموعه
$$T_m = 2+3+\cdots+(m+1)=\frac{m(m+3)}{2}.$$
وهذه هي بداية الكتلة التي يكون فيها عدد أجزاء التجزئة المثلى مساويًا لـ \(m\). لذلك يكون
$$m=\max\left\{r:\frac{r(r+3)}{2}\le n\right\}.$$
يحسب الكود أولًا التقريب
$$m\approx \frac{\sqrt{8n+9}-3}{2},$$
ثم يصححه بخطوات صحيحة قليلة.
نكتب
$$n=T_m+s,\qquad 0\le s\le m+1.$$
وبما أن
$$T_{m+1}=\frac{(m+1)(m+4)}{2}=T_m+m+2,$$
فإن الكتلة الكاملة ذات الفهرس \(m\) هي
$$T_m \le n \le T_{m+1}-1=\frac{(m+1)(m+4)}{2}-1.$$
وعلى كامل هذا المجال يبقى عدد الأجزاء المثالي ثابتًا:
$$m(n)=m.$$
إذا كان \(0\le s\le m\)، فإن التجزئة المثلى تُستخرج من المجموعة \(\{2,3,\dots,m+2\}\) بحذف قيمة واحدة فقط:
$$\{2,3,\dots,m+2\}\setminus\{m+2-s\}.$$
ومجموعها يساوي
$$ \left(\sum_{j=2}^{m+2} j\right)-(m+2-s) = \frac{m(m+3)}{2}+s = n, $$
وحاصل ضربها هو
$$f(n)=\frac{(m+2)!}{m+2-s}.$$
إذن
$$f(n)m(n)=m\frac{(m+2)!}{m+2-s},\qquad 0\le s\le m.$$
أما إذا كان \(s=m+1\)، فالقيمة المحذوفة المفترضة ستكون \(1\)، ولذلك يتغير الشكل إلى
$$\{3,4,\dots,m+1,m+3\}.$$
وفي هذه الحالة
$$f(n)=\frac{(m+3)!}{2(m+2)},$$
ومن ثم
$$f(n)m(n)=m\frac{(m+3)!}{2(m+2)}.$$
وهذه هي بالضبط الصيغة القطعية المستخدمة في ملفات الحل الثلاثة. الحالة \(s=m\) مفصولة في الكود، لكنها رياضيًا ليست إلا حالة خاصة من الصيغة الأولى عندما يكون المقام \(2\).
لدينا
$$T_3=\frac{3\cdot 6}{2}=9,\qquad T_4=\frac{4\cdot 7}{2}=14,$$
إذًا \(m=3\) و\(s=1\). ومن ثم تكون التجزئة المثلى
$$\{2,3,4,5\}\setminus\{4\}=\{2,3,5\}.$$
وعليه
$$f(10)=2\cdot 3\cdot 5=30,\qquad m(10)=3,\qquad f(10)m(10)=90,$$
وهو نفس ناتج نقطة التحقق في ملف C++.
في كتلة كاملة نجمع أولًا القيم \(m+1\) التي تحقق \(0\le s\le m\):
$$ \sum_{s=0}^{m} m\frac{(m+2)!}{m+2-s} = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d}, $$
وذلك بعد إعادة الفهرسة \(d=m+2-s\). ثم تضيف آخر نقطة في الكتلة الحد
$$m\frac{(m+3)!}{2(m+2)}.$$
إذًا مساهمة الكتلة الكاملة هي
$$ B_m = m(m+2)!\sum_{d=2}^{m+2}\frac{1}{d} + m\frac{(m+3)!}{2(m+2)}. $$
ولهذا يكفي التنفيذ أن يحتفظ بعاملية جارية وبمجموع توافقي جاري لمقلوبات المقامات بترديد \(P\).
بما أن \(P\) عدد أولي، وجميع المقامات تحقق \(2\le d\le m_{\max}+3 \lt P\)، فإن كل المقامات قابلة للعكس modulo \(P\). يحسب الكود هذه المعكوسات مسبقًا في زمن خطي بالعلاقة
$$\mathrm{inv}[1]=1,\qquad \mathrm{inv}[i]=-\left\lfloor\frac{P}{i}\right\rfloor\mathrm{inv}[P\bmod i]\pmod{P}.$$
وتنتج هذه العلاقة من كتابة \(P=qi+r\)، وبالتالي \(r\equiv -qi\pmod P\). وبعد بناء جدول المعكوسات تصبح معالجة كل كتلة كاملة من رتبة \(O(1)\).
البنية العامة في C++ وPython وJava واحدة. أولًا يُحسب \(m_{\max}=\max\{m:T_m\le N\}\)، ثم تُحسب المعكوسات المعيارية حتى \(m_{\max}+3\). أثناء الحلقة الرئيسية يحافظ الكود على
$$\texttt{fact}=(m+2)!\pmod P,\qquad \texttt{harmonic}=\sum_{d=2}^{m+2}\frac{1}{d}\pmod P.$$
ولكل \(m\) يعرف البرنامج بداية الكتلة ونهايتها وطول الجزء الذي ما زال داخل المجال المطلوب. الكتل الكاملة تستخدم الصيغة المغلقة مباشرة، أما الكتلة الأخيرة فقط فقد تكون ناقصة، وحينها يُجمع مقطع المعكوسات المطلوب بصورة صريحة.
كما أن ملف C++ يختبر الاشتقاق على قيم دقيقة صغيرة:
$$f(5)m(5)=12,\qquad f(10)m(10)=90,\qquad \sum_{n=1}^{100} f(n)m(n)=1683550844462.$$
بما أن \(T_m\sim m^2/2\)، فإن أكبر فهرس كتلة يحقق \(m_{\max}=\Theta(\sqrt{N})\). لذلك فإن حساب المعكوسات، وتحديث العاملية، والمرور على جميع الكتل يأخذ إجمالًا \(O(\sqrt{N})\) زمنًا. جدول المعكوسات يستهلك \(O(\sqrt{N})\) ذاكرة. ولأن الكتلة الأخيرة وحدها قد تكون غير مكتملة، فلا يوجد عامل خفي إضافي.