Define
$$s(n)=\min\{m\ge 1 : n\mid m!\}.$$
Problem 549 asks for
$$S(N)=\sum_{n=2}^{N} s(n)$$
with \(N=10^8\). Computing \(s(n)\) independently for every \(n\) would repeat the same prime-divisibility work over and over, so the solution reorganizes the problem around prime powers and then propagates their thresholds with a sieve.
The decisive observation is that factorial divisibility is controlled prime by prime. Once the minimal factorial threshold is known for every prime power \(p^a\le N\), the value of \(s(n)\) is simply the largest threshold among the prime powers dividing \(n\).
If
$$n=\prod_{i=1}^{r} p_i^{a_i},$$
then \(n\mid m!\) is equivalent to requiring
$$v_{p_i}(m!)\ge a_i\qquad \text{for every } i.$$
So for one prime power we define
$$t(p,a)=\min\{m\ge 1 : v_p(m!)\ge a\}.$$
With this notation,
$$s(n)=\max_{1\le i\le r} t(p_i,a_i).$$
The reason is that the smallest usable factorial must satisfy every prime-power requirement at once, so it must be at least the largest of those lower bounds, and that largest lower bound is already sufficient for all the others.
For a fixed prime \(p\), Legendre's formula gives
$$v_p(m!)=\sum_{k\ge 1}\left\lfloor\frac{m}{p^k}\right\rfloor.$$
The sum is finite because the terms vanish when \(p^k>m\). It is also monotone in \(m\), so we can binary-search the first value where the exponent reaches \(a\).
A simple universal upper bound is
$$t(p,a)\le pa,$$
because already
$$v_p((pa)!)\ge \left\lfloor\frac{pa}{p}\right\rfloor=a.$$
Therefore the exact threshold for \(p^a\) always lies in the interval \([1,pa]\).
For exponent \(a=1\), there is nothing to search:
$$t(p,1)=p,$$
since \(p\mid p!\) and no smaller factorial contains the prime \(p\). For \(a\ge 2\), the threshold is the first \(m\) in \([1,pa]\) such that Legendre's sum reaches \(a\).
For example,
$$t(2,3)=4,\qquad t(3,2)=6,$$
because
$$v_2(4!)=2+1=3,\qquad v_3(6!)=2,$$
while the previous factorials still fall short.
Suppose \(t(p,a)\) is known for a prime power \(p^a\). Every integer divisible by \(p^a\) must satisfy
$$s(n)\ge t(p,a).$$
That means we do not need to refactor every \(n\) separately. Instead, we sweep through all multiples of \(p^a\) and record the maximum threshold contributed by any prime power.
Concretely, every multiple of \(p\) receives at least the value \(p\). Every multiple of \(p^2\) receives at least \(t(p,2)\), every multiple of \(p^3\) receives at least \(t(p,3)\), and so on for all powers up to \(N\).
After all prime powers have been processed, the stored value at \(n\) is exactly
$$\max_{p^a\mid n} t(p,a)=s(n).$$
We have
$$72=2^3\cdot 3^2.$$
From the previous step,
$$t(2,3)=4,\qquad t(3,2)=6.$$
Therefore
$$s(72)=\max(4,6)=6.$$
This is correct because
$$v_2(6!)=3+1=4\ge 3,\qquad v_3(6!)=2\ge 2,$$
so \(72\mid 6!\). But \(5!\) is not enough, since \(v_3(5!)=1\). The same logic scales to every \(n\le N\): each prime power contributes one lower bound, and the largest one determines \(s(n)\).
The C++, Python, and Java implementations use the same pipeline. First they generate all primes up to \(N\) with an odd-only sieve: the prime \(2\) is handled separately, and only odd candidates are stored and marked. This keeps the prime-generation step compact and efficient.
Next the implementation allocates an array that stores, for each integer \(n\), the best lower bound for \(s(n)\) seen so far. For every prime \(p\), all multiples of \(p\) are updated with the value \(p\). Then the code walks through the higher powers \(p^2,p^3,\dots\) up to \(N\). For each such power, it computes the exact threshold with a binary search based on Legendre's formula and updates every multiple of that prime power by taking the maximum.
When all prime powers have propagated their thresholds, the array entry at \(n\) is exactly \(s(n)\). The final pass sums these values for \(2\le n\le N\). The C++ implementation also verifies the small checkpoint
$$S(100)=2012$$
before performing the full computation.
Prime generation with the odd-only sieve costs \(O(N\log\log N)\) time. The updates over multiples of primes contribute
$$N\sum_{p\le N}\frac{1}{p}=O(N\log\log N).$$
The extra sweeps for higher powers \(p^a\) with \(a\ge 2\) contribute
$$N\sum_{p}\sum_{a\ge 2,\ p^a\le N}\frac{1}{p^a},$$
which is only \(O(N)\) because the geometric tail for each prime is summable. The binary searches for individual prime powers are comparatively small and do not change the main bound. So the overall algorithm runs in \(O(N\log\log N)\) time and uses \(O(N)\) memory.
Wir definieren
$$s(n)=\min\{m\ge 1 : n\mid m!\}.$$
In Problem 549 soll berechnet werden
$$S(N)=\sum_{n=2}^{N} s(n)$$
für \(N=10^8\). Würde man \(s(n)\) für jedes \(n\) getrennt bestimmen, würde man dieselbe Primfaktor-Arbeit ständig wiederholen. Daher ordnet die Lösung das Problem nach Primzahlpotenzen und verteilt deren Schwellenwerte siebartig auf alle Vielfachen.
Der zentrale Punkt ist, dass Teilbarkeit in Fakultäten primweise kontrolliert wird. Sobald man für jede Primzahlpotenz \(p^a\le N\) die kleinste passende Fakultätsgrenze kennt, ist \(s(n)\) einfach der größte dieser Werte unter den Primzahlpotenzen, die \(n\) teilen.
Ist
$$n=\prod_{i=1}^{r} p_i^{a_i},$$
dann gilt \(n\mid m!\) genau dann, wenn
$$v_{p_i}(m!)\ge a_i\qquad \text{für alle } i.$$
Für eine einzelne Primzahlpotenz definieren wir also
$$t(p,a)=\min\{m\ge 1 : v_p(m!)\ge a\}.$$
Damit folgt
$$s(n)=\max_{1\le i\le r} t(p_i,a_i).$$
Der Grund ist, dass die kleinste zulässige Fakultät alle Primzahlpotenz-Bedingungen gleichzeitig erfüllen muss. Sie muss also mindestens so groß sein wie die härteste Einzelbedingung, und genau diese größte Untergrenze reicht dann auch aus.
Für eine feste Primzahl \(p\) liefert die Legendre-Formel
$$v_p(m!)=\sum_{k\ge 1}\left\lfloor\frac{m}{p^k}\right\rfloor.$$
Die Summe ist endlich, weil die Terme verschwinden, sobald \(p^k>m\) wird. Außerdem wächst sie monoton mit \(m\), sodass man die erste passende Stelle per Binärsuche finden kann.
Eine einfache obere Schranke ist
$$t(p,a)\le pa,$$
denn bereits
$$v_p((pa)!)\ge \left\lfloor\frac{pa}{p}\right\rfloor=a.$$
Damit liegt der exakte Schwellenwert für \(p^a\) immer im Intervall \([1,pa]\).
Für \(a=1\) braucht man keine Suche:
$$t(p,1)=p,$$
denn \(p\mid p!\), aber keine kleinere Fakultät enthält den Primfaktor \(p\). Für \(a\ge 2\) wird der kleinste Wert \(m\) in \([1,pa]\) gesucht, für den die Legendre-Summe mindestens \(a\) erreicht.
Zum Beispiel gilt
$$t(2,3)=4,\qquad t(3,2)=6,$$
weil
$$v_2(4!)=2+1=3,\qquad v_3(6!)=2,$$
während die jeweils vorherige Fakultät noch nicht genügt.
Sei \(t(p,a)\) für eine Primzahlpotenz \(p^a\) bekannt. Dann muss für jedes durch \(p^a\) teilbare \(n\) gelten:
$$s(n)\ge t(p,a).$$
Deshalb muss man nicht jedes \(n\) neu faktorisieren. Stattdessen läuft man über alle Vielfachen von \(p^a\) und speichert die größte bisher bekannte Untergrenze.
Konkret erhält jedes Vielfache von \(p\) mindestens den Wert \(p\). Jedes Vielfache von \(p^2\) erhält mindestens \(t(p,2)\), jedes Vielfache von \(p^3\) mindestens \(t(p,3)\) und so weiter, solange \(p^a\le N\).
Nachdem alle Primzahlpotenzen verarbeitet sind, steht an Position \(n\) genau
$$\max_{p^a\mid n} t(p,a)=s(n).$$
Es gilt
$$72=2^3\cdot 3^2.$$
Aus dem vorherigen Schritt kennen wir
$$t(2,3)=4,\qquad t(3,2)=6.$$
Daher ist
$$s(72)=\max(4,6)=6.$$
Das stimmt, denn
$$v_2(6!)=3+1=4\ge 3,\qquad v_3(6!)=2\ge 2,$$
also gilt \(72\mid 6!\). Dagegen reicht \(5!\) nicht, weil \(v_3(5!)=1\) ist. Genau dieselbe Logik skaliert auf jedes \(n\le N\): Jede Primzahlpotenz liefert eine Untergrenze, und die größte davon bestimmt \(s(n)\).
Die Implementierungen in C++, Python und Java folgen derselben Struktur. Zuerst erzeugen sie alle Primzahlen bis \(N\) mit einem Sieb nur über ungerade Zahlen: Die \(2\) wird separat behandelt, und gespeichert sowie markiert werden nur ungerade Kandidaten. Das spart Speicher und passt gut zu den späteren Schleifen über Primzahlpotenzen.
Danach wird ein Feld angelegt, das für jedes \(n\) die bislang beste Untergrenze für \(s(n)\) speichert. Für jede Primzahl \(p\) werden alle Vielfachen von \(p\) mit dem Wert \(p\) aktualisiert. Anschließend geht der Code die höheren Potenzen \(p^2,p^3,\dots\) bis \(N\) durch. Für jede dieser Potenzen wird der exakte Schwellenwert per Binärsuche auf Basis der Legendre-Formel berechnet und in alle entsprechenden Vielfachen per Maximum eingetragen.
Wenn alle Primzahlpotenzen ihre Schwellen verteilt haben, steht im Feld an Position \(n\) genau \(s(n)\). Zum Schluss werden diese Werte für \(2\le n\le N\) aufsummiert. Die C++-Implementierung prüft zuvor zusätzlich den bekannten Kontrollwert
$$S(100)=2012.$$
Die Primzahlerzeugung mit dem ungeraden Sieb kostet \(O(N\log\log N)\) Zeit. Die Aktualisierungen über alle Primzahl-Vielfachen tragen
$$N\sum_{p\le N}\frac{1}{p}=O(N\log\log N)$$
bei. Die zusätzlichen Durchläufe über höhere Potenzen \(p^a\) mit \(a\ge 2\) liefern
$$N\sum_{p}\sum_{a\ge 2,\ p^a\le N}\frac{1}{p^a},$$
und das ist nur \(O(N)\), weil die geometrische Restreihe für jede Primzahl konvergiert. Die Binärsuchen für einzelne Primzahlpotenzen sind im Vergleich klein und ändern die Hauptschranke nicht. Insgesamt läuft das Verfahren also in \(O(N\log\log N)\) Zeit und benötigt \(O(N)\) Speicher.
Şunu tanımlayalım:
$$s(n)=\min\{m\ge 1 : n\mid m!\}.$$
Problem 549 için istenen büyüklük
$$S(N)=\sum_{n=2}^{N} s(n)$$
ve burada \(N=10^8\)'dir. Her \(n\) için \(s(n)\)'yi bağımsız hesaplamak aynı asal çarpan bilgisini tekrar tekrar üretir. Bu yüzden çözüm, problemi asal kuvvet eşiklerine ayırır ve sonra bu eşikleri eleme benzeri bir yayma ile tüm sayılara aktarır.
Ana gözlem şudur: Bir sayının faktöriyelde bölünüp bölünmemesi asal bazında belirlenir. \(p^a\le N\) olan her asal kuvvet için gereken en küçük faktöriyel eşiğini bildiğimiz anda, \(s(n)\) değeri sadece \(n\)'yi bölen asal kuvvetler arasındaki en büyük eşiktir.
Eğer
$$n=\prod_{i=1}^{r} p_i^{a_i},$$
ise \(n\mid m!\) olması tam olarak şu koşulla eşdeğerdir:
$$v_{p_i}(m!)\ge a_i\qquad \text{her } i \text{ için}.$$
Bu yüzden tek bir asal kuvvet için
$$t(p,a)=\min\{m\ge 1 : v_p(m!)\ge a\}$$
tanımını yaparız. Böylece
$$s(n)=\max_{1\le i\le r} t(p_i,a_i)$$
olur. Çünkü gerekli en küçük faktöriyel, bütün asal kuvvet koşullarını aynı anda sağlamalıdır; dolayısıyla en zor koşul kadar büyük olmak zorundadır ve bu en büyük alt sınır diğerlerinin hepsini de otomatik olarak karşılar.
Sabit bir asal \(p\) için Legendre formülü
$$v_p(m!)=\sum_{k\ge 1}\left\lfloor\frac{m}{p^k}\right\rfloor$$
şeklindedir. \(p^k>m\) olduktan sonra terimler sıfır olduğu için toplam sonludur. Ayrıca \(m\) arttıkça bu değer monoton arttığından, doğru eşiği ikili arama ile bulabiliriz.
Basit bir üst sınır
$$t(p,a)\le pa$$
şeklindedir; çünkü en azından
$$v_p((pa)!)\ge \left\lfloor\frac{pa}{p}\right\rfloor=a.$$
Dolayısıyla \(p^a\) için tam eşik her zaman \([1,pa]\) aralığındadır.
\(a=1\) için arama yapmaya gerek yoktur:
$$t(p,1)=p,$$
çünkü \(p\mid p!\) olur ve daha küçük hiçbir faktöriyel \(p\) asalı içermez. \(a\ge 2\) olduğunda ise, Legendre toplamının ilk kez \(a\)'ya ulaştığı \(m\) değeri \([1,pa]\) aralığında ikili arama ile bulunur.
Örneğin
$$t(2,3)=4,\qquad t(3,2)=6,$$
çünkü
$$v_2(4!)=2+1=3,\qquad v_3(6!)=2,$$
ama bir önceki faktöriyeller hâlâ yetersizdir.
Bir asal kuvvet \(p^a\) için \(t(p,a)\) biliniyorsa, \(p^a\)'ya bölünebilen her \(n\) için
$$s(n)\ge t(p,a)$$
olmak zorundadır. Bu da her \(n\)'yi ayrı ayrı çarpanlara ayırmak yerine, \(p^a\)'nın tüm katları üzerinde dolaşıp görülen en büyük eşiği saklamanın yeterli olduğu anlamına gelir.
Somut olarak, \(p\)'nin tüm katları en az \(p\) değerini alır. \(p^2\)'nin tüm katları en az \(t(p,2)\), \(p^3\)'ün tüm katları en az \(t(p,3)\) alır ve bu işlem \(p^a\le N\) olduğu sürece devam eder.
Bütün asal kuvvetler işlendiğinde, \(n\) konumunda saklanan değer tam olarak
$$\max_{p^a\mid n} t(p,a)=s(n)$$
olur.
Burada
$$72=2^3\cdot 3^2.$$
Önceki adımdan
$$t(2,3)=4,\qquad t(3,2)=6$$
olduğunu biliyoruz. O halde
$$s(72)=\max(4,6)=6.$$
Gerçekten de
$$v_2(6!)=3+1=4\ge 3,\qquad v_3(6!)=2\ge 2,$$
dolayısıyla \(72\mid 6!\). Buna karşılık \(5!\) yeterli değildir; çünkü \(v_3(5!)=1\) kalır. Aynı mantık tüm \(n\le N\) için geçerlidir: Her asal kuvvet bir alt sınır üretir ve en büyük olan \(s(n)\)'yi belirler.
C++, Python ve Java uygulamaları aynı akışı izler. Önce yalnızca tek sayıları tutan bir asal eleği ile \(N\)'ye kadar bütün asallar üretilir: \(2\) ayrı ele alınır, depolanan ve işaretlenen adaylar ise yalnızca tek sayılardır. Bu yaklaşım hem alanı azaltır hem de sonraki asal kuvvet döngüleriyle doğal biçimde uyumludur.
Daha sonra, her \(n\) için şimdiye kadar görülen en iyi alt sınırı tutan bir dizi oluşturulur. Her asal \(p\) için \(p\)'nin tüm katları \(p\) değeriyle güncellenir. Ardından kod, \(p^2,p^3,\dots\) biçimindeki daha yüksek kuvvetleri \(N\)'ye kadar gezer. Her böyle kuvvet için, Legendre formülüne dayalı ikili arama ile tam eşik hesaplanır ve o asal kuvvetin tüm katlarına maksimum alınarak yazılır.
Tüm asal kuvvetler eşiklerini yaydıktan sonra dizideki \(n\). değer tam olarak \(s(n)\) olur. Son geçişte bu değerler \(2\le n\le N\) için toplanır. C++ uygulaması, tam hesaplamadan önce şu küçük kontrol değerini de doğrular:
$$S(100)=2012.$$
Tek sayılı asal eleği \(O(N\log\log N)\) zamanda çalışır. Asalların katları üzerindeki güncellemelerin toplam maliyeti
$$N\sum_{p\le N}\frac{1}{p}=O(N\log\log N)$$
olur. \(a\ge 2\) olan daha yüksek kuvvetler için ek taramalar ise
$$N\sum_{p}\sum_{a\ge 2,\ p^a\le N}\frac{1}{p^a}$$
şeklindedir ve her asal için geometrik kuyruk yakınsak olduğundan bu katkı sadece \(O(N)\)'dir. Tek tek asal kuvvetler için yapılan ikili aramalar daha küçüktür ve ana sınırı değiştirmez. Sonuç olarak toplam zaman \(O(N\log\log N)\), bellek kullanımı ise \(O(N)\)'dir.
Definimos
$$s(n)=\min\{m\ge 1 : n\mid m!\}.$$
En el Problema 549 hay que calcular
$$S(N)=\sum_{n=2}^{N} s(n)$$
con \(N=10^8\). Si se intentara obtener \(s(n)\) por separado para cada \(n\), se repetiría una y otra vez la misma información sobre divisibilidad prima. La solución evita esa redundancia trabajando con potencias primas y propagando luego sus umbrales mediante una criba.
La idea clave es que la divisibilidad de un factorial se decide primo a primo. En cuanto conocemos el umbral mínimo de factorial para cada potencia prima \(p^a\le N\), el valor de \(s(n)\) es simplemente el mayor de los umbrales asociados a las potencias primas que dividen a \(n\).
Si
$$n=\prod_{i=1}^{r} p_i^{a_i},$$
entonces \(n\mid m!\) equivale exactamente a exigir
$$v_{p_i}(m!)\ge a_i\qquad \text{para todo } i.$$
Para una sola potencia prima definimos
$$t(p,a)=\min\{m\ge 1 : v_p(m!)\ge a\}.$$
Con esta notación se obtiene
$$s(n)=\max_{1\le i\le r} t(p_i,a_i).$$
La razón es que el menor factorial válido debe satisfacer simultáneamente todas las restricciones de exponentes primos; por tanto, tiene que ser al menos tan grande como la condición individual más exigente, y esa mayor cota inferior ya basta para cubrir las demás.
Para un primo fijo \(p\), la fórmula de Legendre dice
$$v_p(m!)=\sum_{k\ge 1}\left\lfloor\frac{m}{p^k}\right\rfloor.$$
La suma es finita porque los términos se vuelven \(0\) cuando \(p^k>m\). Además, es monótona respecto de \(m\), así que podemos buscar por binaria el primer valor que alcance el exponente \(a\).
Una cota superior muy simple es
$$t(p,a)\le pa,$$
ya que
$$v_p((pa)!)\ge \left\lfloor\frac{pa}{p}\right\rfloor=a.$$
Por lo tanto, el umbral exacto para \(p^a\) siempre está dentro del intervalo \([1,pa]\).
Cuando \(a=1\), no hace falta buscar:
$$t(p,1)=p,$$
porque \(p\mid p!\) y ningún factorial menor contiene todavía ese primo. Para \(a\ge 2\), se busca el menor \(m\) en \([1,pa]\) tal que la suma de Legendre alcance al menos \(a\).
Por ejemplo,
$$t(2,3)=4,\qquad t(3,2)=6,$$
porque
$$v_2(4!)=2+1=3,\qquad v_3(6!)=2,$$
mientras que los factoriales inmediatamente anteriores aún son insuficientes.
Supongamos que ya conocemos \(t(p,a)\) para una potencia prima \(p^a\). Entonces todo entero divisible por \(p^a\) debe cumplir
$$s(n)\ge t(p,a).$$
Eso significa que no hace falta factorizar cada \(n\) por separado. En su lugar, recorremos todos los múltiplos de \(p^a\) y guardamos el mayor umbral aportado por cualquier potencia prima.
En concreto, cada múltiplo de \(p\) recibe al menos el valor \(p\). Cada múltiplo de \(p^2\) recibe al menos \(t(p,2)\), cada múltiplo de \(p^3\) recibe al menos \(t(p,3)\), y así sucesivamente mientras \(p^a\le N\).
Después de procesar todas las potencias primas, el valor almacenado en \(n\) es exactamente
$$\max_{p^a\mid n} t(p,a)=s(n).$$
Tenemos
$$72=2^3\cdot 3^2.$$
De los pasos anteriores se sigue que
$$t(2,3)=4,\qquad t(3,2)=6.$$
Por tanto,
$$s(72)=\max(4,6)=6.$$
Esto es correcto porque
$$v_2(6!)=3+1=4\ge 3,\qquad v_3(6!)=2\ge 2,$$
y por ello \(72\mid 6!\). En cambio, \(5!\) no basta, ya que \(v_3(5!)=1\). La misma lógica vale para todo \(n\le N\): cada potencia prima aporta una cota inferior y la mayor de ellas determina \(s(n)\).
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero generan todos los primos hasta \(N\) con una criba que guarda solo candidatos impares: el \(2\) se trata por separado, y únicamente se almacenan y marcan números impares. Eso reduce el almacenamiento de la criba y simplifica los recorridos posteriores.
Después, la implementación crea un arreglo que guarda, para cada \(n\), la mejor cota inferior conocida hasta ese momento para \(s(n)\). Para cada primo \(p\), todos los múltiplos de \(p\) se actualizan con el valor \(p\). Luego el código recorre las potencias superiores \(p^2,p^3,\dots\) hasta \(N\). Para cada una calcula el umbral exacto con una búsqueda binaria basada en la fórmula de Legendre y actualiza todos sus múltiplos tomando el máximo.
Una vez que todas las potencias primas han propagado sus umbrales, la entrada correspondiente a \(n\) es exactamente \(s(n)\). La pasada final solo suma esos valores para \(2\le n\le N\). La implementación en C++ además verifica antes el pequeño punto de control
$$S(100)=2012.$$
La generación de primos mediante la criba de impares cuesta \(O(N\log\log N)\) tiempo. Las actualizaciones sobre múltiplos de primos aportan
$$N\sum_{p\le N}\frac{1}{p}=O(N\log\log N).$$
Los barridos adicionales para potencias superiores \(p^a\) con \(a\ge 2\) suman
$$N\sum_{p}\sum_{a\ge 2,\ p^a\le N}\frac{1}{p^a},$$
y eso es solo \(O(N)\), porque la cola geométrica para cada primo es convergente. Las búsquedas binarias de potencias primas individuales son pequeñas en comparación y no cambian la cota dominante. Por tanto, el método completo funciona en \(O(N\log\log N)\) tiempo y utiliza \(O(N)\) memoria.
定义
$$s(n)=\min\{m\ge 1 : n\mid m!\}.$$
第 549 题要求计算
$$S(N)=\sum_{n=2}^{N} s(n)$$
其中 \(N=10^8\)。如果把每个 \(n\) 都单独处理一遍，就会无数次重复同样的素因子分析。真正高效的办法，是先处理所有素数幂 \(p^a\) 的“最小阶乘阈值”，再把这些阈值用筛法传播到所有相关整数上。
核心事实是：阶乘的整除性是按素数逐个控制的。只要知道每个素数幂 \(p^a\le N\) 需要多大的阶乘才能被吸收，那么任意 \(n\) 的 \(s(n)\) 就只是所有整除 \(n\) 的素数幂阈值中的最大者。
若
$$n=\prod_{i=1}^{r} p_i^{a_i},$$
那么 \(n\mid m!\) 当且仅当对每个素数都有
$$v_{p_i}(m!)\ge a_i\qquad \text{对所有 } i.$$
于是对单个素数幂定义
$$t(p,a)=\min\{m\ge 1 : v_p(m!)\ge a\}.$$
这样就有
$$s(n)=\max_{1\le i\le r} t(p_i,a_i).$$
原因很直接：要让 \(m!\) 同时包含 \(n\) 的所有素数幂部分，\(m\) 至少要达到其中最苛刻的那个门槛；而一旦达到这个最大门槛，其余较小条件也自然全部满足。
对固定素数 \(p\)，Legendre 公式给出
$$v_p(m!)=\sum_{k\ge 1}\left\lfloor\frac{m}{p^k}\right\rfloor.$$
当 \(p^k>m\) 以后，后面的项全部为 \(0\)，所以这是一个有限和。更重要的是，它随 \(m\) 单调不减，因此可以对答案做二分查找。
一个很方便的统一上界是
$$t(p,a)\le pa,$$
因为至少有
$$v_p((pa)!)\ge \left\lfloor\frac{pa}{p}\right\rfloor=a.$$
所以 \(p^a\) 的精确阈值一定落在 \([1,pa]\) 之内。
当 \(a=1\) 时根本不用搜索：
$$t(p,1)=p,$$
因为 \(p\mid p!\)，而任何更小的阶乘都还不包含素数 \(p\)。当 \(a\ge 2\) 时，就在 \([1,pa]\) 上二分，寻找第一个使 Legendre 和达到至少 \(a\) 的 \(m\)。
例如，
$$t(2,3)=4,\qquad t(3,2)=6,$$
因为
$$v_2(4!)=2+1=3,\qquad v_3(6!)=2,$$
而前一个阶乘还不够。
如果某个素数幂 \(p^a\) 的阈值 \(t(p,a)\) 已经求出，那么所有满足 \(p^a\mid n\) 的整数都必须有
$$s(n)\ge t(p,a).$$
这意味着没有必要把每个 \(n\) 再重新分解一遍。更高效的做法是：对每个素数幂 \(p^a\)，遍历它的所有倍数，把当前位置记录的门槛更新为目前见过的最大值。
具体来说，所有 \(p\) 的倍数至少要写入 \(p\)；所有 \(p^2\) 的倍数至少要写入 \(t(p,2)\)；所有 \(p^3\) 的倍数至少要写入 \(t(p,3)\)；只要 \(p^a\le N\)，这个过程就继续。
等所有素数幂都处理完之后，位置 \(n\) 上保存的恰好就是
$$\max_{p^a\mid n} t(p,a)=s(n).$$
先分解得到
$$72=2^3\cdot 3^2.$$
由前面的计算可知
$$t(2,3)=4,\qquad t(3,2)=6.$$
因此
$$s(72)=\max(4,6)=6.$$
这确实正确，因为
$$v_2(6!)=3+1=4\ge 3,\qquad v_3(6!)=2\ge 2,$$
所以 \(72\mid 6!\)。但 \(5!\) 还不够，因为 \(v_3(5!)=1\)。整道题对每个 \(n\) 做的事情本质上都一样：每个素数幂给出一个下界，最大的那个下界就是答案。
C++、Python 和 Java 三个实现采用的是同一条路线。第一步是用“只保存奇数”的筛法生成 \(N\) 以内的所有素数：素数 \(2\) 单独处理，其余只存储和标记奇数候选。这样可以减少筛数组的体积，同时保持后续素数遍历的高效率。
接着，程序建立一个长度为 \(N+1\) 的答案数组，用来记录每个整数当前已知的最佳下界。对每个素数 \(p\)，先把所有 \(p\) 的倍数更新为至少 \(p\)。然后继续枚举更高的幂 \(p^2,p^3,\dots\) 直到超过 \(N\)。对于每个这样的素数幂，程序利用 Legendre 公式做二分查找，得到精确阈值，再把这个阈值传播到该素数幂的所有倍数上，更新方式是取最大值。
当所有素数幂都传播完毕后，数组中第 \(n\) 项就正好等于 \(s(n)\)。最后一次遍历把 \(2\le n\le N\) 的这些值全部累加起来。C++ 实现还会先验证一个小检查点：
$$S(100)=2012.$$
奇数筛生成素数的时间复杂度是 \(O(N\log\log N)\)。对所有素数倍数做更新的总成本为
$$N\sum_{p\le N}\frac{1}{p}=O(N\log\log N).$$
对更高次幂 \(p^a\)（其中 \(a\ge 2\)）的额外扫描总量为
$$N\sum_{p}\sum_{a\ge 2,\ p^a\le N}\frac{1}{p^a},$$
由于每个素数对应的几何尾和都是收敛的，所以这部分只有 \(O(N)\)。单个素数幂上的二分查找相对更小，不会改变主导复杂度。因此整体算法时间复杂度为 \(O(N\log\log N)\)，空间复杂度为 \(O(N)\)。
Определим
$$s(n)=\min\{m\ge 1 : n\mid m!\}.$$
В задаче 549 требуется вычислить
$$S(N)=\sum_{n=2}^{N} s(n)$$
при \(N=10^8\). Если искать \(s(n)\) отдельно для каждого \(n\), одна и та же информация о простых делителях будет вычисляться снова и снова. Поэтому решение сначала разбирается с простыми степенями, а затем ситовым способом распространяет их пороги на все подходящие числа.
Главное наблюдение состоит в том, что делимость факториала полностью контролируется по простым числам. Если для каждой простой степени \(p^a\le N\) известен минимальный порог факториала, то \(s(n)\) равно просто наибольшему из порогов тех простых степеней, которые делят \(n\).
Пусть
$$n=\prod_{i=1}^{r} p_i^{a_i}.$$
Тогда условие \(n\mid m!\) эквивалентно тому, что
$$v_{p_i}(m!)\ge a_i\qquad \text{для всех } i.$$
Для одной простой степени введем обозначение
$$t(p,a)=\min\{m\ge 1 : v_p(m!)\ge a\}.$$
Тогда
$$s(n)=\max_{1\le i\le r} t(p_i,a_i).$$
Почему это верно: минимальный подходящий факториал обязан удовлетворять всем ограничениям сразу, а значит, должен быть не меньше самого жесткого из них. Как только выполнено наибольшее требование, все остальные автоматически выполнены тоже.
Для фиксированного простого \(p\) формула Лежандра дает
$$v_p(m!)=\sum_{k\ge 1}\left\lfloor\frac{m}{p^k}\right\rfloor.$$
Сумма конечна, поскольку после \(p^k>m\) все слагаемые становятся нулевыми. Кроме того, она монотонно возрастает по \(m\), поэтому точный порог можно искать бинарным поиском.
Удобная общая верхняя граница такова:
$$t(p,a)\le pa,$$
потому что уже
$$v_p((pa)!)\ge \left\lfloor\frac{pa}{p}\right\rfloor=a.$$
Следовательно, точное значение для \(p^a\) всегда лежит в интервале \([1,pa]\).
При \(a=1\) никакой поиск не нужен:
$$t(p,1)=p,$$
ведь \(p\mid p!\), а ни один меньший факториал не содержит простой множитель \(p\). Для \(a\ge 2\) ищется минимальное \(m\) из \([1,pa]\), для которого сумма Лежандра достигает хотя бы \(a\).
Например,
$$t(2,3)=4,\qquad t(3,2)=6,$$
поскольку
$$v_2(4!)=2+1=3,\qquad v_3(6!)=2,$$
а предыдущие факториалы еще недостаточны.
Пусть для простой степени \(p^a\) уже известно \(t(p,a)\). Тогда любое число \(n\), делящееся на \(p^a\), обязано удовлетворять условию
$$s(n)\ge t(p,a).$$
Это означает, что нет смысла заново раскладывать каждое \(n\). Достаточно пройти по всем кратным \(p^a\) и сохранить максимум из всех порогов, которые на них действуют.
Иначе говоря, каждое кратное \(p\) получает как минимум значение \(p\). Каждое кратное \(p^2\) получает как минимум \(t(p,2)\), каждое кратное \(p^3\) получает как минимум \(t(p,3)\), и так далее, пока \(p^a\le N\).
После обработки всех простых степеней в позиции \(n\) окажется ровно
$$\max_{p^a\mid n} t(p,a)=s(n).$$
Имеем
$$72=2^3\cdot 3^2.$$
Из предыдущих шагов следует, что
$$t(2,3)=4,\qquad t(3,2)=6.$$
Значит,
$$s(72)=\max(4,6)=6.$$
И действительно,
$$v_2(6!)=3+1=4\ge 3,\qquad v_3(6!)=2\ge 2,$$
поэтому \(72\mid 6!\). А вот \(5!\) уже не хватает, потому что \(v_3(5!)=1\). Именно эта логика применяется ко всем \(n\le N\): каждая простая степень дает нижнюю границу, и максимальная из них и есть ответ.
Реализации на C++, Python и Java устроены одинаково. Сначала они генерируют все простые числа до \(N\) с помощью решета, которое хранит только нечетные кандидаты: число \(2\) обрабатывается отдельно, а маркировка выполняется лишь по нечетным индексам. Это экономит память и делает перечисление простых более компактным.
Затем создается массив ответов, где для каждого \(n\) хранится лучшая найденная на данный момент нижняя граница для \(s(n)\). Для каждого простого \(p\) все кратные \(p\) обновляются значением \(p\). После этого код перебирает степени \(p^2,p^3,\dots\) до тех пор, пока они не превысят \(N\). Для каждой такой степени точный порог вычисляется бинарным поиском по формуле Лежандра, а затем распространяется на все кратные этой степени операцией взятия максимума.
Когда все простые степени обработаны, массив в точности содержит значения \(s(n)\). Остается только просуммировать их для \(2\le n\le N\). Реализация на C++ также проверяет небольшой контрольный результат
$$S(100)=2012$$
перед полным запуском.
Построение решета по нечетным числам требует \(O(N\log\log N)\) времени. Обновления по всем кратным простых дают вклад
$$N\sum_{p\le N}\frac{1}{p}=O(N\log\log N).$$
Дополнительные проходы по высшим степеням \(p^a\) при \(a\ge 2\) дают
$$N\sum_{p}\sum_{a\ge 2,\ p^a\le N}\frac{1}{p^a},$$
и это всего лишь \(O(N)\), поскольку геометрический хвост по каждой простой базе сходится. Бинарные поиски для отдельных простых степеней сравнительно малы и не меняют общей оценки. В итоге алгоритм работает за \(O(N\log\log N)\) времени и использует \(O(N)\) памяти.
نعرّف
$$s(n)=\min\{m\ge 1 : n\mid m!\}.$$
وفي المسألة 549 نريد حساب
$$S(N)=\sum_{n=2}^{N} s(n)$$
عندما يكون \(N=10^8\). ولو حسبنا \(s(n)\) لكل عدد على حدة فسنكرر نفس تحليل العوامل الأولية مرارًا. لذلك تعيد الفكرة تنظيم المسألة حول قوى الأعداد الأولية، ثم تنشر حدودها الدنيا إلى جميع المضاعفات بطريقة غربالية.
الفكرة الحاسمة هي أن قابلية القسمة على \(m!\) تُحسم أوليًا عددًا أوليًا بعد آخر. فإذا عرفنا أصغر حد عاملي مطلوب لكل قوة أولية \(p^a\le N\)، فإن \(s(n)\) لا يكون إلا أكبر حد من هذه الحدود بين جميع القوى الأولية التي تقسم \(n\).
إذا كان
$$n=\prod_{i=1}^{r} p_i^{a_i},$$
فإن الشرط \(n\mid m!\) يكافئ تمامًا
$$v_{p_i}(m!)\ge a_i\qquad \forall i.$$
ولهذا نعرّف لقوة أولية واحدة
$$t(p,a)=\min\{m\ge 1 : v_p(m!)\ge a\}.$$
وعندئذٍ نحصل على
$$s(n)=\max_{1\le i\le r} t(p_i,a_i).$$
والسبب أن أصغر عاملي صالح لا بد أن يحقق جميع قيود القوى الأولية معًا، وبالتالي يجب أن يكون على الأقل بقدر أصعب هذه القيود، ومتى تحقق هذا القيد الأكبر تحققت القيود الأصغر تلقائيًا.
لعدد أولي ثابت \(p\)، تعطينا صيغة ليجاندر
$$v_p(m!)=\sum_{k\ge 1}\left\lfloor\frac{m}{p^k}\right\rfloor.$$
وهذا المجموع منتهٍ لأن الحدود تصبح صفرًا عندما يصير \(p^k>m\). كما أنه رتيب تصاعديًا مع \(m\)، ولهذا يمكن استعمال البحث الثنائي لإيجاد أول قيمة تبلغ الأس المطلوب \(a\).
ولدينا حد علوي بسيط هو
$$t(p,a)\le pa,$$
لأن
$$v_p((pa)!)\ge \left\lfloor\frac{pa}{p}\right\rfloor=a.$$
إذًا القيمة الدقيقة الموافقة لـ \(p^a\) تقع دائمًا داخل الفترة \([1,pa]\).
عندما \(a=1\) لا حاجة إلى أي بحث:
$$t(p,1)=p,$$
لأن \(p\mid p!\)، ولا يوجد عاملي أصغر يحتوي على العامل الأولي \(p\). أما عندما \(a\ge 2\)، فيُبحث عن أصغر \(m\) في \([1,pa]\) يجعل مجموع ليجاندر يصل إلى \(a\) على الأقل.
فعلى سبيل المثال،
$$t(2,3)=4,\qquad t(3,2)=6,$$
لأن
$$v_2(4!)=2+1=3,\qquad v_3(6!)=2,$$
بينما العواميل السابقة ما تزال غير كافية.
إذا كانت \(t(p,a)\) معلومة لقوة أولية \(p^a\)، فإن كل عدد \(n\) يقبل القسمة على \(p^a\) يجب أن يحقق
$$s(n)\ge t(p,a).$$
وهذا يعني أننا لسنا مضطرين إلى تحليل كل \(n\) من جديد. بدلًا من ذلك نمر على جميع مضاعفات \(p^a\) ونحفظ أكبر حد أدنى وصل إليها من أي قوة أولية.
عمليًا، كل مضاعف لـ \(p\) يحصل على القيمة \(p\) على الأقل. وكل مضاعف لـ \(p^2\) يحصل على \(t(p,2)\) على الأقل، وكل مضاعف لـ \(p^3\) يحصل على \(t(p,3)\)، وهكذا ما دام \(p^a\le N\).
وبعد معالجة جميع القوى الأولية تصبح القيمة المخزنة عند \(n\) مساوية تمامًا لـ
$$\max_{p^a\mid n} t(p,a)=s(n).$$
لدينا
$$72=2^3\cdot 3^2.$$
ومن الخطوات السابقة نعرف أن
$$t(2,3)=4,\qquad t(3,2)=6.$$
إذن
$$s(72)=\max(4,6)=6.$$
وهذا صحيح لأن
$$v_2(6!)=3+1=4\ge 3,\qquad v_3(6!)=2\ge 2,$$
ومن ثم \(72\mid 6!\). أما \(5!\) فلا يكفي لأن \(v_3(5!)=1\) فقط. ونفس الفكرة تنطبق على كل \(n\le N\): كل قوة أولية تضيف حدًا أدنى، وأكبر هذه الحدود هو الذي يحدد \(s(n)\).
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولًا تُولَّد جميع الأعداد الأولية حتى \(N\) بواسطة غربال يحتفظ فقط بالمرشحين الفرديين: يُعالَج العدد \(2\) منفصلًا، وتُخزَّن وتُعلَّم الأعداد الفردية فقط. هذا يقلل من حجم بيانات الغربال ويحافظ على كفاءة تعداد الأوليات.
بعد ذلك يُنشأ مصفوفة أجوبة تحفظ لكل \(n\) أفضل حد أدنى معروف حتى تلك اللحظة لقيمة \(s(n)\). ولكل عدد أولي \(p\)، تُحدَّث جميع مضاعفات \(p\) بالقيمة \(p\). ثم ينتقل التنفيذ إلى القوى الأعلى \(p^2,p^3,\dots\) ما دامت لا تتجاوز \(N\). ولكل قوة من هذه القوى يُحسب الحد الدقيق ببحث ثنائي يعتمد على صيغة ليجاندر، ثم يُنشر ذلك الحد إلى جميع مضاعفات هذه القوة بأخذ القيمة العظمى.
وعندما تنتهي جميع القوى الأولية من نشر حدودها، تكون الخانة الموافقة لـ \(n\) قد أصبحت مساوية تمامًا لـ \(s(n)\). وفي المرور الأخير تُجمع هذه القيم لكل \(2\le n\le N\). كما يتحقق تنفيذ C++ قبل الحساب الكامل من قيمة الضبط الصغيرة
$$S(100)=2012.$$
توليد الأوليات بغربال الأعداد الفردية يحتاج إلى زمن \(O(N\log\log N)\). أما تحديثات مضاعفات الأعداد الأولية فتكلف
$$N\sum_{p\le N}\frac{1}{p}=O(N\log\log N).$$
والمرورات الإضافية على القوى الأعلى \(p^a\) عندما \(a\ge 2\) تساهم بمقدار
$$N\sum_{p}\sum_{a\ge 2,\ p^a\le N}\frac{1}{p^a},$$
وهذا لا يتجاوز \(O(N)\) لأن الذيل الهندسي لكل أولي قابل للجمع. أما عمليات البحث الثنائي لقوى أولية منفردة فهي أصغر بكثير من حيث الكلفة ولا تغيّر الحد الرئيسي. لذلك تكون الخوارزمية كلها بزمن \(O(N\log\log N)\) وذاكرة \(O(N)\).