For a positive integer \(m=\prod p_i^{a_i}\), its roundness is the largest integer \(r\ge 1\) such that \(m\) is a perfect \(r\)th power. For every nontrivial \(m\), that is exactly
$$\rho(m)=\gcd(a_1,a_2,\dots).$$
The total roundness of \(N\) is defined by summing \(\rho(d)\) over every divisor \(d\mid N\) with \(d>1\):
$$T(N)=\sum_{\substack{d\mid N\\ d>1}}\rho(d).$$
Problem 926 asks for \(T(10^7!)\bmod 10^9+7\). The divisor \(1\) is excluded for an important reason: it is a perfect \(k\)th power for every \(k\), so any layer-by-layer counting formula would otherwise contain an infinite extra contribution.
The implementations never enumerate divisors of \(10^7!\), and they never compute \(\gcd\) values divisor by divisor. Instead, they describe every divisor through the prime exponents of the factorial, convert roundness into a sum over perfect-power layers, and then maintain the layer counts with a sweep over the breakpoints of floor quotients.
Write
$$n!=\prod_{p\le n} p^{e_p},$$
where each exponent is given by Legendre's formula
$$e_p=v_p(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
Every divisor of \(n!\) is then uniquely determined by choosing exponents
$$d=\prod_{p\le n} p^{a_p},\qquad 0\le a_p\le e_p.$$
For \(d>1\), only the positive exponents matter, so
$$\rho(d)=\gcd\{a_p:\ a_p>0\}.$$
This is the real problem-specific object behind the task: the answer depends only on the multiset of factorial exponents \(\{e_p\}\), not on the divisors themselves as standalone integers.
A divisor with roundness \(g\) is a perfect \(k\)th power for exactly the integers \(k\) with \(1\le k\le g\). Equivalently,
$$\rho(d)=\sum_{k\ge 1}\mathbf{1}\!\left(d\text{ is a perfect }k\text{th power}\right).$$
Summing that identity over all nontrivial divisors gives
$$T(n!)=\sum_{k\ge 1}\#\left\{d\mid n!:\ d>1,\ d\text{ is a perfect }k\text{th power}\right\}.$$
For a fixed \(k\), the divisor \(d=\prod p^{a_p}\) is a perfect \(k\)th power exactly when each exponent is divisible by \(k\), so we can write \(a_p=k b_p\) with
$$0\le b_p\le \left\lfloor\frac{e_p}{k}\right\rfloor.$$
That makes the number of perfect \(k\)th-power divisors
$$D_k-1,\qquad D_k=\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right).$$
The factor \(D_k\) counts all choices of the scaled exponents \(b_p\), including the all-zero choice that produces the divisor \(1\); the final \(-1\) removes that forbidden divisor.
Since the largest factorial exponent is \(e_2=v_2(n!)\), the sum stops at
$$E=\max_{p\le n} e_p=v_2(n!).$$
So the whole task becomes
$$\boxed{T(n!)=\sum_{k=1}^{E}\left(\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right)-1\right)\pmod{10^9+7}.}$$
At \(k=1\), this product is simply the divisor count \(\tau(n!)\), so the first layer already contributes \(\tau(n!)-1\).
Rebuilding the product over all primes for every \(k\) would still be too slow, because \(n=10^7\) has hundreds of thousands of primes. The key compression used by all three implementations is to group primes by the value of their factorial exponent. Define
$$c_e=\#\left\{p\le n:\ v_p(n!)=e\right\}.$$
Then the layer count becomes
$$D_k=\prod_{e\ge 1}\left(\left\lfloor\frac{e}{k}\right\rfloor+1\right)^{c_e}.$$
Now the problem is no longer indexed by primes, but by distinct exponent values \(e\). Many primes share the same \(e\), so this representation is dramatically smaller than the raw prime list while remaining exactly equivalent.
For one fixed exponent value \(e\), only the factor
$$f_e(k)=\left\lfloor\frac{e}{k}\right\rfloor+1$$
matters. This function is piecewise constant in \(k\). If at some left endpoint \(l\) we have
$$q=\left\lfloor\frac{e}{l}\right\rfloor,$$
then the same quotient persists up to
$$r=\left\lfloor\frac{e}{q}\right\rfloor.$$
So one quotient value controls the entire interval \(l\le k\le r\). The implementations exploit exactly those interval boundaries. They start from
$$D_1=\prod_{e\ge 1}(e+1)^{c_e},$$
and whenever a group with multiplicity \(c_e\) changes from an old factor \(t_{\text{old}}\) to a new factor \(t_{\text{new}}\), the current product is updated by
$$\left(\frac{t_{\text{new}}}{t_{\text{old}}}\right)^{c_e} \pmod{10^9+7}.$$
Because the modulus is prime, those divisions are implemented with modular inverses. When \(k=e+1\), the factor for that group becomes \(1\) permanently, so no further updates from that group are needed.
A concrete one-group example makes the event logic visible. For \(e=8\), the values of \(\left\lfloor 8/k\right\rfloor+1\) are
$$9\text{ at }k=1,\quad 5\text{ at }k=2,\quad 3\text{ at }k=3,4,\quad 2\text{ at }k=5,6,7,8,\quad 1\text{ afterwards}.$$
So this single exponent group generates updates exactly at the breakpoints \(k=2,3,5,9\). The global algorithm does the same for every distinct exponent value, sorts all update events, and sweeps upward through \(k\).
For \(n=10\), Legendre's formula gives
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7^1.$$
So the factorial exponents are \(8,4,2,1\), and the perfect-power layer counts are
$$\begin{aligned} D_1&=(8+1)(4+1)(2+1)(1+1)=270,\\ D_2&=(4+1)(2+1)(1+1)(0+1)=30,\\ D_3&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_4&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_5&=D_6=D_7=D_8=2. \end{aligned}$$
Therefore
$$T(10!)=(270-1)+(30-1)+(6-1)+(6-1)+4\cdot(2-1)=312.$$
This example shows the exact meaning of the layer formula. The first layer counts all nontrivial divisors, the second layer counts all nontrivial square divisors, the third layer counts all nontrivial cube divisors, and so on. Summing those layers reproduces the sum of roundness values without ever enumerating the divisors themselves.
The C++, Python, and Java implementations first generate the primes up to \(n\) with a sieve. For each prime \(p\), they evaluate \(v_p(n!)\) by repeated division, which is exactly Legendre's formula in iterative form. While doing that, they build the multiplicities \(c_e\) and record the maximum exponent \(E\).
Once the groups \((e,c_e)\) are known, the implementations compute the initial product \(D_1\). Then each distinct exponent value is processed independently. Using the interval rule \(r=\lfloor e/q\rfloor\), the code locates every \(k\) where \(\lfloor e/k\rfloor\) changes and emits one event containing that sweep position and the multiplicative ratio that updates the contribution of the whole group. After all groups have emitted their events, those events are sorted by \(k\).
The final sweep runs from \(k=1\) to \(k=E\). Before adding the contribution for a given \(k\), the implementation applies every event scheduled at that position. The maintained invariant is simple and exact: after processing all events at \(k\), the running product equals \(D_k\) modulo \(10^9+7\). The answer then adds \(D_k-1\), again subtracting the trivial divisor \(1\). That is the whole algorithm.
Let \(E=v_2(n!)\), and let \(B\) be the total number of update events produced by all distinct exponent groups. The prime sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. Computing all factorial exponents costs \(O\!\left(\sum_{p\le n}\log_p n\right)\) arithmetic steps.
After that, event generation costs \(O(B)\), sorting costs \(O(B\log B)\), and the sweep costs \(O(E+B)\). In practice, \(B\) is far smaller than the naive \(E\cdot\pi(n)\) recomputation cost because each exponent group changes only at quotient breakpoints rather than at every value of \(k\). Memory usage is \(O(n+B)\), dominated by the sieve storage and the event list.
Für eine positive Zahl \(m=\prod p_i^{a_i}\) ist ihre roundness die größte ganze Zahl \(r\ge 1\), so dass \(m\) eine perfekte \(r\)-te Potenz ist. Für jedes nichttriviale \(m\) gilt also
$$\rho(m)=\gcd(a_1,a_2,\dots).$$
Die total roundness von \(N\) ist die Summe von \(\rho(d)\) über alle Teiler \(d\mid N\) mit \(d>1\):
$$T(N)=\sum_{\substack{d\mid N\\ d>1}}\rho(d).$$
Gesucht ist \(T(10^7!)\bmod 10^9+7\). Der Teiler \(1\) wird bewusst ausgeschlossen, denn \(1\) ist für jedes \(k\) eine perfekte \(k\)-te Potenz; bei einer Schichtenzählung würde er daher eine unendliche Zusatzsumme erzeugen.
Die Implementierungen zählen weder die Teiler von \(10^7!\) direkt noch berechnen sie für jeden Teiler einzeln einen ggT. Stattdessen beschreiben sie alle Teiler über die Primexponenten des Fakultätswerts, schreiben roundness als Summe über Potenz-Schichten und verfolgen diese Schichten dann mit einem Sweep über die Sprungstellen von Floor-Quotienten.
Schreibe
$$n!=\prod_{p\le n} p^{e_p},$$
wobei jeder Exponent durch die Legendre-Formel gegeben ist:
$$e_p=v_p(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
Jeder Teiler von \(n!\) wird dann eindeutig durch Exponenten
$$d=\prod_{p\le n} p^{a_p},\qquad 0\le a_p\le e_p$$
bestimmt. Für \(d>1\) zählen nur die positiven Exponenten, also
$$\rho(d)=\gcd\{a_p:\ a_p>0\}.$$
Damit hängt die Aufgabe nur von der Multimenge der Fakultätsexponenten \(\{e_p\}\) ab. Genau diese Struktur extrahieren die Implementierungen.
Hat ein Teiler roundness \(g\), dann ist er genau für die Werte \(k=1,\dots,g\) eine perfekte \(k\)-te Potenz. Das lässt sich schreiben als
$$\rho(d)=\sum_{k\ge 1}\mathbf{1}\!\left(d\text{ ist eine perfekte }k\text{-te Potenz}\right).$$
Summiert man das über alle nichttrivialen Teiler, erhält man
$$T(n!)=\sum_{k\ge 1}\#\left\{d\mid n!:\ d>1,\ d\text{ ist eine perfekte }k\text{-te Potenz}\right\}.$$
Für festes \(k\) ist \(d=\prod p^{a_p}\) genau dann eine perfekte \(k\)-te Potenz, wenn jeder Exponent durch \(k\) teilbar ist, also \(a_p=k b_p\) mit
$$0\le b_p\le \left\lfloor\frac{e_p}{k}\right\rfloor.$$
Daraus folgt die Anzahl
$$D_k-1,\qquad D_k=\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right).$$
Der Faktor \(D_k\) zählt alle Wahlmöglichkeiten der skalierten Exponenten \(b_p\), einschließlich der All-Null-Wahl für den Teiler \(1\). Das abschließende \(-1\) entfernt genau diesen unerlaubten Fall.
Da der größte Fakultätsexponent bei \(p=2\) auftritt, endet die Summe bei
$$E=\max_{p\le n} e_p=v_2(n!).$$
Somit gilt
$$\boxed{T(n!)=\sum_{k=1}^{E}\left(\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right)-1\right)\pmod{10^9+7}.}$$
Für \(k=1\) ist dieses Produkt gerade \(\tau(n!)\), also die Anzahl aller Teiler. Die erste Schicht trägt daher \(\tau(n!)-1\) bei.
Würde man das Produkt für jedes \(k\) erneut über alle Primzahlen aufbauen, wäre das trotz der Schichtenformel zu langsam. Deshalb gruppieren die Implementierungen alle Primzahlen mit demselben Fakultätsexponenten. Definiere
$$c_e=\#\left\{p\le n:\ v_p(n!)=e\right\}.$$
Dann wird
$$D_k=\prod_{e\ge 1}\left(\left\lfloor\frac{e}{k}\right\rfloor+1\right)^{c_e}.$$
Damit ist das Problem nicht mehr nach Primzahlen indiziert, sondern nach verschiedenen Exponentenwerten \(e\). Viele Primzahlen teilen sich denselben Wert, daher ist diese Darstellung wesentlich kompakter und dennoch exakt.
Für einen festen Exponentenwert \(e\) ist nur der Faktor
$$f_e(k)=\left\lfloor\frac{e}{k}\right\rfloor+1$$
relevant. Diese Funktion ist stückweise konstant. Gilt an einer linken Grenze \(l\)
$$q=\left\lfloor\frac{e}{l}\right\rfloor,$$
dann bleibt derselbe Quotient bis
$$r=\left\lfloor\frac{e}{q}\right\rfloor$$
erhalten. Ein Quotientswert kontrolliert also das ganze Intervall \(l\le k\le r\). Genau diese Intervallgrenzen nutzt der Code. Er startet bei
$$D_1=\prod_{e\ge 1}(e+1)^{c_e},$$
und immer wenn sich eine Gruppe mit Multiplizität \(c_e\) von einem alten Faktor \(t_{\text{old}}\) auf einen neuen Faktor \(t_{\text{new}}\) ändert, wird das laufende Produkt mit
$$\left(\frac{t_{\text{new}}}{t_{\text{old}}}\right)^{c_e} \pmod{10^9+7}$$
aktualisiert. Da der Modul prim ist, geschieht die Division über modulare Inverse. Bei \(k=e+1\) wird der Faktor dieser Gruppe dauerhaft zu \(1\), danach sind aus dieser Gruppe keine weiteren Updates mehr nötig.
Ein kleines Ein-Gruppen-Beispiel macht die Ereignislogik sichtbar. Für \(e=8\) nimmt \(\left\lfloor 8/k\right\rfloor+1\) die Werte
$$9\text{ bei }k=1,\quad 5\text{ bei }k=2,\quad 3\text{ bei }k=3,4,\quad 2\text{ bei }k=5,6,7,8,\quad 1\text{ danach}.$$
Diese einzelne Gruppe erzeugt also genau an den Stellen \(k=2,3,5,9\) Updates. Der Gesamtalgorithmus macht dasselbe für jeden verschiedenen Exponentenwert, sortiert alle Ereignisse und sweeped dann aufsteigend durch \(k\).
Für \(n=10\) liefert die Legendre-Formel
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7^1.$$
Die Fakultätsexponenten sind also \(8,4,2,1\). Damit erhält man die Schichtenzahlen
$$\begin{aligned} D_1&=(8+1)(4+1)(2+1)(1+1)=270,\\ D_2&=(4+1)(2+1)(1+1)(0+1)=30,\\ D_3&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_4&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_5&=D_6=D_7=D_8=2. \end{aligned}$$
Deshalb
$$T(10!)=(270-1)+(30-1)+(6-1)+(6-1)+4\cdot(2-1)=312.$$
Dieses Beispiel zeigt präzise, was die Schichtenformel bedeutet. Die erste Schicht zählt alle nichttrivialen Teiler, die zweite alle nichttrivialen Quadratteiler, die dritte alle nichttrivialen Kubikteiler und so weiter. Ihre Summe reproduziert die roundness-Summe, ohne die Teiler je explizit aufzuzählen.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst mit einem Sieb alle Primzahlen bis \(n\). Für jede Primzahl \(p\) bestimmen sie \(v_p(n!)\) durch wiederholtes Teilen, also genau die iterative Form der Legendre-Formel. Gleichzeitig bauen sie die Multiplizitäten \(c_e\) auf und speichern den größten Exponenten \(E\).
Sobald die Gruppen \((e,c_e)\) vorliegen, wird zuerst das Startprodukt \(D_1\) berechnet. Danach verarbeitet die Implementierung jeden verschiedenen Exponentenwert unabhängig. Mit der Intervallregel \(r=\lfloor e/q\rfloor\) findet der Code alle \(k\)-Werte, an denen sich \(\lfloor e/k\rfloor\) ändert, und erzeugt jeweils ein Ereignis mit der Sweep-Position und dem modularen Verhältnis, das den Beitrag der gesamten Gruppe aktualisiert. Nachdem alle Gruppen ihre Ereignisse erzeugt haben, werden diese nach \(k\) sortiert.
Der abschließende Sweep läuft von \(k=1\) bis \(k=E\). Bevor der Beitrag eines bestimmten \(k\) addiert wird, wendet die Implementierung alle an dieser Stelle geplanten Ereignisse an. Die zentrale Invariante lautet: Nach Verarbeitung aller Ereignisse bei \(k\) ist das laufende Produkt genau \(D_k\) modulo \(10^9+7\). Zum Ergebnis wird dann \(D_k-1\) addiert, also wieder mit Ausschluss des trivialen Teilers \(1\). Mehr ist algorithmisch nicht nötig.
Sei \(E=v_2(n!)\), und sei \(B\) die Gesamtzahl aller Update-Ereignisse aus sämtlichen verschiedenen Exponentengruppen. Das Primzahlsieb kostet \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Die Berechnung aller Fakultätsexponenten benötigt \(O\!\left(\sum_{p\le n}\log_p n\right)\) arithmetische Schritte.
Anschließend kostet die Ereigniserzeugung \(O(B)\), das Sortieren \(O(B\log B)\) und der Sweep \(O(E+B)\). In der Praxis ist \(B\) viel kleiner als die naive Kostenordnung \(E\cdot\pi(n)\), weil jede Exponentengruppe nur an Quotientensprüngen aktualisiert wird und nicht bei jedem einzelnen \(k\). Der Speicherverbrauch ist \(O(n+B)\), dominiert vom Sieb und der Ereignisliste.
Pozitif bir \(m=\prod p_i^{a_i}\) sayısı için roundness, \(m\)'nin tam bir \(r\). kuvvet olmasını sağlayan en büyük \(r\ge 1\) değeridir. Trivial olmayan her \(m\) için bu
$$\rho(m)=\gcd(a_1,a_2,\dots)$$
eşitliğine denktir. Bir \(N\) sayısının total roundness değeri, \(N\)'nin \(1\) dışındaki tüm bölenlerinin roundness toplamıdır:
$$T(N)=\sum_{\substack{d\mid N\\ d>1}}\rho(d).$$
Problem 926, \(T(10^7!)\bmod 10^9+7\) değerini ister. \(1\) böleni özellikle çıkarılır; çünkü \(1\), her \(k\) için tam bir \(k\). kuvvettir ve katman bazlı sayım yapılınca sonsuz fazlalık üretir.
Uygulamalar ne \(10^7!\)'nin bölenlerini tek tek gezer ne de her bölen için ayrı ayrı \(\gcd\) hesabı yapar. Bunun yerine tüm bölenleri faktöriyel içindeki asal üslerle tanımlar, roundness'i tam kuvvet katmanlarının toplamı olarak yazar ve sonra bu katmanları floor bölüm fonksiyonunun kırılma noktaları üzerinde bir taramayla takip eder.
Şöyle yazalım:
$$n!=\prod_{p\le n} p^{e_p},$$
burada her asal üssü Legendre formülüyle verilir:
$$e_p=v_p(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
O halde \(n!\)'nin her böleni
$$d=\prod_{p\le n} p^{a_p},\qquad 0\le a_p\le e_p$$
şeklinde tekil olarak belirlenir. \(d>1\) için yalnızca pozitif üsler önemli olduğundan
$$\rho(d)=\gcd\{a_p:\ a_p>0\}$$
olur. Yani problem aslında tek tek bölenlerden çok, faktöriyel üslerinin çoklu kümesine \(\{e_p\}\) bağlıdır. Kod da tam olarak bu nesneyi çıkarır.
Roundness'i \(g\) olan bir bölen, tam olarak \(k=1,\dots,g\) değerleri için tam bir \(k\). kuvvettir. Bu nedenle
$$\rho(d)=\sum_{k\ge 1}\mathbf{1}\!\left(d\text{ tam bir }k\text{. kuvvettir}\right)$$
yazılabilir. Bunu tüm trivial olmayan bölenler üzerinde toplarsak
$$T(n!)=\sum_{k\ge 1}\#\left\{d\mid n!:\ d>1,\ d\text{ tam bir }k\text{. kuvvet olsun}\right\}$$
elde edilir. Sabit bir \(k\) için \(d=\prod p^{a_p}\) böleninin tam bir \(k\). kuvvet olması, her üssün \(k\)'ya bölünmesine denktir; yani
$$a_p=k b_p,\qquad 0\le b_p\le \left\lfloor\frac{e_p}{k}\right\rfloor.$$
Böyle bölenlerin sayısı
$$D_k-1,\qquad D_k=\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right)$$
olur. \(D_k\), ölçeklenmiş üsler \(b_p\) için bütün seçimleri sayar; bunların içinde \(1\) bölenini veren tümü sıfır seçimi de vardır. Sonundaki \(-1\) tam olarak o yasak seçimi çıkarır.
En büyük faktöriyel üssü \(p=2\) için oluştuğundan toplam şu noktada biter:
$$E=\max_{p\le n} e_p=v_2(n!).$$
Dolayısıyla aranan ifade
$$\boxed{T(n!)=\sum_{k=1}^{E}\left(\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right)-1\right)\pmod{10^9+7}.}$$
\(k=1\) durumunda bu çarpım doğrudan \(\tau(n!)\), yani toplam bölen sayısıdır. Bu yüzden ilk katman \(\tau(n!)-1\) katkısı yapar.
Her \(k\) için çarpımı tüm asallar üzerinden yeniden kurmak yine çok yavaş olurdu. Bu yüzden üç uygulamanın da kullandığı temel sıkıştırma, aynı faktöriyel üssüne sahip asalları bir araya toplamaktır. Şunu tanımlayalım:
$$c_e=\#\left\{p\le n:\ v_p(n!)=e\right\}.$$
O zaman
$$D_k=\prod_{e\ge 1}\left(\left\lfloor\frac{e}{k}\right\rfloor+1\right)^{c_e}$$
olur. Böylece problem tek tek asallarla değil, farklı üs değerleri \(e\) ile indekslenmiş hale gelir. Birçok asal aynı \(e\) değerini paylaştığından bu temsil çok daha küçüktür ama tamamen eşdeğerdir.
Sabit bir \(e\) değeri için yalnızca şu çarpan önemlidir:
$$f_e(k)=\left\lfloor\frac{e}{k}\right\rfloor+1.$$
Bu fonksiyon \(k\) üzerinde parçalı sabittir. Bir sol uç \(l\) için
$$q=\left\lfloor\frac{e}{l}\right\rfloor$$
ise, aynı bölüm değeri
$$r=\left\lfloor\frac{e}{q}\right\rfloor$$
noktasına kadar sürer. Yani tek bir bölüm değeri \(l\le k\le r\) aralığının tamamını kontrol eder. Kod tam olarak bu aralık sınırlarını kullanır. Başlangıçta
$$D_1=\prod_{e\ge 1}(e+1)^{c_e}$$
hesaplanır; sonra çokluğu \(c_e\) olan bir grup eski çarpan \(t_{\text{old}}\)'dan yeni çarpan \(t_{\text{new}}\)'a geçtiğinde akan çarpım
$$\left(\frac{t_{\text{new}}}{t_{\text{old}}}\right)^{c_e} \pmod{10^9+7}$$
ile güncellenir. Modül asal olduğu için bölme, modüler ters üzerinden yapılır. \(k=e+1\) olduğunda o grubun çarpanı kalıcı olarak \(1\)'e düşer; o noktadan sonra bu gruptan başka güncelleme gelmez.
Tek bir grup üzerinden küçük bir örnek, olay mantığını gösterir. \(e=8\) için \(\left\lfloor 8/k\right\rfloor+1\) değerleri
$$9\text{ iken }k=1,\quad 5\text{ iken }k=2,\quad 3\text{ iken }k=3,4,\quad 2\text{ iken }k=5,6,7,8,\quad 1\text{ sonrasında}$$
şeklindedir. Demek ki bu tek grup yalnızca \(k=2,3,5,9\) noktalarında güncelleme üretir. Global algoritma aynı işi her farklı üs grubu için yapar, tüm olayları sıralar ve sonra \(k\) boyunca artan biçimde tarar.
\(n=10\) için Legendre formülü
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7^1$$
sonucunu verir. Dolayısıyla faktöriyel üsleri \(8,4,2,1\)'dir. Buna karşılık gelen katman sayıları
$$\begin{aligned} D_1&=(8+1)(4+1)(2+1)(1+1)=270,\\ D_2&=(4+1)(2+1)(1+1)(0+1)=30,\\ D_3&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_4&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_5&=D_6=D_7=D_8=2. \end{aligned}$$
Bu yüzden
$$T(10!)=(270-1)+(30-1)+(6-1)+(6-1)+4\cdot(2-1)=312.$$
Bu örnek katman formülünün tam anlamını gösterir. İlk katman tüm trivial olmayan bölenleri, ikinci katman tüm trivial olmayan kare bölenleri, üçüncü katman tüm trivial olmayan küp bölenleri sayar. Bu katmanların toplamı, bölenleri açıkça üretmeden roundness toplamını geri verir.
C++, Python ve Java uygulamaları önce bir süzgeçle \(n\)'ye kadar olan asalları üretir. Her asal \(p\) için \(v_p(n!)\) değeri tekrarlı bölmelerle hesaplanır; bu, Legendre formülünün iteratif karşılığıdır. Aynı anda \(c_e\) çoklukları oluşturulur ve en büyük üs \(E\) kaydedilir.
\((e,c_e)\) grupları belli olduktan sonra önce başlangıç çarpımı \(D_1\) hesaplanır. Ardından her farklı üs değeri bağımsız işlenir. Kod, \(r=\lfloor e/q\rfloor\) aralık kuralıyla \(\lfloor e/k\rfloor\) değerinin değiştiği bütün \(k\) noktalarını bulur ve her biri için, tüm grubun katkısını güncelleyecek modüler oranı içeren bir olay üretir. Bütün gruplar olaylarını oluşturduktan sonra bu olaylar \(k\)'ya göre sıralanır.
Son tarama \(k=1\)'den \(k=E\)'ye kadar gider. Belirli bir \(k\) için katkı eklenmeden önce, o konuma planlanmış bütün olaylar uygulanır. Tutulan temel invariant şudur: \(k\) noktasındaki bütün olaylar işlendiğinde akan çarpım tam olarak \(D_k \bmod 10^9+7\) değeridir. Sonra cevaba \(D_k-1\) eklenir; yani yine \(1\) böleni hariç tutulur. Algoritmanın özü bundan ibarettir.
\(E=v_2(n!)\) ve \(B\), tüm farklı üs gruplarının ürettiği toplam güncelleme olayı sayısı olsun. Asal süzgeci \(O(n\log\log n)\) zaman ve \(O(n)\) bellek kullanır. Tüm faktöriyel üslerini hesaplamak \(O\!\left(\sum_{p\le n}\log_p n\right)\) aritmetik adım gerektirir.
Bundan sonra olay üretimi \(O(B)\), sıralama \(O(B\log B)\), son tarama ise \(O(E+B)\) maliyetlidir. Pratikte \(B\), naif \(E\cdot\pi(n)\) yeniden hesaplama maliyetinden çok daha küçüktür; çünkü her üs grubu her \(k\)'da değil, yalnızca bölümün değiştiği kırılma noktalarında güncellenir. Bellek kullanımı \(O(n+B)\) olup asıl yük süzgeç ve olay listesidir.
Para un entero positivo \(m=\prod p_i^{a_i}\), su roundness es el mayor entero \(r\ge 1\) tal que \(m\) es una potencia \(r\)-ésima perfecta. Para todo \(m>1\), esto equivale a
$$\rho(m)=\gcd(a_1,a_2,\dots).$$
La total roundness de \(N\) es la suma de \(\rho(d)\) sobre todos los divisores \(d\mid N\) con \(d>1\):
$$T(N)=\sum_{\substack{d\mid N\\ d>1}}\rho(d).$$
La tarea es calcular \(T(10^7!)\bmod 10^9+7\). El divisor \(1\) se excluye a propósito, porque es una potencia \(k\)-ésima perfecta para todo \(k\), y una suma por capas tendría un término infinito extra si se lo incluyera.
Las implementaciones no enumeran los divisores de \(10^7!\), ni calculan un \(\gcd\) por divisor. En cambio, describen todos los divisores mediante los exponentes primos del factorial, reescriben la roundness como suma sobre capas de potencias perfectas y luego mantienen esas capas con un barrido sobre los puntos donde cambian los cocientes enteros.
Escribimos
$$n!=\prod_{p\le n} p^{e_p},$$
donde cada exponente se obtiene con la fórmula de Legendre:
$$e_p=v_p(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
Entonces cualquier divisor de \(n!\) queda determinado de manera única por
$$d=\prod_{p\le n} p^{a_p},\qquad 0\le a_p\le e_p.$$
Para \(d>1\), solo importan los exponentes positivos, así que
$$\rho(d)=\gcd\{a_p:\ a_p>0\}.$$
Eso significa que la tarea depende únicamente del multiconjunto de exponentes factoriales \(\{e_p\}\). Ese es el verdadero objeto matemático que explotan las implementaciones.
Si un divisor tiene roundness \(g\), entonces es una potencia \(k\)-ésima perfecta exactamente para \(k=1,\dots,g\). Por tanto,
$$\rho(d)=\sum_{k\ge 1}\mathbf{1}\!\left(d\text{ es una potencia perfecta }k\text{-ésima}\right).$$
Al sumar esta identidad sobre todos los divisores no triviales se obtiene
$$T(n!)=\sum_{k\ge 1}\#\left\{d\mid n!:\ d>1,\ d\text{ es una potencia perfecta }k\text{-ésima}\right\}.$$
Fijado \(k\), el divisor \(d=\prod p^{a_p}\) es una potencia \(k\)-ésima perfecta si y solo si cada exponente es múltiplo de \(k\), es decir, si puede escribirse como
$$a_p=k b_p,\qquad 0\le b_p\le \left\lfloor\frac{e_p}{k}\right\rfloor.$$
Por ello, el número de tales divisores es
$$D_k-1,\qquad D_k=\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right).$$
El producto \(D_k\) cuenta todas las elecciones de los exponentes escalados \(b_p\), incluida la elección nula que produce el divisor \(1\). El término \(-1\) elimina exactamente ese caso prohibido.
Como el mayor exponente factorial aparece para \(p=2\), la suma termina en
$$E=\max_{p\le n} e_p=v_2(n!).$$
Así, la identidad central es
$$\boxed{T(n!)=\sum_{k=1}^{E}\left(\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right)-1\right)\pmod{10^9+7}.}$$
Cuando \(k=1\), el producto es simplemente \(\tau(n!)\), el número total de divisores. La primera capa aporta por tanto \(\tau(n!)-1\).
Incluso con la fórmula por capas, recalcular el producto sobre todos los primos para cada \(k\) seguiría siendo demasiado caro. La compresión clave consiste en agrupar todos los primos que comparten el mismo exponente factorial. Definimos
$$c_e=\#\left\{p\le n:\ v_p(n!)=e\right\}.$$
Entonces
$$D_k=\prod_{e\ge 1}\left(\left\lfloor\frac{e}{k}\right\rfloor+1\right)^{c_e}.$$
Ahora el problema ya no está indexado por primos individuales, sino por valores distintos del exponente \(e\). Como muchos primos comparten el mismo valor, esta representación es mucho más compacta y sigue siendo exacta.
Para un valor fijo \(e\), solo importa el factor
$$f_e(k)=\left\lfloor\frac{e}{k}\right\rfloor+1.$$
Esta función es constante por tramos. Si en un extremo izquierdo \(l\) se tiene
$$q=\left\lfloor\frac{e}{l}\right\rfloor,$$
ese mismo cociente se mantiene hasta
$$r=\left\lfloor\frac{e}{q}\right\rfloor.$$
Es decir, un solo valor del cociente controla todo el intervalo \(l\le k\le r\). El código explota justamente esas fronteras. Empieza con
$$D_1=\prod_{e\ge 1}(e+1)^{c_e},$$
y cuando un grupo de multiplicidad \(c_e\) pasa de un factor antiguo \(t_{\text{old}}\) a uno nuevo \(t_{\text{new}}\), el producto acumulado se actualiza con
$$\left(\frac{t_{\text{new}}}{t_{\text{old}}}\right)^{c_e} \pmod{10^9+7}.$$
Como el módulo es primo, esas divisiones se implementan con inversos modulares. Cuando \(k=e+1\), la contribución de ese grupo se vuelve \(1\) para siempre, así que ya no hacen falta más eventos procedentes de él.
Un ejemplo de una sola agrupación deja visible la lógica. Para \(e=8\), los valores de \(\left\lfloor 8/k\right\rfloor+1\) son
$$9\text{ cuando }k=1,\quad 5\text{ cuando }k=2,\quad 3\text{ cuando }k=3,4,\quad 2\text{ cuando }k=5,6,7,8,\quad 1\text{ después}.$$
Así, ese único grupo genera actualizaciones exactamente en \(k=2,3,5,9\). El algoritmo global hace lo mismo para cada exponente distinto, ordena todos los eventos y luego barre \(k\) en orden creciente.
Para \(n=10\), la fórmula de Legendre da
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7^1.$$
Los exponentes factoriales son por tanto \(8,4,2,1\). De ahí salen los conteos por capas
$$\begin{aligned} D_1&=(8+1)(4+1)(2+1)(1+1)=270,\\ D_2&=(4+1)(2+1)(1+1)(0+1)=30,\\ D_3&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_4&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_5&=D_6=D_7=D_8=2. \end{aligned}$$
Por consiguiente,
$$T(10!)=(270-1)+(30-1)+(6-1)+(6-1)+4\cdot(2-1)=312.$$
Este ejemplo muestra exactamente qué significa la fórmula por capas. La primera capa cuenta todos los divisores no triviales, la segunda todos los divisores cuadrados no triviales, la tercera todos los divisores cúbicos no triviales, y así sucesivamente. La suma de esas capas reproduce la suma de roundness sin enumerar los divisores uno por uno.
Las implementaciones en C++, Python y Java generan primero todos los primos hasta \(n\) con una criba. Para cada primo \(p\), evalúan \(v_p(n!)\) mediante divisiones repetidas, que no es más que la forma iterativa de la fórmula de Legendre. A la vez construyen las multiplicidades \(c_e\) y registran el máximo exponente \(E\).
Una vez conocidos los grupos \((e,c_e)\), se calcula el producto inicial \(D_1\). Después se procesa cada valor distinto del exponente por separado. Usando la regla de intervalos \(r=\lfloor e/q\rfloor\), el código localiza todos los valores de \(k\) donde cambia \(\lfloor e/k\rfloor\) y emite un evento con esa posición y con la razón modular que actualiza la contribución de todo el grupo. Cuando todos los grupos han emitido sus eventos, estos se ordenan por \(k\).
El barrido final recorre \(k=1,2,\dots,E\). Antes de añadir la contribución correspondiente a un valor de \(k\), la implementación aplica todos los eventos programados en ese punto. La invariante central es muy simple: después de procesar los eventos de \(k\), el producto acumulado coincide exactamente con \(D_k\) módulo \(10^9+7\). Entonces se suma \(D_k-1\), volviendo a excluir el divisor trivial \(1\). Ese es todo el algoritmo.
Sea \(E=v_2(n!)\), y sea \(B\) el número total de eventos de actualización emitidos por todos los grupos de exponentes distintos. La criba de primos cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Calcular todos los exponentes factoriales requiere \(O\!\left(\sum_{p\le n}\log_p n\right)\) pasos aritméticos.
Después, generar eventos cuesta \(O(B)\), ordenarlos cuesta \(O(B\log B)\), y el barrido cuesta \(O(E+B)\). En la práctica, \(B\) es mucho menor que el coste ingenuo \(E\cdot\pi(n)\), porque cada grupo solo se actualiza en puntos de ruptura del cociente y no para cada valor de \(k\). El uso de memoria es \(O(n+B)\), dominado por la criba y la lista de eventos.
对正整数 \(m=\prod p_i^{a_i}\)，它的 roundness 定义为使 \(m\) 成为完全 \(r\) 次幂的最大整数 \(r\ge 1\)。对任意 \(m>1\)，这就等价于
$$\rho(m)=\gcd(a_1,a_2,\dots).$$
\(N\) 的 total roundness 定义为所有非 1 因子 \(d\mid N\) 的 roundness 之和：
$$T(N)=\sum_{\substack{d\mid N\\ d>1}}\rho(d).$$
题目要求计算 \(T(10^7!)\bmod 10^9+7\)。这里必须排除因子 \(1\)，因为 \(1\) 对任意 \(k\) 都是完全 \(k\) 次幂；如果把它放进按幂次分层的求和里，就会额外产生一个发散项。
实现不会枚举 \(10^7!\) 的所有因子，也不会对每个因子单独求一次 \(\gcd\)。它真正做的是：先用阶乘的素因子指数来描述所有因子，再把 roundness 改写成“完全幂层数”的总和，最后沿着 floor 商发生变化的位置做一次乘法扫描。
先写成
$$n!=\prod_{p\le n} p^{e_p},$$
其中每个素数指数都由 Legendre 公式给出：
$$e_p=v_p(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
于是 \(n!\) 的每个因子都可以唯一写成
$$d=\prod_{p\le n} p^{a_p},\qquad 0\le a_p\le e_p.$$
对 \(d>1\) 而言，只有正指数才有意义，所以
$$\rho(d)=\gcd\{a_p:\ a_p>0\}.$$
这说明题目的核心并不是“因子本身长什么样”，而是阶乘分解中那一组指数 \(\{e_p\}\)。实现处理的正是这个对象。
如果某个因子的 roundness 是 \(g\)，那么它恰好对 \(k=1,\dots,g\) 这些值都是完全 \(k\) 次幂。因此可以写成
$$\rho(d)=\sum_{k\ge 1}\mathbf{1}\!\left(d\text{ 是完全 }k\text{ 次幂}\right).$$
把这个恒等式对所有非平凡因子求和，就得到
$$T(n!)=\sum_{k\ge 1}\#\left\{d\mid n!:\ d>1,\ d\text{ 是完全 }k\text{ 次幂}\right\}.$$
固定一个 \(k\) 以后，因子 \(d=\prod p^{a_p}\) 是完全 \(k\) 次幂，当且仅当每个指数都能被 \(k\) 整除，也就是可以写成
$$a_p=k b_p,\qquad 0\le b_p\le \left\lfloor\frac{e_p}{k}\right\rfloor.$$
因此，这样的因子个数是
$$D_k-1,\qquad D_k=\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right).$$
\(D_k\) 统计了所有缩放后指数 \(b_p\) 的选择，其中包括全部取零时对应的因子 \(1\)。最后的 \(-1\) 就是把这个不允许的因子删掉。
由于最大的阶乘指数出现在 \(p=2\) 上，所以求和只需要做到
$$E=\max_{p\le n} e_p=v_2(n!).$$
于是整个问题化为
$$\boxed{T(n!)=\sum_{k=1}^{E}\left(\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right)-1\right)\pmod{10^9+7}.}$$
当 \(k=1\) 时，这个乘积就是 \(\tau(n!)\)，也就是全部因子的个数，所以第一层的贡献是 \(\tau(n!)-1\)。
即使已经得到分层公式，如果对每个 \(k\) 仍然沿着所有素数重建一次乘积，规模也还是太大。三个实现都使用同一个压缩办法：把拥有相同阶乘指数的素数合并。定义
$$c_e=\#\left\{p\le n:\ v_p(n!)=e\right\}.$$
那么
$$D_k=\prod_{e\ge 1}\left(\left\lfloor\frac{e}{k}\right\rfloor+1\right)^{c_e}.$$
这样一来，问题就不再按素数逐个处理，而是按不同的指数值 \(e\) 来处理。由于许多素数会共享同一个 \(e\)，这个表示法比原始素数列表小得多，但数学上完全等价。
对固定的 \(e\)，真正相关的只是因子
$$f_e(k)=\left\lfloor\frac{e}{k}\right\rfloor+1.$$
它是一个分段常值函数。若某个区间左端点为 \(l\)，并且
$$q=\left\lfloor\frac{e}{l}\right\rfloor,$$
那么同一个商值会一直保持到
$$r=\left\lfloor\frac{e}{q}\right\rfloor.$$
也就是说，一个商值控制整个区间 \(l\le k\le r\)。实现正是利用这些区间边界。程序先计算
$$D_1=\prod_{e\ge 1}(e+1)^{c_e},$$
然后当某个 multiplicity 为 \(c_e\) 的组从旧因子 \(t_{\text{old}}\) 变到新因子 \(t_{\text{new}}\) 时，就把当前乘积乘上
$$\left(\frac{t_{\text{new}}}{t_{\text{old}}}\right)^{c_e} \pmod{10^9+7}.$$
由于模数是素数，分式中的除法通过模逆元完成。当 \(k=e+1\) 时，这一组的贡献会永久变成 \(1\)，因此后面不再需要来自这组的更新事件。
一个单组例子很能说明事件机制。取 \(e=8\)，则 \(\left\lfloor 8/k\right\rfloor+1\) 依次取值
$$9\text{ 在 }k=1,\quad 5\text{ 在 }k=2,\quad 3\text{ 在 }k=3,4,\quad 2\text{ 在 }k=5,6,7,8,\quad 1\text{ 在之后}.$$
所以这一组只会在 \(k=2,3,5,9\) 这些位置产生更新。全局算法对每个不同的指数值都做同样的事，把所有事件按 \(k\) 排序，然后从小到大扫描。
当 \(n=10\) 时，Legendre 公式给出
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7^1.$$
所以阶乘指数就是 \(8,4,2,1\)。对应的分层计数为
$$\begin{aligned} D_1&=(8+1)(4+1)(2+1)(1+1)=270,\\ D_2&=(4+1)(2+1)(1+1)(0+1)=30,\\ D_3&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_4&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_5&=D_6=D_7=D_8=2. \end{aligned}$$
因此
$$T(10!)=(270-1)+(30-1)+(6-1)+(6-1)+4\cdot(2-1)=312.$$
这个例子准确展示了分层公式的含义。第一层数的是全部非 1 因子，第二层数的是全部非 1 平方因子，第三层数的是全部非 1 立方因子，依此类推。把这些层加起来，就得到所有因子的 roundness 总和，而不必显式列出因子。
C++、Python 和 Java 实现都会先用筛法生成不超过 \(n\) 的全部素数。对每个素数 \(p\)，程序通过反复整除来计算 \(v_p(n!)\)，这正是 Legendre 公式的迭代写法。与此同时，程序把相同指数值的出现次数汇总成 \(c_e\)，并记录最大指数 \(E\)。
得到 \((e,c_e)\) 分组后，程序先算出初始乘积 \(D_1\)。接下来每个不同的指数值分别处理。利用区间规则 \(r=\lfloor e/q\rfloor\)，程序定位所有使 \(\lfloor e/k\rfloor\) 发生变化的 \(k\)，并在这些位置生成事件。每个事件保存扫描位置以及更新整组贡献所需的模乘因子。所有组的事件全部生成后，再统一按 \(k\) 排序。
最终扫描从 \(k=1\) 一直到 \(k=E\)。在把某个 \(k\) 的贡献加入答案之前，程序先应用所有安排在这个位置的事件。核心不变量非常直接：处理完位置 \(k\) 的全部事件后，当前乘积就恰好等于 \(D_k \bmod 10^9+7\)。然后答案加上 \(D_k-1\)，也就是继续排除因子 \(1\)。整个算法就是这样完成的。
设 \(E=v_2(n!)\)，再设 \(B\) 为所有不同指数分组一共生成的更新事件总数。素数筛的时间复杂度是 \(O(n\log\log n)\)，空间复杂度是 \(O(n)\)。计算全部阶乘素数指数需要 \(O\!\left(\sum_{p\le n}\log_p n\right)\) 次算术操作。
之后，事件生成是 \(O(B)\)，事件排序是 \(O(B\log B)\)，最终扫描是 \(O(E+B)\)。在实际规模下，\(B\) 远小于朴素方法的 \(E\cdot\pi(n)\) 成本，因为每一组只在 floor 商改变的断点处更新，而不会在每个 \(k\) 都重算。内存使用量为 \(O(n+B)\)，主要由筛法数组和事件列表构成。
Для положительного числа \(m=\prod p_i^{a_i}\) его roundness - это наибольшее целое \(r\ge 1\), при котором \(m\) является точной \(r\)-й степенью. Для любого \(m>1\) это равносильно формуле
$$\rho(m)=\gcd(a_1,a_2,\dots).$$
Total roundness числа \(N\) - это сумма \(\rho(d)\) по всем делителям \(d\mid N\), кроме \(1\):
$$T(N)=\sum_{\substack{d\mid N\\ d>1}}\rho(d).$$
Нужно вычислить \(T(10^7!)\bmod 10^9+7\). Делитель \(1\) исключается специально, потому что он является точной \(k\)-й степенью для любого \(k\), и при послойном подсчете это создало бы бесконечный лишний вклад.
Реализации не перебирают делители \(10^7!\) по одному и не считают \(\gcd\) отдельно для каждого делителя. Вместо этого они описывают все делители через показатели простых в факториале, переписывают roundness как сумму по слоям совершенных степеней, а затем поддерживают эти слои проходом по точкам, где меняются целые частные.
Представим
$$n!=\prod_{p\le n} p^{e_p},$$
где каждый показатель задается формулой Лежандра:
$$e_p=v_p(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
Тогда любой делитель \(n!\) однозначно задается выбором
$$d=\prod_{p\le n} p^{a_p},\qquad 0\le a_p\le e_p.$$
Для \(d>1\) важны только положительные показатели, поэтому
$$\rho(d)=\gcd\{a_p:\ a_p>0\}.$$
Отсюда видно, что задача зависит не от делителей как таковых, а от мультимножества факториальных показателей \(\{e_p\}\). Именно эту структуру и извлекает код.
Если у делителя roundness равна \(g\), то он является точной \(k\)-й степенью ровно для \(k=1,\dots,g\). Поэтому
$$\rho(d)=\sum_{k\ge 1}\mathbf{1}\!\left(d\text{ является точной }k\text{-й степенью}\right).$$
Просуммировав это по всем нетривиальным делителям, получаем
$$T(n!)=\sum_{k\ge 1}\#\left\{d\mid n!:\ d>1,\ d\text{ является точной }k\text{-й степенью}\right\}.$$
Для фиксированного \(k\) делитель \(d=\prod p^{a_p}\) является точной \(k\)-й степенью тогда и только тогда, когда каждый показатель кратен \(k\), то есть
$$a_p=k b_p,\qquad 0\le b_p\le \left\lfloor\frac{e_p}{k}\right\rfloor.$$
Отсюда число таких делителей равно
$$D_k-1,\qquad D_k=\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right).$$
Произведение \(D_k\) считает все выборы масштабированных показателей \(b_p\), включая нулевой выбор, который соответствует делителю \(1\). Последнее \(-1\) удаляет именно этот запрещенный случай.
Так как максимальный показатель факториала достигается при \(p=2\), суммирование заканчивается на
$$E=\max_{p\le n} e_p=v_2(n!).$$
Следовательно, задача сводится к формуле
$$\boxed{T(n!)=\sum_{k=1}^{E}\left(\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right)-1\right)\pmod{10^9+7}.}$$
При \(k=1\) это произведение равно \(\tau(n!)\), то есть числу всех делителей, поэтому первый слой дает вклад \(\tau(n!)-1\).
Даже после перехода к слоям полный пересчет произведения по всем простым для каждого \(k\) остался бы слишком дорогим. Ключевое сжатие состоит в том, чтобы объединить все простые с одинаковым факториальным показателем. Обозначим
$$c_e=\#\left\{p\le n:\ v_p(n!)=e\right\}.$$
Тогда
$$D_k=\prod_{e\ge 1}\left(\left\lfloor\frac{e}{k}\right\rfloor+1\right)^{c_e}.$$
Теперь задача индексируется не отдельными простыми, а различными значениями \(e\). Поскольку многие простые имеют один и тот же показатель, такое представление гораздо компактнее, но математически полностью эквивалентно.
Для фиксированного \(e\) имеет значение только множитель
$$f_e(k)=\left\lfloor\frac{e}{k}\right\rfloor+1.$$
Эта функция кусочно-постоянна. Если в левой точке интервала \(l\)
$$q=\left\lfloor\frac{e}{l}\right\rfloor,$$
то тот же самый частный сохраняется до
$$r=\left\lfloor\frac{e}{q}\right\rfloor.$$
Значит, одно значение частного управляет всем интервалом \(l\le k\le r\). Именно эти границы и использует код. Он начинает с
$$D_1=\prod_{e\ge 1}(e+1)^{c_e},$$
а когда группа кратности \(c_e\) переходит от старого множителя \(t_{\text{old}}\) к новому \(t_{\text{new}}\), текущее произведение домножается на
$$\left(\frac{t_{\text{new}}}{t_{\text{old}}}\right)^{c_e} \pmod{10^9+7}.$$
Так как модуль прост, деление реализуется через модульные обратные элементы. При \(k=e+1\) вклад этой группы навсегда становится равным \(1\), и дальнейшие обновления от нее уже не нужны.
Небольшой пример для одной группы хорошо показывает механику событий. При \(e=8\) значения \(\left\lfloor 8/k\right\rfloor+1\) равны
$$9\text{ при }k=1,\quad 5\text{ при }k=2,\quad 3\text{ при }k=3,4,\quad 2\text{ при }k=5,6,7,8,\quad 1\text{ после этого}.$$
То есть одна эта группа создает обновления ровно в точках \(k=2,3,5,9\). Глобальный алгоритм делает то же самое для каждого различного показателя, сортирует все события и затем идет по \(k\) вверх.
Для \(n=10\) формула Лежандра дает
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7^1.$$
Следовательно, факториальные показатели равны \(8,4,2,1\). Тогда послойные количества равны
$$\begin{aligned} D_1&=(8+1)(4+1)(2+1)(1+1)=270,\\ D_2&=(4+1)(2+1)(1+1)(0+1)=30,\\ D_3&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_4&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_5&=D_6=D_7=D_8=2. \end{aligned}$$
Поэтому
$$T(10!)=(270-1)+(30-1)+(6-1)+(6-1)+4\cdot(2-1)=312.$$
Этот пример точно показывает смысл слоистой формулы. Первый слой считает все нетривиальные делители, второй - все нетривиальные квадратные делители, третий - все нетривиальные кубические делители и так далее. Их сумма восстанавливает сумму roundness без явного перечисления делителей.
Реализации на C++, Python и Java сначала строят решето простых до \(n\). Для каждого простого \(p\) значение \(v_p(n!)\) вычисляется повторным делением, то есть в точности как итеративная версия формулы Лежандра. Одновременно формируются кратности \(c_e\) и запоминается максимальный показатель \(E\).
После того как группы \((e,c_e)\) известны, вычисляется стартовое произведение \(D_1\). Затем каждый различный показатель обрабатывается отдельно. С помощью правила интервалов \(r=\lfloor e/q\rfloor\) код находит все значения \(k\), в которых меняется \(\lfloor e/k\rfloor\), и создает событие, содержащее позицию прохода и модульное отношение, обновляющее вклад всей группы. Когда все группы сгенерировали свои события, эти события сортируются по \(k\).
Финальный проход идет от \(k=1\) до \(k=E\). Перед тем как добавить вклад данного \(k\), программа применяет все события, назначенные на эту позицию. Основной инвариант очень прост: после обработки всех событий в точке \(k\) текущее произведение точно равно \(D_k \bmod 10^9+7\). Затем к ответу добавляется \(D_k-1\), то есть снова с исключением делителя \(1\). На этом алгоритм заканчивается.
Пусть \(E=v_2(n!)\), а \(B\) - общее число событий обновления, порожденных всеми различными группами показателей. Решето простых требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Вычисление всех факториальных показателей занимает \(O\!\left(\sum_{p\le n}\log_p n\right)\) арифметических операций.
Далее генерация событий стоит \(O(B)\), сортировка - \(O(B\log B)\), а итоговый проход - \(O(E+B)\). На практике \(B\) намного меньше наивной стоимости \(E\cdot\pi(n)\), потому что каждая группа обновляется только в точках разрыва частного, а не при каждом значении \(k\). Память имеет порядок \(O(n+B)\) и в основном расходуется на решето и список событий.
إذا كان \(m=\prod p_i^{a_i}\) عددًا صحيحًا موجبًا، فإن roundness الخاصة به هي أكبر قيمة \(r\ge 1\) تجعل \(m\) قوة كاملة من الدرجة \(r\). ولكل \(m>1\) يمكن كتابة ذلك على الصورة
$$\rho(m)=\gcd(a_1,a_2,\dots).$$
أما total roundness للعدد \(N\) فهي مجموع \(\rho(d)\) على جميع القواسم \(d\mid N\) مع استبعاد \(1\):
$$T(N)=\sum_{\substack{d\mid N\\ d>1}}\rho(d).$$
المطلوب هو حساب \(T(10^7!)\bmod 10^9+7\). ويُستبعد القاسم \(1\) عمدًا، لأنه قوة كاملة من الدرجة \(k\) لكل \(k\)، ولو أُدخل في العدّ الطبقي لأضاف مساهمة غير منتهية.
التنفيذ لا يحصي قواسم \(10^7!\) واحدًا واحدًا، ولا يحسب \(\gcd\) لكل قاسم على حدة. الفكرة الحقيقية هي وصف جميع القواسم بواسطة أسس العوامل الأولية في العامل، ثم كتابة roundness على أنها مجموع لطبقات القوى الكاملة، وبعد ذلك تتبع هذه الطبقات بمسح يمر على نقاط تغيّر خارج القسمة الصحيح.
نكتب
$$n!=\prod_{p\le n} p^{e_p},$$
حيث يُحسب كل أس أولي بصيغة ليجاندر:
$$e_p=v_p(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor.$$
وعندئذٍ يتحدد كل قاسم من قواسم \(n!\) بشكل وحيد عن طريق
$$d=\prod_{p\le n} p^{a_p},\qquad 0\le a_p\le e_p.$$
وبالنسبة إلى \(d>1\)، فإن المهم هو الأسس الموجبة فقط، لذا
$$\rho(d)=\gcd\{a_p:\ a_p>0\}.$$
وهذا يبيّن أن المسألة تعتمد في جوهرها على مجموعة الأسس \(\{e_p\}\) في تحليل العامل، لا على القواسم كأعداد منفصلة. وهذا بالضبط ما تستخرجه التطبيقات.
إذا كانت roundness لقاسم ما تساوي \(g\)، فإنه يكون قوة كاملة من الدرجة \(k\) بالضبط للقيم \(k=1,\dots,g\). وإذا رمزنا بمؤشر هذه الخاصية إلى \(I_k(d)\)، حيث \(I_k(d)=1\) عندما يكون \(d\) قوة كاملة من الدرجة \(k\) و\(I_k(d)=0\) خلاف ذلك، أمكن كتابة
$$\rho(d)=\sum_{k\ge 1} I_k(d).$$
وبجمع هذه الهوية على جميع القواسم غير التافهة نحصل على
$$T(n!)=\sum_{k\ge 1}\#\left\{d\mid n!:\ d>1,\ I_k(d)=1\right\}.$$
ولقيمة ثابتة من \(k\)، يكون القاسم \(d=\prod p^{a_p}\) قوة كاملة من الدرجة \(k\) إذا وفقط إذا كان كل أس قابلًا للقسمة على \(k\)، أي يمكن كتابته على الصورة
$$a_p=k b_p,\qquad 0\le b_p\le \left\lfloor\frac{e_p}{k}\right\rfloor.$$
ومن ثم فإن عدد هذه القواسم يساوي
$$D_k-1,\qquad D_k=\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right).$$
الحد \(D_k\) يعدّ جميع اختيارات الأسس المقيّسة \(b_p\)، بما في ذلك الاختيار الصفري الكامل الذي يعطي القاسم \(1\). والطرح بمقدار \(1\) يحذف هذا القاسم الممنوع بالضبط.
وبما أن أكبر أس في \(n!\) يظهر عند \(p=2\)، فإن الجمع يتوقف عند
$$E=\max_{p\le n} e_p=v_2(n!).$$
إذًا تصبح المسألة كلها
$$\boxed{T(n!)=\sum_{k=1}^{E}\left(\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right)-1\right)\pmod{10^9+7}.}$$
وعند \(k=1\) يكون هذا الجداء هو \(\tau(n!)\)، أي عدد جميع القواسم، ولذلك تسهم الطبقة الأولى بمقدار \(\tau(n!)-1\).
حتى بعد الوصول إلى صيغة الطبقات، فإن إعادة بناء الجداء على جميع الأعداد الأولية لكل \(k\) ستبقى بطيئة جدًا. لذلك تجمع التطبيقات كل الأعداد الأولية التي لها الأس العاملِي نفسه. نعرّف
$$c_e=\#\left\{p\le n:\ v_p(n!)=e\right\}.$$
وعندها يصبح
$$D_k=\prod_{e\ge 1}\left(\left\lfloor\frac{e}{k}\right\rfloor+1\right)^{c_e}.$$
وبذلك لا يعود الفهرس هو الأعداد الأولية نفسها، بل القيم المختلفة للأس \(e\). ولأن كثيرًا من الأعداد الأولية يشترك في القيمة نفسها، فإن هذا التمثيل أصغر بكثير مع بقائه مطابقًا رياضيًا للصيغة الأصلية.
إذا ثبتنا قيمة \(e\)، فإن العامل المهم هو فقط
$$f_e(k)=\left\lfloor\frac{e}{k}\right\rfloor+1.$$
وهذه دالة ثابتة على فترات. فإذا كان
$$q=\left\lfloor\frac{e}{l}\right\rfloor$$
عند الطرف الأيسر \(l\)، فإن هذا الخارج يبقى ثابتًا حتى
$$r=\left\lfloor\frac{e}{q}\right\rfloor.$$
أي إن قيمة واحدة من الخارج تتحكم في الفترة كلها \(l\le k\le r\). والشفرة تستغل حدود هذه الفترات تحديدًا. فهي تبدأ من
$$D_1=\prod_{e\ge 1}(e+1)^{c_e},$$
ثم إذا انتقلت مجموعة ذات تعدد \(c_e\) من عامل قديم \(t_{\text{old}}\) إلى عامل جديد \(t_{\text{new}}\)، فإن الجداء الجاري يُحدَّث بالكمية
$$\left(\frac{t_{\text{new}}}{t_{\text{old}}}\right)^{c_e} \pmod{10^9+7}.$$
ولأن المودولو عدد أولي، فإن القسمة هنا تُنفذ بواسطة المعكوسات الضربية المعيارية. وعند \(k=e+1\) يصبح إسهام تلك المجموعة مساويًا لـ \(1\) بشكل دائم، فلا تبقى حاجة إلى أحداث أخرى منها.
يوضح مثال مجموعة واحدة آلية الأحداث جيدًا. إذا كان \(e=8\)، فإن قيم \(\left\lfloor 8/k\right\rfloor+1\) تكون كما يلي:
$$k=1\mapsto 9,\quad k=2\mapsto 5,\quad k=3,4\mapsto 3,\quad k=5,6,7,8\mapsto 2,\quad k\ge 9\mapsto 1.$$
إذن هذه المجموعة الواحدة تولد تحديثات فقط عند \(k=2,3,5,9\). والخوارزمية الكاملة تفعل الشيء نفسه لكل قيمة مختلفة من \(e\)، ثم ترتب جميع الأحداث بحسب \(k\) وتقوم بمسح تصاعدي.
عندما \(n=10\)، تعطي صيغة ليجاندر
$$10!=2^8\cdot 3^4\cdot 5^2\cdot 7^1.$$
إذن الأسس العاملية هي \(8,4,2,1\). ومن ثم تكون أعداد الطبقات
$$\begin{aligned} D_1&=(8+1)(4+1)(2+1)(1+1)=270,\\ D_2&=(4+1)(2+1)(1+1)(0+1)=30,\\ D_3&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_4&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_5&=D_6=D_7=D_8=2. \end{aligned}$$
وبالتالي
$$T(10!)=(270-1)+(30-1)+(6-1)+(6-1)+4\cdot(2-1)=312.$$
هذا المثال يوضح المعنى الدقيق لصيغة الطبقات. فالطبقة الأولى تعدّ جميع القواسم غير التافهة، والثانية تعدّ جميع القواسم المربعة غير التافهة، والثالثة تعدّ جميع القواسم التكعيبية غير التافهة، وهكذا. ومجموع هذه الطبقات يعيد مجموع roundness من دون تعداد القواسم صراحة.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع الأعداد الأولية حتى \(n\) باستخدام غربال. ثم تحسب لكل عدد أولي \(p\) القيمة \(v_p(n!)\) عبر القسمة المتكررة، وهي الصيغة التكرارية المباشرة لقاعدة ليجاندر. وفي الوقت نفسه تُبنى المضاعفات \(c_e\) ويُسجل أكبر أس \(E\).
بعد معرفة الأزواج \((e,c_e)\)، يُحسب أولًا الجداء الابتدائي \(D_1\). ثم تُعالج كل قيمة مختلفة من \(e\) على حدة. وباستخدام قاعدة الفترات \(r=\lfloor e/q\rfloor\)، تحدد الشفرة جميع قيم \(k\) التي يتغير عندها \(\lfloor e/k\rfloor\)، وتولد عند كل قيمة حدثًا يحمل موضع المسح والنسبة المعيارية التي تُحدث إسهام المجموعة كلها. وبعد أن تنهي جميع المجموعات توليد أحداثها، تُرتب هذه الأحداث بحسب \(k\).
يمتد المسح النهائي من \(k=1\) حتى \(k=E\). وقبل إضافة مساهمة قيمة معينة من \(k\)، تطبق الشفرة جميع الأحداث المجدولة عند تلك القيمة. الثابت المركزي بسيط ودقيق: بعد معالجة أحداث الموضع \(k\)، يكون الجداء الجاري مساويًا تمامًا لـ \(D_k \bmod 10^9+7\). ثم يضاف إلى الجواب الحد \(D_k-1\)، أي مع استمرار استبعاد القاسم \(1\). وهذه هي الخوارزمية كاملة.
ليكن \(E=v_2(n!)\)، وليكن \(B\) هو العدد الكلي لأحداث التحديث التي تولدها جميع مجموعات الأسس المختلفة. يكلف الغربال حتى \(n\) زمنًا \(O(n\log\log n)\) وذاكرة \(O(n)\). أما حساب جميع الأسس العاملية فيحتاج إلى \(O\!\left(\sum_{p\le n}\log_p n\right)\) خطوة حسابية.
بعد ذلك تكون كلفة توليد الأحداث \(O(B)\)، وكلفة ترتيبها \(O(B\log B)\)، وكلفة المسح النهائي \(O(E+B)\). وعمليًا يكون \(B\) أصغر بكثير من الكلفة الساذجة \(E\cdot\pi(n)\)، لأن كل مجموعة تُحدَّث فقط عند نقاط كسر الخارج، لا عند كل قيمة من \(k\). أما الذاكرة فترتيبها \(O(n+B)\)، ويهيمن عليها الغربال وقائمة الأحداث.