Define \(N(i)\) as the smallest integer \(n\) such that
$$n! \text{ is divisible by } (i!)^{1234567890}.$$
Then
$$S(u)=\sum_{i=10}^{u}N(i).$$
We are given
$$S(1000)=614538266565663,$$
and must compute
$$S(1000000)\bmod 10^{18}.$$
1) Divisibility of factorials is a prime-valuation problem.
Write
$$i!=\prod_{p\le i}p^{e_{i,p}},\qquad e_{i,p}=v_p(i!).$$
Then
$$(i!)^K=\prod_{p\le i}p^{K e_{i,p}},\qquad K=1234567890.$$
Therefore
$$(i!)^K\mid n!\iff v_p(n!)\ge K e_{i,p}\quad\text{for every prime }p\le i.$$
So the whole problem reduces to matching required prime exponents inside \(n!\).
2) Legendre's formula tells us the exponent of one prime in \(n!\).
For a fixed prime \(p\),
$$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
This function is monotone increasing in \(n\). So if we want the smallest \(n\) satisfying
$$v_p(n!)\ge t,$$
we can find it by binary search.
3) Per-prime bottlenecks.
For each prime \(p\), define the current target
$$t_p=K\,v_p(i!).$$
Let \(n_p\) be the smallest integer with
$$v_p(n_p!)\ge t_p.$$
Then the smallest \(n\) satisfying all prime conditions simultaneously is simply
$$N(i)=\max_{p\le i} n_p.$$
The largest per-prime obstruction determines the answer.
4) Incremental update from \(i-1\) to \(i\).
This is the key optimization. Suppose
$$i=\prod p^{\alpha_p}.$$
Then
$$v_p(i!)=v_p((i-1)!)+\alpha_p,$$
so the required target updates only for primes dividing \(i\):
$$t_p\leftarrow t_p+K\alpha_p.$$
All other primes keep exactly the same target. Therefore, when we move from \(i-1\) to \(i\), we only need to recompute the primes appearing in the factorization of \(i\).
5) Why the global maximum never decreases.
Every target \(t_p\) is nondecreasing as \(i\) grows. Hence every minimal witness \(n_p\) is also nondecreasing. So
$$N(i)=\max_p n_p$$
can never go down. This is why the code stores a single running value current_max and only raises it when a changed prime produces a larger \(n_p\).
6) Lower bound for binary search.
Legendre's formula implies
$$v_p(n!)\le \frac{n}{p-1}.$$
So any \(n\) meeting \(v_p(n!)\ge t_p\) must satisfy
$$n\ge t_p(p-1).$$
The implementation uses this as a cheap lower bound, and it also keeps the previous solution for that prime as another lower bound because \(n_p\) never decreases.
7) Example of the incremental logic.
When we move from \(i=9\) to \(i=10\), only the prime factors of \(10\) matter:
$$10=2\cdot 5.$$
So the required exponents update as
$$t_2\leftarrow t_2+K,\qquad t_5\leftarrow t_5+K,$$
while the targets for \(3,7,\dots\) stay unchanged. Therefore we recompute only \(n_2\) and \(n_5\), and then compare them to the existing global maximum.
8) Fast factorization of every \(i\).
To make the incremental update cheap, the program precomputes the smallest prime factor (SPF) of every number up to \(10^6\). Then each \(i\) is factorized in essentially logarithmic time by repeatedly dividing by its SPF.
1) Build an SPF sieve up to \(u\).
2) Maintain, for every prime \(p\), the required target \(t_p\) and its minimal witness \(n_p\).
3) For each \(i=2,3,\dots,u\), factorize \(i\).
4) For each prime \(p^{\alpha_p}\) in \(i\), update
$$t_p\leftarrow t_p+K\alpha_p,$$
then recompute \(n_p\) by binary search on Legendre's formula.
5) Update the running maximum \(N(i)\).
6) Add \(N(i)\) to the sum whenever \(i\ge10\).
The sieve costs roughly linear time in \(u\). Each \(i\) changes only the primes in its factorization, which is very small on average. Each changed prime needs a binary search, and each midpoint evaluation computes
$$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor$$
in \(O(\log_p n)\). This is vastly faster than recomputing all prime constraints from scratch for every \(i\).
The source checks
$$S(1000)=614538266565663.$$
For the full problem, it computes
$$S(1000000)\bmod 10^{18}=278157919195482643.$$
Fuer jedes \(i\) wird das kleinste \(n\) gesucht, so dass
$$n! \text{ durch } (i!)^{1234567890} \text{ teilbar ist.}$$
Dann wird
$$S(u)=\sum_{i=10}^{u}N(i)$$
gebildet, und gesucht ist \(S(10^6)\bmod 10^{18}\).
1) Primexponenten.
Mit
$$i!=\prod_{p\le i}p^{e_{i,p}},\qquad e_{i,p}=v_p(i!),$$
ist die Bedingung aequivalent zu
$$v_p(n!)\ge K e_{i,p}\quad\text{fuer alle }p\le i.$$
2) Legendre pro Primzahl.
Es gilt
$$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor,$$
also eine monotone Funktion in \(n\). Deshalb kann das kleinste passende \(n_p\) per Binaersuche gefunden werden.
3) Nur Primfaktoren von \(i\) aendern sich.
Ist
$$i=\prod p^{\alpha_p},$$
dann gilt beim Uebergang \(i-1\to i\):
$$t_p\leftarrow t_p+K\alpha_p.$$
Andere Primzahlen bleiben unveraendert.
4) Globales Minimum.
Wenn \(n_p\) das Minimum fuer Primzahl \(p\) ist, dann lautet
$$N(i)=\max_{p\le i} n_p.$$
Da alle Ziele \(t_p\) nur wachsen, koennen auch \(n_p\) und damit \(N(i)\) nie sinken. Deshalb reicht ein laufendes Maximum.
5) Untere Schranke.
Aus
$$v_p(n!)\le \frac{n}{p-1}$$
folgt
$$n\ge t_p(p-1).$$
Diese Schranke dient zusammen mit der alten Loesung fuer \(p\) als Startpunkt der Suche.
1) SPF-Sieb bis \(10^6\) aufbauen.
2) Fuer jede Primzahl \(p\) die Zielgroesse \(t_p\) und das aktuelle Minimum \(n_p\) speichern.
3) Jedes \(i\) schnell faktorisieren.
4) Nur die betroffenen Primzahlen aktualisieren und per Legendre + Binaersuche neu berechnen.
5) Das laufende Maximum zu \(N(i)\) machen und zu \(S(u)\) addieren.
Nach dem Sieb braucht jeder Schritt nur wenige Prime-Updates. Pro Update faellt eine Binaersuche an, und jeder Testwert benoetigt nur eine kurze Legendre-Summe. Das ist viel effizienter als eine komplette Neuberechnung fuer jedes \(i\).
Der Code prueft
$$S(1000)=614538266565663.$$
Das Endergebnis ist
$$S(1000000)\bmod 10^{18}=278157919195482643.$$
Her \(i\) icin
$$n! \text{ sayisinin } (i!)^{1234567890}\text{'a bolundugu en kucuk }n$$
aranir. Buna \(N(i)\) denir. Sonra
$$S(u)=\sum_{i=10}^{u}N(i)$$
toplami hesaplanir ve \(S(10^6)\bmod 10^{18}\) istenir.
1) Problem tamamen asal uslere iner.
$$i!=\prod_{p\le i}p^{e_{i,p}},\qquad e_{i,p}=v_p(i!).$$
Bu durumda
$$(i!)^K\mid n!\iff v_p(n!)\ge K e_{i,p}\quad\text{tum }p\le i\text{ icin}.$$
2) Legendre formulu tek asal icin ihtiyaci verir.
$$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
Bu fonksiyon \(n\)'e gore arttigi icin,
$$v_p(n!)\ge t_p$$
kosulunu saglayan en kucuk \(n_p\) ikili arama ile bulunur.
3) \(i\) artarken sadece \(i\)'nin asal carpanlari degisir.
Eger
$$i=\prod p^{\alpha_p}$$
ise
$$v_p(i!)=v_p((i-1)!)+\alpha_p,$$
dolayisiyla hedefler sadece bu asallar icin
$$t_p\leftarrow t_p+K\alpha_p$$
olarak guncellenir.
4) Tum kosullari birden saglayan minimum.
Her asal icin bulunan minimum \(n_p\) verildiginde
$$N(i)=\max_{p\le i} n_p$$
olur. Cunku tum asal kosullarini ayni anda saglamak icin en zorlayici asal hangi \(n\)'i istiyorsa, cevap odur.
5) Neden global maksimumu basta tutmak yeterli?
Hicbir \(t_p\) azalmaz; bu yuzden hicbir \(n_p\) de azalmaz. Dolayisiyla
$$N(i)=\max_p n_p$$
degeri de asla dusmez. Kodun sadece current_max tutmasinin nedeni bu monotonluktur.
6) Ikili arama icin alt sinir.
Legendre formulunden
$$v_p(n!)\le \frac{n}{p-1}$$
geldigi icin, hedef \(t_p\) icin zorunlu olarak
$$n\ge t_p(p-1)$$
olmalidir. Kod, hem bu alt siniri hem de bir onceki \(n_p\) degerini kullanarak aramayi cok dar bir araliktan baslatir.
7) Somut artimsal ornek.
\(9\)'dan \(10\)'a gecerken sadece
$$10=2\cdot5$$
asal carpanlari etkilidir. Yani yalnizca
$$t_2\leftarrow t_2+K,\qquad t_5\leftarrow t_5+K$$
yapilir; diger asallar ayni kalir. Bu sayede her adimda tum asallari sifirdan taramaya gerek kalmaz.
1) \(10^6\)'ya kadar SPF eleği kur.
2) Her asal icin hedef us \(t_p\) ve buna yeten minimum \(n_p\) tut.
3) Her \(i\)'yi SPF ile hizli carpana ayir.
4) Sadece bu carpanlar icin \(t_p\)'yi arttir ve \(n_p\)'yi ikili arama + Legendre ile yeniden hesapla.
5) Guncel maksimumu \(N(i)\) olarak topla.
Eleğin maliyeti lineer civarindadir. Sonraki adimlarda her \(i\) icin yalnizca cok az sayida asal guncellenir. Her guncelleme bir ikili arama ve her testte kisa bir Legendre toplami gerektirir. Bu, her \(i\) icin tum asallari yeniden kontrol etmekten cok daha hizlidir.
Kaynak kod su checkpoint'i dogrular:
$$S(1000)=614538266565663.$$
Nihai sonuc ise
$$S(1000000)\bmod 10^{18}=278157919195482643$$
olarak bulunur.
Para cada \(i\), se define \(N(i)\) como el menor \(n\) tal que
$$n! \text{ sea divisible por } (i!)^{1234567890}.$$
Luego
$$S(u)=\sum_{i=10}^{u}N(i),$$
y se pide \(S(10^6)\bmod 10^{18}\).
1) Todo se reduce a exponentes primos.
Si
$$i!=\prod_{p\le i}p^{e_{i,p}},$$
entonces la divisibilidad equivale a
$$v_p(n!)\ge K e_{i,p}\quad\text{para todo primo }p\le i.$$
2) Formula de Legendre.
$$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
Como esta funcion es monotona, el menor \(n_p\) que satisface un objetivo dado se encuentra por busqueda binaria.
3) Actualizacion incremental.
Si
$$i=\prod p^{\alpha_p},$$
al pasar de \(i-1\) a \(i\) solo cambian esas potencias:
$$t_p\leftarrow t_p+K\alpha_p.$$
Los demas primos quedan intactos.
4) Maximo de restricciones.
Si \(n_p\) es el minimo para el primo \(p\), entonces
$$N(i)=\max_{p\le i} n_p.$$
Ademas, estos valores nunca disminuyen, por lo que basta mantener un maximo global creciente.
5) Cota inferior util.
De
$$v_p(n!)\le \frac{n}{p-1}$$
se obtiene la cota
$$n\ge t_p(p-1).$$
El codigo usa esta cota y el valor anterior de \(n_p\) para iniciar la busqueda binaria.
1) Construir una criba SPF hasta \(10^6\).
2) Mantener, para cada primo, el objetivo \(t_p\) y el minimo \(n_p\).
3) Factorizar cada \(i\) con la criba.
4) Actualizar solo los primos que dividen a \(i\) y recalcular su \(n_p\) con Legendre + busqueda binaria.
5) Acumular el maximo global.
Tras la criba, cada paso afecta solo a pocos primos. Cada actualizacion usa busqueda binaria y evaluaciones breves de Legendre, mucho mas rapido que recomputar todas las restricciones en cada \(i\).
El programa verifica
$$S(1000)=614538266565663.$$
El resultado final es
$$S(1000000)\bmod 10^{18}=278157919195482643.$$
对每个 \(i\)，定义 \(N(i)\) 为满足
$$n! \text{ 可被 } (i!)^{1234567890}\text{ 整除}$$
的最小 \(n\)。再令
$$S(u)=\sum_{i=10}^{u}N(i),$$
要求 \(S(10^6)\bmod 10^{18}\)。
1）转成素因子指数约束。
$$i!=\prod_{p\le i}p^{e_{i,p}},\qquad e_{i,p}=v_p(i!).$$
于是
$$ (i!)^K\mid n! \iff v_p(n!)\ge K e_{i,p}\ \text{对所有 }p\le i.$$
2）Legendre 公式。
$$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
它关于 \(n\) 单调递增，所以每个素数的最小满足值 \(n_p\) 可以用二分搜索得到。
3）从 \(i-1\) 到 \(i\) 只需做增量更新。
若
$$i=\prod p^{\alpha_p},$$
则只有这些素数的需求变化：
$$t_p\leftarrow t_p+K\alpha_p.$$
其他素数完全不变。
4）全局答案就是所有 \(n_p\) 的最大值。
$$N(i)=\max_{p\le i} n_p.$$
而且每个 \(t_p\) 都只增不减，因此每个 \(n_p\) 以及全局最大值都不会下降。这就是代码里只维护一个递增的 current_max 的原因。
5）二分搜索的下界。
由
$$v_p(n!)\le \frac{n}{p-1}$$
可得必要条件
$$n\ge t_p(p-1).$$
代码把它和旧的 \(n_p\) 一起作为二分的起点。
1) 做 SPF 筛到 \(10^6\)。
2) 维护每个素数的目标指数 \(t_p\) 及其最小见证值 \(n_p\)。
3) 用 SPF 快速分解每个 \(i\)。
4) 只更新 \(i\) 的素因子，并用 Legendre + 二分重算对应 \(n_p\)。
5) 将当前最大值加入总和。
筛法近似线性。之后每个 \(i\) 只影响很少的素数，每次更新只需一次二分和若干个 Legendre 项。比每步重算全部素数约束高效得多。
程序先验证
$$S(1000)=614538266565663.$$
最终结果是
$$S(1000000)\bmod 10^{18}=278157919195482643.$$
Для каждого \(i\) определяется минимальное \(n\), для которого
$$n! \text{ делится на } (i!)^{1234567890}.$$
Далее суммируются значения
$$S(u)=\sum_{i=10}^{u}N(i),$$
и требуется \(S(10^6)\bmod 10^{18}\).
1) Переход к p-адическим показателям.
$$i!=\prod_{p\le i}p^{e_{i,p}},\qquad e_{i,p}=v_p(i!).$$
Тогда условие делимости равносильно
$$v_p(n!)\ge K e_{i,p}\quad\text{для всех простых }p\le i.$$
2) Формула Лежандра.
$$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
Так как эта функция монотонно растет, минимальное подходящее \(n_p\) ищется бинарным поиском.
3) Инкрементное обновление.
Если
$$i=\prod p^{\alpha_p},$$
то при переходе к \(i\) меняются только эти простые:
$$t_p\leftarrow t_p+K\alpha_p.$$
Остальные ограничения остаются прежними.
4) Глобальный ответ.
Если \(n_p\) - минимальное решение для простого \(p\), то
$$N(i)=\max_{p\le i}n_p.$$
Поскольку цели \(t_p\) только растут, значения \(n_p\) и максимум также никогда не убывают.
5) Нижняя граница для поиска.
Из оценки
$$v_p(n!)\le \frac{n}{p-1}$$
следует необходимость
$$n\ge t_p(p-1).$$
Код использует эту границу и предыдущее значение \(n_p\) как старт бинарного поиска.
1) Построить SPF-решето до \(10^6\).
2) Хранить для каждого простого \(t_p\) и \(n_p\).
3) Быстро факторизовать каждое \(i\).
4) Обновлять только простые делители \(i\) и пересчитывать их \(n_p\) через Лежандра + бинарный поиск.
5) Добавлять текущий максимум к сумме.
После решета каждый шаг затрагивает лишь несколько простых чисел. Каждый апдейт требует одного бинарного поиска и короткой суммы Лежандра. Это намного быстрее полного пересчета на каждом \(i\).
Программа проверяет
$$S(1000)=614538266565663.$$
Итоговый ответ:
$$S(1000000)\bmod 10^{18}=278157919195482643.$$
لكل \(i\)، نعرّف \(N(i)\) بأنه أصغر \(n\) يحقق
$$n! \text{ قابل للقسمة على } (i!)^{1234567890}.$$
ثم نحسب
$$S(u)=\sum_{i=10}^{u}N(i),$$
والمطلوب هو \(S(10^6)\bmod 10^{18}\).
1) تحويل الشرط إلى أسس أولية.
$$i!=\prod_{p\le i}p^{e_{i,p}},\qquad e_{i,p}=v_p(i!).$$
إذن
$$ (i!)^K\mid n! \iff v_p(n!)\ge K e_{i,p}\text{ لكل أولي }p\le i.$$
2) صيغة Legendre.
$$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
وبما أن هذه الدالة متزايدة في \(n\)، فإن أقل \(n_p\) يحقق هدفًا معينًا يمكن إيجاده بالبحث الثنائي.
3) التحديث التزايدي.
إذا كان
$$i=\prod p^{\alpha_p},$$
فعند الانتقال من \(i-1\) إلى \(i\) تتغير فقط هذه الأوليات:
$$t_p\leftarrow t_p+K\alpha_p.$$
أما باقي الأوليات فتبقى كما هي.
4) الجواب الكلي هو أكبر قيد جزئي.
إذا كان \(n_p\) هو أصغر عدد يحقق شرط الأولي \(p\)، فحينئذ
$$N(i)=\max_{p\le i} n_p.$$
كما أن كل \(t_p\) لا ينقص أبدًا، وبالتالي لا ينقص أي \(n_p\) ولا ينقص الحد الأقصى العام أيضًا.
5) حد سفلي مفيد للبحث.
من
$$v_p(n!)\le \frac{n}{p-1}$$
نحصل على الشرط الضروري
$$n\ge t_p(p-1).$$
ويستخدمه الكود مع القيمة السابقة لـ \(n_p\) كنقطة بداية للبحث الثنائي.
1) بناء منخل SPF حتى \(10^6\).
2) تخزين \(t_p\) و\(n_p\) لكل أولي.
3) تحليل كل \(i\) سريعًا باستخدام SPF.
4) تحديث الأوليات التي تقسم \(i\) فقط، ثم إعادة حساب \(n_p\) لها بصيغة Legendre مع بحث ثنائي.
5) إضافة الحد الأقصى الحالي إلى المجموع.
بعد المنخل، كل خطوة تمس عددًا قليلًا فقط من الأوليات. وكل تحديث يحتاج إلى بحث ثنائي وتقييم قصير لصيغة Legendre، وهو أسرع كثيرًا من إعادة الفحص الكامل لكل \(i\).
يتحقق البرنامج من
$$S(1000)=614538266565663.$$
والنتيجة النهائية هي
$$S(1000000)\bmod 10^{18}=278157919195482643.$$