For a positive integer \(N\), let
$$U(N)=\{d \mid N : \gcd(d, N/d)=1\}$$
be the set of unitary divisors of \(N\). The function in this problem is
$$S(N)=\sum_{d \in U(N)} d^2.$$
We must compute \(S(100000000!) \bmod 1000000009\). A direct construction of the factorial or of all its divisors is impossible, so the solution has to work entirely from prime exponents.
If \(n=100000000\), then
$$n! = \prod_{p \le n} p^{e_p},$$
where the exponent of each prime \(p\) is given by Legendre's formula:
$$e_p = v_p(n!) = \sum_{k \ge 1}\left\lfloor \frac{n}{p^k} \right\rfloor.$$
The sum is finite because once \(p^k > n\), the quotient becomes zero. This formula is exactly what the implementation evaluates by repeated integer division.
Any divisor of \(N=\prod p^{e_p}\) has the form
$$d=\prod p^{a_p}, \qquad 0 \le a_p \le e_p.$$
The unitary condition \(\gcd(d,N/d)=1\) means that no prime may appear in both \(d\) and \(N/d\). Therefore, for every prime \(p\), the exponent \(a_p\) has only two valid choices:
$$a_p \in \{0, e_p\}.$$
If \(0 < a_p < e_p\), then \(p\) divides both \(d\) and \(N/d\), so the gcd would be larger than 1. Conversely, choosing only \(0\) or \(e_p\) makes the prime supports disjoint, so the divisor is unitary.
Because each prime contributes independently, every unitary divisor corresponds to choosing either “exclude \(p^{e_p}\)” or “include \(p^{e_p}\)”. Squaring such a divisor gives either a factor \(1\) or a factor \(p^{2e_p}\) from that prime. Hence
$$S(N)=\prod_{p \mid N}\left(\sum_{\varepsilon \in \{0,1\}} p^{2\varepsilon e_p}\right)=\prod_{p \mid N}\left(1+p^{2e_p}\right).$$
This is the crucial simplification: the huge sum over divisors becomes one multiplicative factor per prime.
Substituting the factorial exponents gives
$$\boxed{S(n!)=\prod_{p \le n}\left(1+p^{2v_p(n!)}\right).}$$
For the actual problem we evaluate this modulo
$$M=1000000009,$$
so the computation performed by the implementation is
$$S(n!) \equiv \prod_{p \le n}\left(1+p^{2e_p}\right) \pmod{M}.$$
No step ever needs the decimal expansion of \(n!\) itself.
This small case is useful because it matches a checkpoint used by the implementation. We have
$$4! = 24 = 2^3 \cdot 3^1.$$
A unitary divisor must take exponent \(0\) or the full exponent for each prime, so the unitary divisors are
$$1,\quad 2^3=8,\quad 3,\quad 2^3\cdot 3=24.$$
The sum of squares is
$$1^2+8^2+3^2+24^2 = 1+64+9+576 = 650.$$
The product formula gives the same result immediately:
$$S(4!)=(1+2^{2\cdot 3})(1+3^{2\cdot 1})=(1+64)(1+9)=65\cdot 10=650.$$
The C++, Python, and Java implementations all follow the same plan. First they generate every prime up to \(n\) with a sieve of Eratosthenes. Then, for each prime \(p\), they compute \(e_p=v_p(n!)\) by repeatedly dividing \(n\) by \(p\), then by \(p\) again, and accumulating the quotients \(\left\lfloor n/p \right\rfloor\), \(\left\lfloor n/p^2 \right\rfloor\), and so on.
After that, they evaluate \(p^{2e_p} \bmod M\) with binary modular exponentiation, form the factor \((1+p^{2e_p}) \bmod M\), and multiply it into a running product modulo \(M\). This avoids both overflow from the factorial itself and any attempt to enumerate divisors.
The sieve up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory. For each prime \(p\), exponent extraction needs \(O(\log_p n)\) divisions, so over all primes the extra work is
$$O\left(\sum_{p \le n}\log_p n\right),$$
and each modular power uses \(O(\log e_p)\) multiplications. In practice these stages are smaller than the sieve cost, so the overall method is dominated by prime generation and remains near
$$O(n\log\log n)$$
time with
$$O(n)$$
memory.
Für eine positive ganze Zahl \(N\) sei
$$U(N)=\{d \mid N : \gcd(d, N/d)=1\}$$
die Menge der unitären Teiler von \(N\). Gesucht ist die Funktion
$$S(N)=\sum_{d \in U(N)} d^2.$$
In dieser Aufgabe muss \(S(100000000!) \bmod 1000000009\) berechnet werden. Weder das Fakultätsprodukt selbst noch die Menge aller Teiler kann direkt konstruiert werden, daher arbeitet die Lösung ausschließlich mit Primexponenten.
Für \(n=100000000\) gilt
$$n! = \prod_{p \le n} p^{e_p},$$
wobei der Exponent eines Primteils \(p\) durch die Formel von Legendre gegeben ist:
$$e_p = v_p(n!) = \sum_{k \ge 1}\left\lfloor \frac{n}{p^k} \right\rfloor.$$
Die Summe endet automatisch, sobald \(p^k > n\) ist. Genau diese sukzessive Division wird in der Implementierung verwendet.
Jeder Teiler von \(N=\prod p^{e_p}\) besitzt die Form
$$d=\prod p^{a_p}, \qquad 0 \le a_p \le e_p.$$
Die Bedingung \(\gcd(d,N/d)=1\) bedeutet, dass keine Primzahl gleichzeitig in \(d\) und in \(N/d\) vorkommen darf. Daher hat für jedes \(p\) der Exponent \(a_p\) genau zwei zulässige Werte:
$$a_p \in \{0, e_p\}.$$
Liegt \(a_p\) strikt zwischen \(0\) und \(e_p\), dann teilt \(p\) beide Faktoren, also wäre der ggT größer als 1. Umgekehrt liefert jede Wahl nur aus \(0\) und \(e_p\) tatsächlich einen unitären Teiler.
Die Beiträge der verschiedenen Primzahlen sind unabhängig. Für jede Primzahl entscheidet man nur, ob \(p^{e_p}\) im unitären Teiler fehlt oder vollständig enthalten ist. Beim Quadrieren entsteht aus jedem Primblock daher entweder der Faktor \(1\) oder der Faktor \(p^{2e_p}\). Also
$$S(N)=\prod_{p \mid N}\left(\sum_{\varepsilon \in \{0,1\}} p^{2\varepsilon e_p}\right)=\prod_{p \mid N}\left(1+p^{2e_p}\right).$$
Damit reduziert sich die große Teilersumme auf genau einen Faktor pro Primzahl.
Einsetzen der Fakultätsexponenten ergibt
$$\boxed{S(n!)=\prod_{p \le n}\left(1+p^{2v_p(n!)}\right).}$$
Für die eigentliche Aufgabe rechnen wir modulo
$$M=1000000009,$$
also konkret
$$S(n!) \equiv \prod_{p \le n}\left(1+p^{2e_p}\right) \pmod{M}.$$
Zu keinem Zeitpunkt muss die Zahl \(n!\) selbst ausgerechnet werden.
Dieser Fall ist besonders nützlich, weil er mit einem Kontrollwert der Implementierung übereinstimmt. Es gilt
$$4! = 24 = 2^3 \cdot 3^1.$$
Ein unitärer Teiler darf pro Primzahl nur Exponent \(0\) oder den vollen Exponenten wählen. Daher sind die unitären Teiler
$$1,\quad 2^3=8,\quad 3,\quad 2^3\cdot 3=24.$$
Die Quadratsumme lautet
$$1^2+8^2+3^2+24^2 = 1+64+9+576 = 650.$$
Mit der Produktformel erhält man sofort denselben Wert:
$$S(4!)=(1+2^{2\cdot 3})(1+3^{2\cdot 1})=(1+64)(1+9)=65\cdot 10=650.$$
Die C++-, Python- und Java-Implementierungen verfolgen alle denselben Ablauf. Zuerst erzeugen sie mit einem Sieb des Eratosthenes alle Primzahlen bis \(n\). Danach wird für jede Primzahl \(p\) der Exponent \(e_p=v_p(n!)\) bestimmt, indem die Quotienten \(\left\lfloor n/p \right\rfloor\), \(\left\lfloor n/p^2 \right\rfloor\), \(\left\lfloor n/p^3 \right\rfloor\) und so weiter aufsummiert werden.
Anschließend berechnen die Implementierungen \(p^{2e_p} \bmod M\) per binärer modularer Exponentiation, bilden den Faktor \((1+p^{2e_p}) \bmod M\) und multiplizieren ihn in ein laufendes Produkt modulo \(M\). So werden weder die Fakultät noch die Teilermenge explizit aufgebaut.
Das Sieb bis \(n\) benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Für eine Primzahl \(p\) kostet die Bestimmung von \(e_p\) genau \(O(\log_p n)\) Divisionen; insgesamt entsteht also zusätzlicher Aufwand von
$$O\left(\sum_{p \le n}\log_p n\right).$$
Jede modulare Potenz kostet außerdem \(O(\log e_p)\) Multiplikationen. In der Praxis bleibt der dominante Anteil jedoch das Primzahlsieb, daher liegt die Gesamtlaufzeit nahe bei
$$O(n\log\log n)$$
bei einem Speicherverbrauch von
$$O(n).$$
Pozitif bir \(N\) tamsayısı için
$$U(N)=\{d \mid N : \gcd(d, N/d)=1\}$$
kümesi \(N\)'in üniter bölenlerini göstersin. Problemde kullanılan fonksiyon
$$S(N)=\sum_{d \in U(N)} d^2$$
şeklindedir. İstenen değer \(S(100000000!) \bmod 1000000009\)'dur. \(100000000!\) sayısını açıkça üretmek veya tüm bölenlerini dolaşmak mümkün olmadığı için çözüm tamamen asal üsleri üzerinden ilerler.
\(n=100000000\) için
$$n! = \prod_{p \le n} p^{e_p}$$
yazılır. Burada her asal \(p\)'nin üssü Legendre formülüyle bulunur:
$$e_p = v_p(n!) = \sum_{k \ge 1}\left\lfloor \frac{n}{p^k} \right\rfloor.$$
\(p^k > n\) olduğunda bölüm sıfır olacağı için toplam kendiliğinden biter. Uygulamanın yaptığı da tam olarak bu bölme zincirini hesaplamaktır.
\(N=\prod p^{e_p}\) için herhangi bir bölen
$$d=\prod p^{a_p}, \qquad 0 \le a_p \le e_p$$
biçimindedir. Üniter koşul \(\gcd(d,N/d)=1\) olduğundan, aynı asal hem \(d\) içinde hem de \(N/d\) içinde bulunamaz. Bu yüzden her asal için yalnızca iki olasılık vardır:
$$a_p \in \{0, e_p\}.$$
Eğer \(0 < a_p < e_p\) olursa, \(p\) hem \(d\)'yi hem de \(N/d\)'yi böler ve ebob 1'den büyük olur. Tersine, her asal için sadece \(0\) ya da tam üs seçilirse gerçekten üniter bölen elde edilir.
Farklı asallar birbirinden bağımsız katkı verir. Her asal blok için ya hiçbir şey seçilmez ya da \(p^{e_p}\) bütünüyle seçilir. Bu böleni karesini aldığımızda ilgili asaldan gelen katkı ya \(1\) ya da \(p^{2e_p}\) olur. Dolayısıyla
$$S(N)=\prod_{p \mid N}\left(\sum_{\varepsilon \in \{0,1\}} p^{2\varepsilon e_p}\right)=\prod_{p \mid N}\left(1+p^{2e_p}\right).$$
Böylece çok büyük bir bölen toplamı, asal başına tek bir çarpana indirgenmiş olur.
Faktöriyel üslerini yerine koyarsak
$$\boxed{S(n!)=\prod_{p \le n}\left(1+p^{2v_p(n!)}\right)}$$
elde edilir. Soruda modül
$$M=1000000009$$
olduğundan hesaplanan ifade
$$S(n!) \equiv \prod_{p \le n}\left(1+p^{2e_p}\right) \pmod{M}$$
şeklindedir. Yani algoritma hiçbir aşamada \(n!\) sayısını doğrudan kurmaz.
Bu küçük örnek, uygulamadaki denetim değeriyle birebir uyuşur. Önce
$$4! = 24 = 2^3 \cdot 3^1$$
yazalım. Her asal için üs ya \(0\) ya da tam üs olacağından üniter bölenler
$$1,\quad 2^3=8,\quad 3,\quad 2^3\cdot 3=24$$
olur. Kareler toplamı
$$1^2+8^2+3^2+24^2 = 1+64+9+576 = 650$$
çıkar. Çarpım formülü de aynı sonucu hemen verir:
$$S(4!)=(1+2^{2\cdot 3})(1+3^{2\cdot 1})=(1+64)(1+9)=65\cdot 10=650.$$
C++, Python ve Java uygulamalarının ortak planı aynıdır. Önce Eratosthenes eleği ile \(n\)'ye kadar tüm asallar üretilir. Sonra her asal \(p\) için \(\left\lfloor n/p \right\rfloor\), \(\left\lfloor n/p^2 \right\rfloor\), \(\left\lfloor n/p^3 \right\rfloor\) gibi terimler toplanarak \(e_p=v_p(n!)\) bulunur.
Daha sonra ikili modüler üs alma ile \(p^{2e_p} \bmod M\) hesaplanır, \((1+p^{2e_p}) \bmod M\) çarpanı oluşturulur ve bu değer mod altında birikimli sonuca çarpılır. Böylece ne faktöriyel sayısı ne de bölen listesi açıkça saklanır.
\(n\)'ye kadar yapılan elek \(O(n\log\log n)\) zaman ve \(O(n)\) bellek gerektirir. Bir asal \(p\) için üs hesabı \(O(\log_p n)\) bölme yapar; tüm asallar üzerinde ek maliyet
$$O\left(\sum_{p \le n}\log_p n\right)$$
olur. Her modüler üs alma da \(O(\log e_p)\) çarpma gerektirir. Pratikte baskın terim yine elektir; dolayısıyla toplam karmaşıklık yaklaşık
$$O(n\log\log n)$$
zaman ve
$$O(n)$$
bellektir.
Para un entero positivo \(N\), definamos
$$U(N)=\{d \mid N : \gcd(d, N/d)=1\}$$
como el conjunto de divisores unitarios de \(N\). La función pedida es
$$S(N)=\sum_{d \in U(N)} d^2.$$
El objetivo es calcular \(S(100000000!) \bmod 1000000009\). Construir el factorial o enumerar todos sus divisores es inviable, así que la solución debe trabajar únicamente con la factorización prima.
Si \(n=100000000\), entonces
$$n! = \prod_{p \le n} p^{e_p}.$$
El exponente de cada primo \(p\) está dado por la fórmula de Legendre:
$$e_p = v_p(n!) = \sum_{k \ge 1}\left\lfloor \frac{n}{p^k} \right\rfloor.$$
La suma termina cuando \(p^k > n\), porque a partir de ese momento el cociente es cero. Eso es exactamente lo que calculan las implementaciones mediante divisiones enteras repetidas.
Cualquier divisor de \(N=\prod p^{e_p}\) se escribe como
$$d=\prod p^{a_p}, \qquad 0 \le a_p \le e_p.$$
La condición \(\gcd(d,N/d)=1\) obliga a que ningún primo aparezca simultáneamente en \(d\) y en \(N/d\). Por tanto, para cada primo \(p\), el exponente \(a_p\) solo puede tomar dos valores:
$$a_p \in \{0, e_p\}.$$
Si \(0 < a_p < e_p\), entonces \(p\) divide a ambos factores y el máximo común divisor sería mayor que 1. En cambio, si siempre elegimos \(0\) o el exponente completo, el divisor es unitario.
Cada primo contribuye de manera independiente. Para un primo dado, o bien se excluye su bloque completo, o bien se incluye entero. Al elevar al cuadrado, la contribución de ese primo es \(1\) o \(p^{2e_p}\). Por eso
$$S(N)=\prod_{p \mid N}\left(\sum_{\varepsilon \in \{0,1\}} p^{2\varepsilon e_p}\right)=\prod_{p \mid N}\left(1+p^{2e_p}\right).$$
La gran suma sobre divisores unitarios queda reducida a un producto simple sobre los primos de \(N\).
Sustituyendo los exponentes de \(n!\), obtenemos
$$\boxed{S(n!)=\prod_{p \le n}\left(1+p^{2v_p(n!)}\right).}$$
Como el problema pide el resultado módulo
$$M=1000000009,$$
la cantidad que se evalúa es
$$S(n!) \equiv \prod_{p \le n}\left(1+p^{2e_p}\right) \pmod{M}.$$
En ningún momento hace falta construir explícitamente el valor decimal de \(n!\).
Este caso pequeño sirve como verificación concreta y coincide con un control usado por la implementación. Tenemos
$$4! = 24 = 2^3 \cdot 3^1.$$
Como cada primo solo puede aportar exponente \(0\) o el total, los divisores unitarios son
$$1,\quad 2^3=8,\quad 3,\quad 2^3\cdot 3=24.$$
Su suma de cuadrados es
$$1^2+8^2+3^2+24^2 = 1+64+9+576 = 650.$$
La fórmula producto da el mismo valor de inmediato:
$$S(4!)=(1+2^{2\cdot 3})(1+3^{2\cdot 1})=(1+64)(1+9)=65\cdot 10=650.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero generan todos los primos hasta \(n\) con una criba de Eratóstenes. Después, para cada primo \(p\), calculan \(e_p=v_p(n!)\) sumando los cocientes \(\left\lfloor n/p \right\rfloor\), \(\left\lfloor n/p^2 \right\rfloor\), \(\left\lfloor n/p^3 \right\rfloor\), y así sucesivamente.
Luego evalúan \(p^{2e_p} \bmod M\) mediante exponenciación modular binaria, forman el factor \((1+p^{2e_p}) \bmod M\) y lo multiplican en un producto acumulado módulo \(M\). De esta manera nunca se construye el factorial ni se enumeran divisores.
La criba hasta \(n\) cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Para cada primo \(p\), el cálculo del exponente requiere \(O(\log_p n)\) divisiones; en total, el trabajo adicional es
$$O\left(\sum_{p \le n}\log_p n\right).$$
Cada potencia modular consume además \(O(\log e_p)\) multiplicaciones. En la práctica, el coste dominante sigue siendo la generación de primos, así que el método completo queda cerca de
$$O(n\log\log n)$$
tiempo y
$$O(n)$$
memoria.
对正整数 \(N\)，定义
$$U(N)=\{d \mid N : \gcd(d, N/d)=1\}$$
为 \(N\) 的 unitary divisor 集合。题目要求的函数是
$$S(N)=\sum_{d \in U(N)} d^2.$$
现在要计算 \(S(100000000!) \bmod 1000000009\)。由于 \(100000000!\) 极其庞大，既不能直接构造这个数，也不能枚举它的全部因子，所以必须从素因子指数入手。
令 \(n=100000000\)，则
$$n! = \prod_{p \le n} p^{e_p}.$$
每个素数 \(p\) 在 \(n!\) 中的指数由 Legendre 公式给出：
$$e_p = v_p(n!) = \sum_{k \ge 1}\left\lfloor \frac{n}{p^k} \right\rfloor.$$
当 \(p^k > n\) 时，后面的商都为 0，因此这是一个有限和。实现中正是通过不断整除来计算这些指数。
若 \(N=\prod p^{e_p}\)，那么任意因子都可写成
$$d=\prod p^{a_p}, \qquad 0 \le a_p \le e_p.$$
条件 \(\gcd(d,N/d)=1\) 表示同一个素数不能同时出现在 \(d\) 和 \(N/d\) 中。所以对每个素数 \(p\)，指数 \(a_p\) 只能有两种选择：
$$a_p \in \{0, e_p\}.$$
如果 \(0 < a_p < e_p\)，那么 \(p\) 会同时整除 \(d\) 和 \(N/d\)，从而最大公因数大于 1。反过来，只要每个素数都只取 \(0\) 或完整指数，就一定得到 unitary divisor。
不同素数之间的贡献彼此独立。对每个素数块，要么完全不选，要么把 \(p^{e_p}\) 整块选入。平方以后，这个素数的贡献要么是 \(1\)，要么是 \(p^{2e_p}\)。因此
$$S(N)=\prod_{p \mid N}\left(\sum_{\varepsilon \in \{0,1\}} p^{2\varepsilon e_p}\right)=\prod_{p \mid N}\left(1+p^{2e_p}\right).$$
这一步把庞大的因子求和问题化成了按素数逐项相乘的问题。
将阶乘中的指数代入后得到
$$\boxed{S(n!)=\prod_{p \le n}\left(1+p^{2v_p(n!)}\right).}$$
题目要求模
$$M=1000000009,$$
所以实际计算的是
$$S(n!) \equiv \prod_{p \le n}\left(1+p^{2e_p}\right) \pmod{M}.$$
整个过程中都不需要真的把 \(n!\) 写出来。
这个小例子很重要，因为它正好对应实现中的一个校验值。我们有
$$4! = 24 = 2^3 \cdot 3^1.$$
由于每个素数只能取指数 \(0\) 或完整指数，所以 unitary divisor 为
$$1,\quad 2^3=8,\quad 3,\quad 2^3\cdot 3=24.$$
平方和为
$$1^2+8^2+3^2+24^2 = 1+64+9+576 = 650.$$
乘积公式也立刻给出同样的结果：
$$S(4!)=(1+2^{2\cdot 3})(1+3^{2\cdot 1})=(1+64)(1+9)=65\cdot 10=650.$$
C++、Python 和 Java 实现遵循同一套算法。首先用埃拉托斯特尼筛生成不超过 \(n\) 的全部素数。然后对每个素数 \(p\)，通过累加 \(\left\lfloor n/p \right\rfloor\)、\(\left\lfloor n/p^2 \right\rfloor\)、\(\left\lfloor n/p^3 \right\rfloor\) 等商，得到 \(e_p=v_p(n!)\)。
接着使用二进制快速幂计算 \(p^{2e_p} \bmod M\)，形成因子 \((1+p^{2e_p}) \bmod M\)，并把它乘进当前答案。这样就避免了构造超大的阶乘，也避免了枚举因子。
筛到 \(n\) 的时间复杂度是 \(O(n\log\log n)\)，空间复杂度是 \(O(n)\)。对单个素数 \(p\)，求 \(e_p\) 需要 \(O(\log_p n)\) 次整除，因此额外工作量总计为
$$O\left(\sum_{p \le n}\log_p n\right).$$
每次模幂运算还需要 \(O(\log e_p)\) 次乘法。实际运行中，主导成本仍然是筛法，所以整体复杂度接近
$$O(n\log\log n)$$
时间和
$$O(n)$$
空间。
Для положительного целого \(N\) обозначим через
$$U(N)=\{d \mid N : \gcd(d, N/d)=1\}$$
множество унитарных делителей числа \(N\). Рассматривается функция
$$S(N)=\sum_{d \in U(N)} d^2.$$
Нужно вычислить \(S(100000000!) \bmod 1000000009\). Поскольку \(100000000!\) слишком велико, решение не строит сам факториал и не перебирает делители, а работает только с показателями простых.
При \(n=100000000\) имеем
$$n! = \prod_{p \le n} p^{e_p}.$$
Показатель каждого простого \(p\) задается формулой Лежандра:
$$e_p = v_p(n!) = \sum_{k \ge 1}\left\lfloor \frac{n}{p^k} \right\rfloor.$$
Когда \(p^k > n\), частное становится нулем, поэтому сумма конечна. Именно такое повторное деление и выполняет реализация.
Любой делитель числа \(N=\prod p^{e_p}\) можно записать в виде
$$d=\prod p^{a_p}, \qquad 0 \le a_p \le e_p.$$
Условие \(\gcd(d,N/d)=1\) означает, что один и тот же простой не может входить одновременно и в \(d\), и в \(N/d\). Следовательно, для каждого простого \(p\) показатель \(a_p\) может быть только двух типов:
$$a_p \in \{0, e_p\}.$$
Если \(0 < a_p < e_p\), то \(p\) делит оба множителя, и gcd будет больше 1. Если же везде выбирать только \(0\) или полный показатель, получится ровно унитарный делитель.
Вклады разных простых независимы. Для каждого простого блока можно либо не брать его совсем, либо взять полностью \(p^{e_p}\). После возведения в квадрат вклад этого простого равен либо \(1\), либо \(p^{2e_p}\). Поэтому
$$S(N)=\prod_{p \mid N}\left(\sum_{\varepsilon \in \{0,1\}} p^{2\varepsilon e_p}\right)=\prod_{p \mid N}\left(1+p^{2e_p}\right).$$
Тем самым огромная сумма по делителям заменяется одним множителем на каждый простой.
После подстановки показателей факториала получаем
$$\boxed{S(n!)=\prod_{p \le n}\left(1+p^{2v_p(n!)}\right).}$$
Так как в задаче требуется ответ по модулю
$$M=1000000009,$$
реально вычисляется выражение
$$S(n!) \equiv \prod_{p \le n}\left(1+p^{2e_p}\right) \pmod{M}.$$
Само число \(n!\) нигде не строится явно.
Этот небольшой пример удобен тем, что совпадает с контрольным значением в реализации. Имеем
$$4! = 24 = 2^3 \cdot 3^1.$$
Поскольку по каждому простому можно выбрать только показатель \(0\) или полный показатель, унитарные делители таковы:
$$1,\quad 2^3=8,\quad 3,\quad 2^3\cdot 3=24.$$
Сумма квадратов равна
$$1^2+8^2+3^2+24^2 = 1+64+9+576 = 650.$$
Формула произведения дает тот же результат сразу:
$$S(4!)=(1+2^{2\cdot 3})(1+3^{2\cdot 1})=(1+64)(1+9)=65\cdot 10=650.$$
Реализации на C++, Python и Java используют один и тот же алгоритм. Сначала они строят все простые числа до \(n\) с помощью решета Эратосфена. Затем для каждого простого \(p\) вычисляют \(e_p=v_p(n!)\), суммируя \(\left\lfloor n/p \right\rfloor\), \(\left\lfloor n/p^2 \right\rfloor\), \(\left\lfloor n/p^3 \right\rfloor\) и так далее.
После этого с помощью бинарного модульного возведения в степень считается \(p^{2e_p} \bmod M\), формируется множитель \((1+p^{2e_p}) \bmod M\), и он умножается на текущий ответ по модулю \(M\). Благодаря этому не нужно ни хранить факториал, ни перебирать делители.
Решето до \(n\) требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Для одного простого \(p\) вычисление \(e_p\) занимает \(O(\log_p n)\) делений, так что суммарная добавка равна
$$O\left(\sum_{p \le n}\log_p n\right).$$
Каждое модульное возведение в степень использует еще \(O(\log e_p)\) умножений. На практике главный вклад все равно дает решето, поэтому итоговая сложность близка к
$$O(n\log\log n)$$
по времени и
$$O(n)$$
по памяти.
لعدد صحيح موجب \(N\)، نعرّف
$$U(N)=\{d \mid N : \gcd(d, N/d)=1\}$$
على أنه مجموعة القواسم الأحادية للعدد \(N\). والدالة المطلوبة هي
$$S(N)=\sum_{d \in U(N)} d^2.$$
المطلوب حساب \(S(100000000!) \bmod 1000000009\). وبما أن \(100000000!\) عدد هائل جدًا، فلا يمكن بناؤه مباشرة ولا يمكن تعداد جميع قواسمه، لذا يجب أن يعتمد الحل على أسس العوامل الأولية فقط.
إذا كان \(n=100000000\)، فإن
$$n! = \prod_{p \le n} p^{e_p}.$$
حيث يعطى أس كل عدد أولي \(p\) في \(n!\) بواسطة صيغة لوجندر:
$$e_p = v_p(n!) = \sum_{k \ge 1}\left\lfloor \frac{n}{p^k} \right\rfloor.$$
هذا المجموع منتهٍ لأن الحدود تصبح صفرًا عندما \(p^k > n\). وهذا بالضبط ما تحسبه الشيفرة عبر القسمة الصحيحة المتكررة.
أي قاسم للعدد \(N=\prod p^{e_p}\) يمكن كتابته على الصورة
$$d=\prod p^{a_p}, \qquad 0 \le a_p \le e_p.$$
لكن الشرط \(\gcd(d,N/d)=1\) يعني أن العامل الأولي نفسه لا يجوز أن يظهر في كل من \(d\) و \(N/d\) معًا. لذلك، لكل أولي \(p\)، لا توجد إلا حالتان ممكنتان:
$$a_p \in \{0, e_p\}.$$
فإذا كان \(0 < a_p < e_p\)، فإن \(p\) يقسم كلا العددين \(d\) و \(N/d\)، وعندئذ يكون القاسم المشترك الأكبر أكبر من 1. أما إذا اخترنا دائمًا \(0\) أو الأس الكامل، حصلنا على قاسم أحادي فعلًا.
إسهامات العوامل الأولية المختلفة مستقلة عن بعضها. لكل عامل أولي، إما أن نستبعد الكتلة \(p^{e_p}\) تمامًا أو نأخذها كاملة. وبعد التربيع تصبح مساهمة هذا العامل إما \(1\) أو \(p^{2e_p}\). لذلك نحصل على
$$S(N)=\prod_{p \mid N}\left(\sum_{\varepsilon \in \{0,1\}} p^{2\varepsilon e_p}\right)=\prod_{p \mid N}\left(1+p^{2e_p}\right).$$
وبهذا تتحول عملية جمع ضخمة على جميع القواسم الأحادية إلى جداء بسيط على جميع العوامل الأولية.
بالتعويض عن أسس العوامل في العاملية نحصل على
$$\boxed{S(n!)=\prod_{p \le n}\left(1+p^{2v_p(n!)}\right).}$$
ولأن المطلوب هو الحساب بترديد
$$M=1000000009,$$
فإن التعبير المنفذ فعليًا هو
$$S(n!) \equiv \prod_{p \le n}\left(1+p^{2e_p}\right) \pmod{M}.$$
لا حاجة في أي مرحلة إلى تكوين العدد \(n!\) نفسه.
هذا المثال الصغير مهم لأنه يطابق قيمة تحقق مستخدمة في التنفيذ. لدينا
$$4! = 24 = 2^3 \cdot 3^1.$$
وبما أن كل عامل أولي يختار الأس \(0\) أو الأس الكامل فقط، فإن القواسم الأحادية هي
$$1,\quad 2^3=8,\quad 3,\quad 2^3\cdot 3=24.$$
ومن ثم يكون مجموع المربعات
$$1^2+8^2+3^2+24^2 = 1+64+9+576 = 650.$$
وصيغة الجداء تعطي النتيجة نفسها مباشرة:
$$S(4!)=(1+2^{2\cdot 3})(1+3^{2\cdot 1})=(1+64)(1+9)=65\cdot 10=650.$$
تتبع تطبيقات C++ وPython وJava الخطة نفسها. أولًا تُولد جميع الأعداد الأولية حتى \(n\) باستعمال غربال إراتوستينس. ثم لكل أولي \(p\)، تُحسب القيمة \(e_p=v_p(n!)\) بجمع القيم \(\left\lfloor n/p \right\rfloor\)، \(\left\lfloor n/p^2 \right\rfloor\)، \(\left\lfloor n/p^3 \right\rfloor\)، وهكذا.
بعد ذلك يُحسب \(p^{2e_p} \bmod M\) بواسطة الأس المعياري الثنائي، ثم يُكوَّن العامل \((1+p^{2e_p}) \bmod M\) ويُضرب في الناتج التراكمي بترديد \(M\). بهذه الطريقة لا يتم إنشاء العاملية الضخمة ولا تعداد القواسم.
تكلفة الغربال حتى \(n\) هي \(O(n\log\log n)\) زمنًا و \(O(n)\) ذاكرة. أما حساب \(e_p\) لأولِي واحد \(p\) فيتطلب \(O(\log_p n)\) من عمليات القسمة، وبالتالي يكون العمل الإضافي الكلي
$$O\left(\sum_{p \le n}\log_p n\right).$$
كما أن كل عملية أس معياري تحتاج إلى \(O(\log e_p)\) من الضربات. عمليًا تبقى كلفة الغربال هي المسيطرة، لذا تكون الكلفة الإجمالية قريبة من
$$O(n\log\log n)$$
زمنًا و
$$O(n)$$
ذاكرة.