A pseudo-random sequence produces digits \(T_n\in\{0,1,\dots,p-1\}\). These digits define a huge base-\(p\) integer
$$N=\sum_{n=0}^{q}T_n p^n.$$
The required quantity is the \(p\)-adic valuation
$$\nu_p(N!)$$
taken modulo \(p^e\). For the actual problem, \(p=61\), \(q=10^7\), \(e=10\), but the explanation below is written for general \(p,q,e\).
1) Start from Legendre’s formula. For every positive integer \(N\),
$$\nu_p(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{p^k}\right\rfloor.$$
Since \(N\) has only \(q+1\) base-\(p\) digits, the sum actually stops at \(k=q\).
2) Expand each floor using the base-\(p\) digits. Because
$$N=\sum_{n=0}^{q}T_n p^n,$$
dividing by \(p^k\) and taking the floor simply drops the lowest \(k\) digits. Therefore
$$\left\lfloor\frac{N}{p^k}\right\rfloor=\sum_{n=k}^{q}T_n p^{\,n-k}.$$
This already shows why \(T_0\) never contributes to \(\nu_p(N!)\): every term in Legendre’s sum starts with division by at least one power of \(p\).
3) Swap the order of summation. Substitute the digit expansion into Legendre:
$$ \nu_p(N!)= \sum_{k=1}^{q}\sum_{n=k}^{q}T_n p^{\,n-k}. $$
Now fix a digit position \(n\). It contributes once for every \(k=1,2,\dots,n\). Writing \(j=n-k\), we obtain
$$ \nu_p(N!)= \sum_{n=1}^{q} T_n \sum_{j=0}^{n-1} p^j. $$
Equivalently, after swapping in the other direction,
$$ \nu_p(N!)= \sum_{j\ge 0} p^j \sum_{n=j+1}^{q} T_n. $$
This is the exact formula implemented by the code.
4) Why only the first \(e\) layers matter modulo \(p^e\). We only need the answer modulo \(p^e\). If \(j\ge e\), then \(p^j\) is already divisible by \(p^e\), so those terms vanish. Hence
$$ \nu_p(N!)\equiv \sum_{j=0}^{e-1} p^j S_j \pmod{p^e}, \qquad S_j=\sum_{n=j+1}^{q} T_n. $$
So the entire huge problem reduces to computing only \(e\) suffix sums of the digit sequence.
5) Why the code stores only a short prefix. Let
$$T_{\mathrm{all}}=\sum_{n=0}^{q}T_n.$$
Then each suffix can be written as
$$ S_j=T_{\mathrm{all}}-\sum_{n=0}^{j}T_n. $$
Therefore the solver only needs:
$$\text{(a) the total sum of all digits, and}\qquad \text{(b) prefix sums up to index }e-1.$$
This is why it stores
$$\texttt{first\_len}=\min(e,q+1)$$
prefix values, not the entire sequence.
6) Sequence generation. The digits are generated from
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,$$
and then
$$T_n=s_n\bmod p.$$
The algorithm streams the generator exactly once, accumulating the total digit sum and the first few prefix sums.
Take a toy base-\(5\) number with digits
$$T_0=2,\qquad T_1=4,\qquad T_2=1.$$
Then
$$N=2+4\cdot 5+1\cdot 25=47.$$
Legendre gives
$$\nu_5(47!)=\left\lfloor\frac{47}{5}\right\rfloor+\left\lfloor\frac{47}{25}\right\rfloor=9+1=10.$$
Now use the suffix formula:
$$S_0=T_1+T_2=5,\qquad S_1=T_2=1.$$
So
$$\nu_5(47!)=5^0S_0+5^1S_1=5+5=10,$$
exactly as expected.
The source file includes the checkpoint
$$\mathrm{NF}(3,10000)\bmod 3^{20}=624955285,$$
and also compares the fast method against a brute-force big-integer computation for a smaller case.
Time complexity is
$$O(q+e),$$
because generating the digits costs \(O(q)\) and the final valuation sum costs \(O(e)\). Memory usage is
$$O(e),$$
since only a short prefix array and a few accumulators are stored.
Eine Pseudozufallsfolge erzeugt Ziffern \(T_n\in\{0,1,\dots,p-1\}\). Daraus entsteht die riesige Zahl
$$N=\sum_{n=0}^{q}T_n p^n.$$
Gesucht ist die \(p\)-adische Bewertung
$$\nu_p(N!)$$
modulo \(p^e\). Im eigentlichen Problem sind \(p=61\), \(q=10^7\), \(e=10\).
1) Ausgangspunkt: Legendre.
$$\nu_p(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{p^k}\right\rfloor.$$
Wegen der endlichen Ziffernlänge endet diese Summe effektiv bei \(k=q\).
2) Jede Floor-Funktion in Basis \(p\) ausschreiben. Aus
$$N=\sum_{n=0}^{q}T_n p^n$$
folgt sofort
$$\left\lfloor\frac{N}{p^k}\right\rfloor=\sum_{n=k}^{q}T_n p^{n-k}.$$
Die unteren \(k\) Ziffern fallen einfach weg. Dadurch sieht man auch direkt: \(T_0\) trägt nie zu \(\nu_p(N!)\) bei.
3) Summen vertauschen. Einsetzen in Legendre liefert
$$ \nu_p(N!)= \sum_{k=1}^{q}\sum_{n=k}^{q}T_n p^{n-k}. $$
Fixiert man nun \(n\), so erscheint \(T_n\) genau für \(k=1,\dots,n\). Mit \(j=n-k\) ergibt sich
$$ \nu_p(N!)= \sum_{n=1}^{q}T_n\sum_{j=0}^{n-1}p^j. $$
Oder äquivalent
$$ \nu_p(N!)= \sum_{j\ge 0}p^j\sum_{n=j+1}^{q}T_n. $$
4) Warum modulo \(p^e\) nur \(j<e\) zählt. Sobald \(j\ge e\), ist \(p^j\) bereits durch \(p^e\) teilbar. Also bleibt
$$ \nu_p(N!)\equiv \sum_{j=0}^{e-1}p^jS_j \pmod{p^e}, \qquad S_j=\sum_{n=j+1}^{q}T_n. $$
5) Warum nur ein kurzer Präfix gespeichert wird. Mit
$$T_{\mathrm{all}}=\sum_{n=0}^{q}T_n$$
gilt
$$S_j=T_{\mathrm{all}}-\sum_{n=0}^{j}T_n.$$
Damit braucht der Code nur die Gesamtsumme aller Ziffern und Präfixsummen bis Index \(e-1\). Genau deshalb wird
$$\texttt{first\_len}=\min(e,q+1)$$
verwendet.
6) Erzeugung der Ziffern.
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,\qquad T_n=s_n\bmod p.$$
Die Folge wird nur einmal gestreamt.
Nimm in Basis \(5\) die Ziffern
$$T_0=2,\qquad T_1=4,\qquad T_2=1.$$
Dann ist
$$N=2+4\cdot 5+1\cdot 25=47.$$
Legendre ergibt
$$\nu_5(47!)=\left\lfloor\frac{47}{5}\right\rfloor+\left\lfloor\frac{47}{25}\right\rfloor=9+1=10.$$
Mit den Suffixsummen:
$$S_0=T_1+T_2=5,\qquad S_1=T_2=1,$$
also
$$\nu_5(47!)=5^0S_0+5^1S_1=5+5=10.$$
Im Quelltext steht der Checkpoint
$$\mathrm{NF}(3,10000)\bmod 3^{20}=624955285,$$
zusätzlich zu einem Brute-Force-Vergleich für einen kleineren Fall.
Die Laufzeit ist
$$O(q+e),$$
der Speicherbedarf
$$O(e).$$
Bir pseudo-random dizi \(T_n\in\{0,1,\dots,p-1\}\) basamaklarını üretir. Bu basamaklar
$$N=\sum_{n=0}^{q}T_n p^n$$
şeklinde çok büyük bir \(p\)-tabanlı sayı tanımlar. Aranan değer
$$\nu_p(N!)$$
olup sonuç \(p^e\) modunda alınır. Asıl problemde \(p=61\), \(q=10^7\), \(e=10\)'dur.
1) Başlangıç noktası: Legendre formülü.
$$\nu_p(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{p^k}\right\rfloor.$$
\(N\)'nin yalnızca \(q+1\) basamağı olduğundan bu toplam gerçekte \(k=q\)'da biter.
2) Her floor terimini basamaklarla aç. Çünkü
$$N=\sum_{n=0}^{q}T_n p^n,$$
bölüp floor alınca en alt \(k\) basamak düşer:
$$\left\lfloor\frac{N}{p^k}\right\rfloor=\sum_{n=k}^{q}T_n p^{n-k}.$$
Buradan \(T_0\)'ın neden hiç katkı vermediği de açıkça görülür.
3) Toplamları yer değiştir. Legendre içine yerleştirince
$$ \nu_p(N!)= \sum_{k=1}^{q}\sum_{n=k}^{q}T_n p^{n-k} $$
elde edilir. Sabit bir \(n\) için \(T_n\), \(k=1,\dots,n\) boyunca görünür. \(j=n-k\) yazarsak
$$ \nu_p(N!)= \sum_{n=1}^{q}T_n\sum_{j=0}^{n-1}p^j $$
ve eşdeğer olarak
$$ \nu_p(N!)= \sum_{j\ge 0}p^j\sum_{n=j+1}^{q}T_n $$
olur. Kodun çekirdek fikri tam budur.
4) Neden mod \(p^e\) altında sadece ilk \(e\) katman kalır? Eğer \(j\ge e\) ise \(p^j\), zaten \(p^e\)'ye tam bölünür. Bu yüzden
$$ \nu_p(N!)\equiv \sum_{j=0}^{e-1}p^jS_j \pmod{p^e}, \qquad S_j=\sum_{n=j+1}^{q}T_n $$
yeterlidir. Yani bütün dev problem sadece \(e\) tane suffix toplamına indirgenir.
5) Kod neden kısa bir prefix tutuyor? Toplam basamak toplamını
$$T_{\mathrm{all}}=\sum_{n=0}^{q}T_n$$
olarak yazarsak
$$S_j=T_{\mathrm{all}}-\sum_{n=0}^{j}T_n$$
olur. Bu nedenle kodun ihtiyacı olan şey yalnızca:
$$\text{(a) tüm basamakların toplamı,}\qquad \text{(b) yalnızca ilk }e\text{ kadar prefix toplamı.}$$
Bu yüzden
$$\texttt{first\_len}=\min(e,q+1)$$
saklanır; bütün dizi tutulmaz.
6) Dizinin üretimi.
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,\qquad T_n=s_n\bmod p.$$
Algoritma bu üreteci yalnızca bir kez akar şekilde çalıştırır.
Taban \(5\) için
$$T_0=2,\qquad T_1=4,\qquad T_2=1$$
olsun. O zaman
$$N=2+4\cdot 5+1\cdot 25=47.$$
Legendre formülünden
$$\nu_5(47!)=\left\lfloor\frac{47}{5}\right\rfloor+\left\lfloor\frac{47}{25}\right\rfloor=9+1=10$$
çıkar. Suffix toplam formülü ise
$$S_0=T_1+T_2=5,\qquad S_1=T_2=1$$
verir ve
$$\nu_5(47!)=5^0S_0+5^1S_1=5+5=10$$
aynı sonucu üretir.
Kaynak dosyadaki checkpoint şunu doğrular:
$$\mathrm{NF}(3,10000)\bmod 3^{20}=624955285.$$
Ayrıca daha küçük bir örnekte brute-force büyük tamsayı hesabıyla çapraz kontrol yapılır.
Zaman karmaşıklığı
$$O(q+e),$$
bellek karmaşıklığı ise
$$O(e)$$
olarak kalır.
Una secuencia pseudoaleatoria produce dígitos \(T_n\in\{0,1,\dots,p-1\}\). Con ellos se define el enorme entero en base \(p\)
$$N=\sum_{n=0}^{q}T_n p^n.$$
Se busca la valoración \(p\)-ádica
$$\nu_p(N!)$$
módulo \(p^e\).
1) Punto de partida: Legendre.
$$\nu_p(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{p^k}\right\rfloor.$$
2) Expandir cada floor con las cifras base \(p\). Como
$$N=\sum_{n=0}^{q}T_n p^n,$$
tenemos
$$\left\lfloor\frac{N}{p^k}\right\rfloor=\sum_{n=k}^{q}T_n p^{n-k}.$$
Esto también muestra por qué \(T_0\) nunca contribuye.
3) Reordenar la suma. Sustituyendo en Legendre:
$$ \nu_p(N!)= \sum_{k=1}^{q}\sum_{n=k}^{q}T_n p^{n-k}. $$
Fijando \(n\) y usando \(j=n-k\), obtenemos
$$ \nu_p(N!)= \sum_{n=1}^{q}T_n\sum_{j=0}^{n-1}p^j =\sum_{j\ge 0}p^j\sum_{n=j+1}^{q}T_n. $$
4) Truncación módulo \(p^e\). Si \(j\ge e\), entonces \(p^j\) ya es múltiplo de \(p^e\), así que
$$ \nu_p(N!)\equiv \sum_{j=0}^{e-1}p^jS_j \pmod{p^e}, \qquad S_j=\sum_{n=j+1}^{q}T_n. $$
5) Por qué el código guarda solo un prefijo corto. Si
$$T_{\mathrm{all}}=\sum_{n=0}^{q}T_n,$$
entonces
$$S_j=T_{\mathrm{all}}-\sum_{n=0}^{j}T_n.$$
Por eso basta con la suma total y las sumas prefijo hasta \(e-1\).
6) Generación de la secuencia.
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,\qquad T_n=s_n\bmod p.$$
La secuencia se recorre una sola vez.
En base \(5\), toma
$$T_0=2,\qquad T_1=4,\qquad T_2=1.$$
Entonces
$$N=2+4\cdot5+1\cdot25=47.$$
Legendre da
$$\nu_5(47!)=\left\lfloor\frac{47}{5}\right\rfloor+\left\lfloor\frac{47}{25}\right\rfloor=9+1=10.$$
Por la fórmula de sufijos,
$$S_0=T_1+T_2=5,\qquad S_1=T_2=1,$$
y así
$$\nu_5(47!)=5^0S_0+5^1S_1=5+5=10.$$
El código incluye el checkpoint
$$\mathrm{NF}(3,10000)\bmod 3^{20}=624955285,$$
además de una verificación brute force para un caso pequeño.
La complejidad temporal es
$$O(q+e),$$
y la memoria es
$$O(e).$$
伪随机序列生成数字 \(T_n\in\{0,1,\dots,p-1\}\)，从而构造出巨大的 \(p\) 进制整数
$$N=\sum_{n=0}^{q}T_n p^n.$$
要求计算
$$\nu_p(N!)$$
并对 \(p^e\) 取模。
1) 从 Legendre 公式出发。
$$\nu_p(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{p^k}\right\rfloor.$$
2) 用 \(p\) 进制数字展开每一个 floor。 因为
$$N=\sum_{n=0}^{q}T_n p^n,$$
所以
$$\left\lfloor\frac{N}{p^k}\right\rfloor=\sum_{n=k}^{q}T_n p^{n-k}.$$
这也立刻解释了为什么 \(T_0\) 从不贡献到 \(\nu_p(N!)\)。
3) 交换求和顺序。
$$ \nu_p(N!)= \sum_{k=1}^{q}\sum_{n=k}^{q}T_n p^{n-k}. $$
固定 \(n\)，再令 \(j=n-k\)，可得
$$ \nu_p(N!)= \sum_{n=1}^{q}T_n\sum_{j=0}^{n-1}p^j =\sum_{j\ge 0}p^j\sum_{n=j+1}^{q}T_n. $$
4) 为什么模 \(p^e\) 只需要前 \(e\) 层。 当 \(j\ge e\) 时，\(p^j\) 已经被 \(p^e\) 整除，因此这些项在模 \(p^e\) 下全部消失。于是
$$ \nu_p(N!)\equiv \sum_{j=0}^{e-1}p^jS_j \pmod{p^e}, \qquad S_j=\sum_{n=j+1}^{q}T_n. $$
5) 为什么代码只保存很短的前缀和。 令
$$T_{\mathrm{all}}=\sum_{n=0}^{q}T_n,$$
则
$$S_j=T_{\mathrm{all}}-\sum_{n=0}^{j}T_n.$$
所以只要保存所有数字总和，以及前 \(e\) 项以内的前缀和，就足够恢复全部需要的 \(S_j\)。
6) 数列生成。
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,\qquad T_n=s_n\bmod p.$$
算法只顺序扫描这条序列一次。
取一个 \(5\) 进制玩具例子：
$$T_0=2,\qquad T_1=4,\qquad T_2=1.$$
则
$$N=2+4\cdot5+1\cdot25=47.$$
由 Legendre 公式，
$$\nu_5(47!)=\left\lfloor\frac{47}{5}\right\rfloor+\left\lfloor\frac{47}{25}\right\rfloor=9+1=10.$$
而后缀公式给出
$$S_0=T_1+T_2=5,\qquad S_1=T_2=1,$$
因此
$$\nu_5(47!)=5^0S_0+5^1S_1=5+5=10,$$
两种方法完全一致。
源码中包含如下 checkpoint：
$$\mathrm{NF}(3,10000)\bmod 3^{20}=624955285,$$
并且还会在一个更小的案例上与 brute-force 大整数方法交叉验证。
时间复杂度为
$$O(q+e),$$
空间复杂度为
$$O(e).$$
Псевдослучайная последовательность порождает цифры \(T_n\in\{0,1,\dots,p-1\}\), из которых строится огромное число в базе \(p\):
$$N=\sum_{n=0}^{q}T_n p^n.$$
Требуется вычислить
$$\nu_p(N!)$$
по модулю \(p^e\).
1) Стартуем с формулы Лежандра.
$$\nu_p(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{p^k}\right\rfloor.$$
2) Разложим каждую floor-функцию по цифрам. Так как
$$N=\sum_{n=0}^{q}T_n p^n,$$
получаем
$$\left\lfloor\frac{N}{p^k}\right\rfloor=\sum_{n=k}^{q}T_n p^{n-k}.$$
Отсюда сразу видно, почему \(T_0\) не входит в \(\nu_p(N!)\).
3) Переставим суммы.
$$ \nu_p(N!)= \sum_{k=1}^{q}\sum_{n=k}^{q}T_n p^{n-k}. $$
Фиксируя \(n\) и полагая \(j=n-k\), получаем
$$ \nu_p(N!)= \sum_{n=1}^{q}T_n\sum_{j=0}^{n-1}p^j =\sum_{j\ge 0}p^j\sum_{n=j+1}^{q}T_n. $$
4) Усечение по модулю \(p^e\). При \(j\ge e\) множитель \(p^j\) уже кратен \(p^e\), поэтому остаётся только
$$ \nu_p(N!)\equiv \sum_{j=0}^{e-1}p^jS_j \pmod{p^e}, \qquad S_j=\sum_{n=j+1}^{q}T_n. $$
5) Почему достаточно короткого префикса. Если
$$T_{\mathrm{all}}=\sum_{n=0}^{q}T_n,$$
то
$$S_j=T_{\mathrm{all}}-\sum_{n=0}^{j}T_n.$$
Значит, программе нужна только общая сумма всех цифр и префиксные суммы до индекса \(e-1\).
6) Генерация последовательности.
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,\qquad T_n=s_n\bmod p.$$
Последовательность читается ровно один раз.
Пусть в базе \(5\)
$$T_0=2,\qquad T_1=4,\qquad T_2=1.$$
Тогда
$$N=2+4\cdot5+1\cdot25=47.$$
По Лежандру
$$\nu_5(47!)=\left\lfloor\frac{47}{5}\right\rfloor+\left\lfloor\frac{47}{25}\right\rfloor=9+1=10.$$
По формуле через суффиксы
$$S_0=T_1+T_2=5,\qquad S_1=T_2=1,$$
и потому
$$\nu_5(47!)=5^0S_0+5^1S_1=5+5=10.$$
В исходнике есть checkpoint
$$\mathrm{NF}(3,10000)\bmod 3^{20}=624955285,$$
а также brute-force сверка на меньшем тесте.
Временная сложность равна
$$O(q+e),$$
пространственная
$$O(e).$$
تولّد سلسلة pseudo-random أرقامًا \(T_n\in\{0,1,\dots,p-1\}\)، ومن هذه الأرقام نكوّن العدد الضخم
$$N=\sum_{n=0}^{q}T_n p^n.$$
المطلوب هو حساب
$$\nu_p(N!)$$
بترديد \(p^e\).
1) نبدأ بصيغة ليجاندر.
$$\nu_p(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{p^k}\right\rfloor.$$
2) نفك كل حد باستعمال أرقام الأساس \(p\). بما أن
$$N=\sum_{n=0}^{q}T_n p^n,$$
فإن
$$\left\lfloor\frac{N}{p^k}\right\rfloor=\sum_{n=k}^{q}T_n p^{n-k}.$$
ومن هنا يظهر فورًا أن \(T_0\) لا يساهم أبدًا في \(\nu_p(N!)\).
3) نبدّل ترتيب الجمع.
$$ \nu_p(N!)= \sum_{k=1}^{q}\sum_{n=k}^{q}T_n p^{n-k}. $$
وبتثبيت \(n\) وكتابة \(j=n-k\) نحصل على
$$ \nu_p(N!)= \sum_{n=1}^{q}T_n\sum_{j=0}^{n-1}p^j =\sum_{j\ge 0}p^j\sum_{n=j+1}^{q}T_n. $$
4) القص بترديد \(p^e\). عندما \(j\ge e\)، يكون \(p^j\) من مضاعفات \(p^e\)، ولذلك لا تبقى إلا الحدود
$$ \nu_p(N!)\equiv \sum_{j=0}^{e-1}p^jS_j \pmod{p^e}, \qquad S_j=\sum_{n=j+1}^{q}T_n. $$
5) لماذا يكفي تخزين prefix قصير. إذا كانت
$$T_{\mathrm{all}}=\sum_{n=0}^{q}T_n,$$
فإن
$$S_j=T_{\mathrm{all}}-\sum_{n=0}^{j}T_n.$$
إذًا يحتاج الكود فقط إلى مجموع جميع الأرقام وإلى prefix sums لأول \(e\) حدود تقريبًا، لا إلى السلسلة كلها.
6) توليد السلسلة.
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,\qquad T_n=s_n\bmod p.$$
وتتم معالجة هذه السلسلة مرورًا واحدًا فقط.
لنأخذ في الأساس \(5\):
$$T_0=2,\qquad T_1=4,\qquad T_2=1.$$
إذن
$$N=2+4\cdot5+1\cdot25=47.$$
ومن صيغة ليجاندر
$$\nu_5(47!)=\left\lfloor\frac{47}{5}\right\rfloor+\left\lfloor\frac{47}{25}\right\rfloor=9+1=10.$$
أما بصيغة suffix sums فنجد
$$S_0=T_1+T_2=5,\qquad S_1=T_2=1,$$
ومن ثم
$$\nu_5(47!)=5^0S_0+5^1S_1=5+5=10.$$
يتضمن الملف نقطة تحقق:
$$\mathrm{NF}(3,10000)\bmod 3^{20}=624955285,$$
كما يجري مقارنة مع brute-force على حالة أصغر.
التعقيد الزمني هو
$$O(q+e),$$
والذاكرة
$$O(e).$$