For each positive integer \(n\), let \(g(n)\) be the largest perfect square dividing \(n\). The problem asks for
$$S(N)=\sum_{n=1}^{N} g(n)$$
with \(N=10^{14}\), and the final result is required modulo \(10^9+7\). The implementations use the checkpoints \(S(10)=24\) and \(S(100)=767\). A direct scan over all \(n\le N\) is hopeless, so the sum has to be reorganized around square divisors rather than around the integers themselves.
The key transformation is to rewrite the problem as a weighted sum over \(m\le \lfloor \sqrt N \rfloor\), where the weights turn out to be the Jordan totient values \(J_2(m)\).
Every positive integer \(n\) can be written uniquely as
$$n=s\,d^2,$$
where \(s\) is squarefree. In that decomposition, the largest square dividing \(n\) is exactly
$$g(n)=d^2.$$
If we group all integers by the value of \(d\), then for a fixed \(d\) the admissible values of \(s\) are precisely the squarefree integers satisfying
$$1\le s\le \left\lfloor\frac{N}{d^2}\right\rfloor.$$
Let \(Q(x)\) denote the number of squarefree integers up to \(x\). Then
$$S(N)=\sum_{d=1}^{\lfloor \sqrt N \rfloor} d^2\,Q\!\left(\left\lfloor\frac{N}{d^2}\right\rfloor\right).$$
This already removes the need to inspect each \(n\) individually.
The indicator of squarefreeness satisfies the classical identity
$$\mathbf{1}_{\mathrm{sqfree}}(t)=\sum_{k^2\mid t}\mu(k),$$
because the Möbius function cancels exactly those integers containing repeated prime factors. Summing this identity for \(1\le t\le x\) gives
$$Q(x)=\sum_{k=1}^{\lfloor \sqrt x \rfloor}\mu(k)\left\lfloor\frac{x}{k^2}\right\rfloor.$$
Substituting \(x=\left\lfloor N/d^2\right\rfloor\) into the previous formula yields
$$S(N)=\sum_{d\le \sqrt N} d^2\sum_{k\le \sqrt{N/d^2}}\mu(k)\left\lfloor\frac{N}{d^2k^2}\right\rfloor.$$
Now let
$$m=d\,k.$$
Every pair \((d,k)\) with \(d^2k^2\le N\) contributes to the term with \(m^2=d^2k^2\). Reordering the sum by \(m\) instead of by the pair \((d,k)\) gives
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor}\left(\sum_{d\mid m}\mu\!\left(\frac{m}{d}\right)d^2\right)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
The inner divisor sum is the coefficient that matters. Once it is identified, the whole problem collapses to a single floor-sum.
Define the Jordan totient of order \(2\) by
$$J_2(m)=\sum_{d\mid m}\mu(d)\left(\frac{m}{d}\right)^2.$$
Replacing \(d\) by \(m/d\) shows that this is exactly the same coefficient as above, so
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
The function \(J_2\) is multiplicative and has the product formula
$$J_2(m)=m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right).$$
For a prime power \(p^e\), this simplifies to
$$J_2(p^e)=p^{2e}-p^{2e-2}.$$
This multiplicative structure is exactly what the sieve exploits.
Start with the values \(m^2\) for all \(m\le \lfloor \sqrt N \rfloor\). Each prime \(p\) contributes the factor \((1-1/p^2)\) to every multiple of \(p\). After every prime has applied its factor, the stored value at index \(m\) becomes
$$m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right)=J_2(m).$$
Therefore the final closed form used by the implementations is
$$\boxed{S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor \pmod{10^9+7}.}$$
Here \(\lfloor\sqrt{10}\rfloor=3\). The Jordan weights are
$$J_2(1)=1,\qquad J_2(2)=4\left(1-\frac14\right)=3,\qquad J_2(3)=9\left(1-\frac19\right)=8.$$
The floor factors are
$$\left\lfloor\frac{10}{1^2}\right\rfloor=10,\qquad \left\lfloor\frac{10}{2^2}\right\rfloor=2,\qquad \left\lfloor\frac{10}{3^2}\right\rfloor=1.$$
So
$$S(10)=1\cdot 10+3\cdot 2+8\cdot 1=24.$$
This matches the direct list of largest square divisors: \(1,1,1,4,1,1,1,4,9,1\).
The C++, Python, and Java implementations first compute the exact integer value \(R=\lfloor\sqrt N\rfloor\). They allocate an array of length \(R+1\) and initialize entry \(m\) with \(m^2\).
Next, they run a prime sieve up to \(R\). Whenever a prime \(p\) is encountered, the implementation visits every multiple of \(p\) and applies the multiplicative factor \((p^2-1)/p^2\). After this pass, the array stores \(J_2(m)\) for every \(1\le m\le R\).
Finally, the implementation loops over \(m=1,2,\dots,R\), computes \(\lfloor N/m^2\rfloor\), multiplies that count by the precomputed Jordan weight, and accumulates the result modulo \(10^9+7\). The arithmetic is entirely integer-based, so the only care points are an exact square root and safe modular multiplication.
Let \(R=\lfloor\sqrt N\rfloor\). Initializing the array costs \(O(R)\). The sieve that applies the prime factors behaves like a totient-style sieve and runs in \(O(R\log\log R)\) time. The final weighted summation is \(O(R)\). The memory usage is \(O(R)\).
Für jede positive ganze Zahl \(n\) sei \(g(n)\) der größte vollkommene Quadrat-Teiler von \(n\). Gesucht ist
$$S(N)=\sum_{n=1}^{N} g(n)$$
für \(N=10^{14}\), wobei das Endergebnis modulo \(10^9+7\) ausgegeben werden soll. Die Implementierungen verwenden die Kontrollwerte \(S(10)=24\) und \(S(100)=767\). Ein direkter Durchlauf über alle \(n\le N\) ist unmöglich, deshalb muss man die Summe nach Quadratteilern und nicht nach einzelnen Zahlen umordnen.
Die zentrale Umformung besteht darin, das Problem als gewichtete Summe über \(m\le \lfloor \sqrt N \rfloor\) zu schreiben, wobei die Gewichte die Jordan-Totientfunktion zweiter Ordnung \(J_2(m)\) sind.
Jede positive ganze Zahl \(n\) besitzt eine eindeutige Darstellung
$$n=s\,d^2,$$
wobei \(s\) quadratfrei ist. In dieser Darstellung ist der größte Quadrat-Teiler von \(n\) genau
$$g(n)=d^2.$$
Gruppieren wir alle Zahlen nach dem Wert von \(d\), dann sind für festes \(d\) genau die quadratfreien \(s\) zulässig mit
$$1\le s\le \left\lfloor\frac{N}{d^2}\right\rfloor.$$
Bezeichne \(Q(x)\) als Anzahl der quadratfreien Zahlen bis \(x\). Dann gilt
$$S(N)=\sum_{d=1}^{\lfloor \sqrt N \rfloor} d^2\,Q\!\left(\left\lfloor\frac{N}{d^2}\right\rfloor\right).$$
Damit muss man nicht mehr jede Zahl einzeln betrachten.
Der Indikator für Quadratfreiheit erfüllt die klassische Identität
$$\mathbf{1}_{\mathrm{sqfree}}(t)=\sum_{k^2\mid t}\mu(k),$$
denn die Möbiusfunktion eliminiert genau die Zahlen mit wiederholten Primfaktoren. Summiert man dies für \(1\le t\le x\), so erhält man
$$Q(x)=\sum_{k=1}^{\lfloor \sqrt x \rfloor}\mu(k)\left\lfloor\frac{x}{k^2}\right\rfloor.$$
Setzt man \(x=\left\lfloor N/d^2\right\rfloor\) in die vorige Formel ein, folgt
$$S(N)=\sum_{d\le \sqrt N} d^2\sum_{k\le \sqrt{N/d^2}}\mu(k)\left\lfloor\frac{N}{d^2k^2}\right\rfloor.$$
Nun setzen wir
$$m=d\,k.$$
Jedes Paar \((d,k)\) mit \(d^2k^2\le N\) trägt zu dem Term mit \(m^2=d^2k^2\) bei. Ordnet man die Summe nach \(m\) statt nach dem Paar \((d,k)\), ergibt sich
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor}\left(\sum_{d\mid m}\mu\!\left(\frac{m}{d}\right)d^2\right)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
Die innere Teilersumme ist also der entscheidende Koeffizient.
Die Jordan-Totientfunktion zweiter Ordnung ist definiert durch
$$J_2(m)=\sum_{d\mid m}\mu(d)\left(\frac{m}{d}\right)^2.$$
Durch die Ersetzung \(d\mapsto m/d\) sieht man, dass dies genau derselbe Koeffizient ist wie oben. Also
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
Die Funktion \(J_2\) ist multiplikativ und besitzt die Produktdarstellung
$$J_2(m)=m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right).$$
Für eine Primzahlpotenz \(p^e\) vereinfacht sich das zu
$$J_2(p^e)=p^{2e}-p^{2e-2}.$$
Genau diese multiplikative Struktur nutzt das Sieb aus.
Man startet mit den Werten \(m^2\) für alle \(m\le \lfloor \sqrt N \rfloor\). Jede Primzahl \(p\) liefert den Faktor \((1-1/p^2)\) für jedes Vielfache von \(p\). Nachdem alle Primzahlen verarbeitet wurden, steht an Position \(m\) genau
$$m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right)=J_2(m).$$
Damit reduziert sich das Problem auf die geschlossene Formel
$$\boxed{S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor \pmod{10^9+7}.}$$
Hier ist \(\lfloor\sqrt{10}\rfloor=3\). Die Jordan-Gewichte lauten
$$J_2(1)=1,\qquad J_2(2)=4\left(1-\frac14\right)=3,\qquad J_2(3)=9\left(1-\frac19\right)=8.$$
Die zugehörigen Abrundungen sind
$$\left\lfloor\frac{10}{1^2}\right\rfloor=10,\qquad \left\lfloor\frac{10}{2^2}\right\rfloor=2,\qquad \left\lfloor\frac{10}{3^2}\right\rfloor=1.$$
Daraus folgt
$$S(10)=1\cdot 10+3\cdot 2+8\cdot 1=24.$$
Das stimmt mit der direkten Liste der größten Quadrat-Teiler überein: \(1,1,1,4,1,1,1,4,9,1\).
Die C++-, Python- und Java-Implementierungen bestimmen zuerst den exakten ganzzahligen Wert \(R=\lfloor\sqrt N\rfloor\). Dann wird ein Array der Länge \(R+1\) angelegt und der Eintrag \(m\) mit \(m^2\) initialisiert.
Anschließend läuft ein Primzahlsieb bis \(R\). Immer wenn eine Primzahl \(p\) erkannt wird, besucht die Implementierung alle Vielfachen von \(p\) und wendet den Faktor \((p^2-1)/p^2\) an. Nach diesem Schritt steht für jedes \(1\le m\le R\) genau der Wert \(J_2(m)\) im Array.
Zum Schluss iteriert die Implementierung über \(m=1,2,\dots,R\), berechnet \(\lfloor N/m^2\rfloor\), multipliziert diesen Wert mit dem vorberechneten Jordan-Gewicht und akkumuliert alles modulo \(10^9+7\). Kritisch sind nur eine exakte Ganzzahlwurzel und sichere modulare Multiplikation.
Sei \(R=\lfloor\sqrt N\rfloor\). Das Initialisieren des Arrays kostet \(O(R)\). Das Sieb mit den Primfaktor-Updates verhält sich wie ein klassisches Totient-Sieb und benötigt \(O(R\log\log R)\) Zeit. Die abschließende gewichtete Summe kostet \(O(R)\). Der Speicherverbrauch beträgt \(O(R)\).
Her pozitif tamsayı \(n\) için \(g(n)\), \(n\)'yi bölen en büyük tam kare olsun. Problemde istenen büyüklük
$$S(N)=\sum_{n=1}^{N} g(n)$$
ifadesidir; burada \(N=10^{14}\) ve sonuç \(10^9+7\) modunda alınır. Uygulamaların kullandığı kontrol değerleri \(S(10)=24\) ve \(S(100)=767\)'dir. Tüm \(n\le N\) değerlerini tek tek dolaşmak mümkün olmadığı için toplamı sayılar üzerinden değil, kare bölenler üzerinden yeniden düzenlemek gerekir.
Ana dönüşüm, problemi \(m\le \lfloor \sqrt N \rfloor\) için kurulan ağırlıklı bir toplama çevirmektir. Bu ağırlıkların Jordan totient fonksiyonunun ikinci dereceden hali olan \(J_2(m)\) olduğu ortaya çıkar.
Her pozitif tamsayı \(n\) tek biçimde
$$n=s\,d^2$$
şeklinde yazılabilir; burada \(s\) karekökten arındırılmıştır, yani squarefree'dir. Bu gösterimde \(n\)'yi bölen en büyük tam kare tam olarak
$$g(n)=d^2$$
olur. Sayıları \(d\) değerine göre gruplayınca, sabit bir \(d\) için mümkün olan \(s\) değerleri sadece
$$1\le s\le \left\lfloor\frac{N}{d^2}\right\rfloor$$
eşitsizliğini sağlayan squarefree sayılardır. \(Q(x)\), \(x\)'e kadar olan squarefree sayı sayısı olsun. O zaman
$$S(N)=\sum_{d=1}^{\lfloor \sqrt N \rfloor} d^2\,Q\!\left(\left\lfloor\frac{N}{d^2}\right\rfloor\right)$$
elde edilir. Böylece her \(n\)'yi ayrı ayrı inceleme zorunluluğu ortadan kalkar.
Squarefree olmanın gösterge fonksiyonu için klasik özdeşlik
$$\mathbf{1}_{\mathrm{sqfree}}(t)=\sum_{k^2\mid t}\mu(k)$$
geçerlidir. Bunun nedeni, Möbius fonksiyonunun tekrarlı asal çarpan içeren sayıları tam olarak iptal etmesidir. Bu özdeşliği \(1\le t\le x\) için toplarsak
$$Q(x)=\sum_{k=1}^{\lfloor \sqrt x \rfloor}\mu(k)\left\lfloor\frac{x}{k^2}\right\rfloor$$
sonucunu elde ederiz. Bunu \(x=\left\lfloor N/d^2\right\rfloor\) için yerine koyunca
$$S(N)=\sum_{d\le \sqrt N} d^2\sum_{k\le \sqrt{N/d^2}}\mu(k)\left\lfloor\frac{N}{d^2k^2}\right\rfloor$$
olur.
Şimdi
$$m=d\,k$$
yazalım. \(d^2k^2\le N\) koşulunu sağlayan her \((d,k)\) çifti, \(m^2=d^2k^2\) terimine katkı yapar. Toplamı \((d,k)\) çiftleri yerine \(m\) üzerinden yeniden düzenlersek
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor}\left(\sum_{d\mid m}\mu\!\left(\frac{m}{d}\right)d^2\right)\left\lfloor\frac{N}{m^2}\right\rfloor$$
ifadesine ulaşırız. Asıl kritik katsayı içteki bölen toplamıdır.
İkinci dereceden Jordan totient fonksiyonunu
$$J_2(m)=\sum_{d\mid m}\mu(d)\left(\frac{m}{d}\right)^2$$
şeklinde tanımlayalım. \(d\mapsto m/d\) dönüşümüyle bunun yukarıdaki iç katsayıyla aynı olduğu görülür. Dolayısıyla
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor$$
olur. \(J_2\) çarpımsaldır ve
$$J_2(m)=m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right)$$
çarpım formuna sahiptir. Bir asal kuvvet için bu
$$J_2(p^e)=p^{2e}-p^{2e-2}$$
şeklinde sadeleşir. Eleğin kullandığı yapı tam olarak budur.
Başlangıçta tüm \(m\le \lfloor \sqrt N \rfloor\) için değerleri \(m^2\) olarak alırız. Her asal \(p\), kendi katlarına \((1-1/p^2)\) çarpanını uygular. Bütün asallar işlendiğinde, \(m\) konumunda tutulan değer
$$m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right)=J_2(m)$$
olur. Böylece uygulamanın kullandığı nihai kapalı form
$$\boxed{S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor \pmod{10^9+7}.}$$
Burada \(\lfloor\sqrt{10}\rfloor=3\) olur. Jordan ağırlıkları
$$J_2(1)=1,\qquad J_2(2)=4\left(1-\frac14\right)=3,\qquad J_2(3)=9\left(1-\frac19\right)=8$$
şeklindedir. Zemin fonksiyonundan gelen çarpanlar ise
$$\left\lfloor\frac{10}{1^2}\right\rfloor=10,\qquad \left\lfloor\frac{10}{2^2}\right\rfloor=2,\qquad \left\lfloor\frac{10}{3^2}\right\rfloor=1$$
olur. O halde
$$S(10)=1\cdot 10+3\cdot 2+8\cdot 1=24$$
elde edilir. Bu sonuç, en büyük kare bölenlerin doğrudan listesiyle de uyuşur: \(1,1,1,4,1,1,1,4,9,1\).
C++, Python ve Java uygulamaları önce \(R=\lfloor\sqrt N\rfloor\) değerini tam sayı olarak hesaplar. Ardından uzunluğu \(R+1\) olan bir dizi ayrılır ve \(m\) indisindeki başlangıç değeri \(m^2\) yapılır.
Sonraki aşamada \(R\)'ye kadar bir asal eleği çalıştırılır. Bir asal \(p\) bulunduğunda uygulama \(p\)'nin tüm katlarını gezer ve her birine \((p^2-1)/p^2\) çarpanını uygular. Bu işlem bittiğinde dizi, tüm \(1\le m\le R\) için \(J_2(m)\) değerlerini içerir.
Son adımda uygulama \(m=1,2,\dots,R\) üzerinden geçer, \(\lfloor N/m^2\rfloor\) hesabını yapar, bunu önceden hazırlanmış Jordan ağırlığıyla çarpar ve sonucu \(10^9+7\) modunda toplar. Kritik noktalar, tam sayı karekök hesabı ve mod alınmadan önce güvenli çarpımdır.
\(R=\lfloor\sqrt N\rfloor\) olsun. Diziyi başlatmak \(O(R)\) sürer. Asal çarpan güncellemelerini yapan elek, klasik totient benzeri eleklere benzer ve \(O(R\log\log R)\) zamanda çalışır. Son ağırlıklı toplama \(O(R)\) maliyetlidir. Bellek kullanımı \(O(R)\) düzeyindedir.
Para cada entero positivo \(n\), sea \(g(n)\) el mayor cuadrado perfecto que divide a \(n\). La cantidad buscada es
$$S(N)=\sum_{n=1}^{N} g(n)$$
con \(N=10^{14}\), y el resultado final debe darse módulo \(10^9+7\). Las implementaciones usan como comprobaciones \(S(10)=24\) y \(S(100)=767\). Recorrer todos los \(n\le N\) es inviable, así que la suma debe reorganizarse por divisores cuadrados en lugar de por los enteros uno por uno.
La transformación clave consiste en reescribir el problema como una suma ponderada sobre \(m\le \lfloor \sqrt N \rfloor\), donde los pesos son los valores de la función totiente de Jordan de orden \(2\), \(J_2(m)\).
Todo entero positivo \(n\) se escribe de manera única como
$$n=s\,d^2,$$
donde \(s\) es libre de cuadrados. En esa descomposición, el mayor cuadrado que divide a \(n\) es exactamente
$$g(n)=d^2.$$
Si agrupamos los enteros por el valor de \(d\), entonces para un \(d\) fijo los valores posibles de \(s\) son justamente los enteros libres de cuadrados que cumplen
$$1\le s\le \left\lfloor\frac{N}{d^2}\right\rfloor.$$
Sea \(Q(x)\) el número de enteros libres de cuadrados no mayores que \(x\). Entonces
$$S(N)=\sum_{d=1}^{\lfloor \sqrt N \rfloor} d^2\,Q\!\left(\left\lfloor\frac{N}{d^2}\right\rfloor\right).$$
Con esto ya dejamos de pensar en cada \(n\) por separado.
El indicador de que un número sea libre de cuadrados satisface la identidad clásica
$$\mathbf{1}_{\mathrm{sqfree}}(t)=\sum_{k^2\mid t}\mu(k),$$
porque la función de Möbius cancela exactamente los enteros que contienen algún factor primo repetido. Al sumar esta identidad para \(1\le t\le x\), obtenemos
$$Q(x)=\sum_{k=1}^{\lfloor \sqrt x \rfloor}\mu(k)\left\lfloor\frac{x}{k^2}\right\rfloor.$$
Sustituyendo \(x=\left\lfloor N/d^2\right\rfloor\) en la fórmula anterior resulta
$$S(N)=\sum_{d\le \sqrt N} d^2\sum_{k\le \sqrt{N/d^2}}\mu(k)\left\lfloor\frac{N}{d^2k^2}\right\rfloor.$$
Ahora escribimos
$$m=d\,k.$$
Cada par \((d,k)\) con \(d^2k^2\le N\) aporta al término con \(m^2=d^2k^2\). Si reordenamos la suma por \(m\) en lugar de por el par \((d,k)\), obtenemos
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor}\left(\sum_{d\mid m}\mu\!\left(\frac{m}{d}\right)d^2\right)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
La suma sobre divisores del interior es el coeficiente esencial del método.
Definimos la función totiente de Jordan de orden \(2\) mediante
$$J_2(m)=\sum_{d\mid m}\mu(d)\left(\frac{m}{d}\right)^2.$$
Al sustituir \(d\mapsto m/d\), se ve que es exactamente el mismo coeficiente que aparece arriba. Por tanto
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
La función \(J_2\) es multiplicativa y satisface la fórmula producto
$$J_2(m)=m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right).$$
Para una potencia prima \(p^e\), esto se simplifica a
$$J_2(p^e)=p^{2e}-p^{2e-2}.$$
Esa estructura multiplicativa es la razón por la que una criba funciona tan bien.
Se empieza con los valores \(m^2\) para todos los \(m\le \lfloor \sqrt N \rfloor\). Cada primo \(p\) aporta el factor \((1-1/p^2)\) a todos sus múltiplos. Cuando todos los primos han sido procesados, el valor almacenado en \(m\) es
$$m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right)=J_2(m).$$
Así, la fórmula cerrada que implementan los programas es
$$\boxed{S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor \pmod{10^9+7}.}$$
Aquí \(\lfloor\sqrt{10}\rfloor=3\). Los pesos de Jordan son
$$J_2(1)=1,\qquad J_2(2)=4\left(1-\frac14\right)=3,\qquad J_2(3)=9\left(1-\frac19\right)=8.$$
Los factores de piso son
$$\left\lfloor\frac{10}{1^2}\right\rfloor=10,\qquad \left\lfloor\frac{10}{2^2}\right\rfloor=2,\qquad \left\lfloor\frac{10}{3^2}\right\rfloor=1.$$
Por tanto
$$S(10)=1\cdot 10+3\cdot 2+8\cdot 1=24.$$
Esto coincide con la lista directa de máximos cuadrados divisores: \(1,1,1,4,1,1,1,4,9,1\).
Las implementaciones en C++, Python y Java calculan primero el valor entero exacto \(R=\lfloor\sqrt N\rfloor\). Después reservan un arreglo de longitud \(R+1\) e inicializan la posición \(m\) con \(m^2\).
A continuación ejecutan una criba de primos hasta \(R\). Cada vez que aparece un primo \(p\), la implementación recorre todos los múltiplos de \(p\) y aplica el factor multiplicativo \((p^2-1)/p^2\). Al terminar esa fase, el arreglo contiene \(J_2(m)\) para todo \(1\le m\le R\).
Por último, la implementación recorre \(m=1,2,\dots,R\), calcula \(\lfloor N/m^2\rfloor\), lo multiplica por el peso de Jordan precalculado y acumula el resultado módulo \(10^9+7\). Los únicos puntos delicados son la raíz cuadrada exacta y la multiplicación segura antes de reducir módulo.
Sea \(R=\lfloor\sqrt N\rfloor\). Inicializar el arreglo cuesta \(O(R)\). La criba que aplica las actualizaciones por primos tiene el mismo orden que una criba tipo totiente, es decir, \(O(R\log\log R)\) tiempo. La suma final ponderada cuesta \(O(R)\). La memoria utilizada es \(O(R)\).
对每个正整数 \(n\)，记 \(g(n)\) 为整除 \(n\) 的最大完全平方数。题目要求计算
$$S(N)=\sum_{n=1}^{N} g(n)$$
其中 \(N=10^{14}\)，最终答案对 \(10^9+7\) 取模。实现中使用的校验点是 \(S(10)=24\) 和 \(S(100)=767\)。如果对所有 \(n\le N\) 逐个判断最大平方因子，规模完全不可接受，所以必须先把求和方式改写成更适合筛法的形式。
核心思路是把原问题改写为对 \(m\le \lfloor \sqrt N \rfloor\) 的一个加权求和，而这些权重正好是二阶 Jordan totient 函数 \(J_2(m)\)。
每个正整数 \(n\) 都能唯一写成
$$n=s\,d^2,$$
其中 \(s\) 是平方自由数。按照这个分解，整除 \(n\) 的最大完全平方数就是
$$g(n)=d^2.$$
如果按 \(d\) 来分组，那么对固定的 \(d\)，所有可能的 \(s\) 恰好是满足
$$1\le s\le \left\lfloor\frac{N}{d^2}\right\rfloor$$
的平方自由整数。设 \(Q(x)\) 表示不超过 \(x\) 的平方自由整数个数，则有
$$S(N)=\sum_{d=1}^{\lfloor \sqrt N \rfloor} d^2\,Q\!\left(\left\lfloor\frac{N}{d^2}\right\rfloor\right).$$
这一步已经把“枚举所有 \(n\)”变成了“枚举平方部分 \(d^2\)”。
平方自由性的指示函数满足经典恒等式
$$\mathbf{1}_{\mathrm{sqfree}}(t)=\sum_{k^2\mid t}\mu(k),$$
因为 Möbius 函数会把含有重复素因子的整数完全抵消。把这个恒等式对 \(1\le t\le x\) 求和，可得
$$Q(x)=\sum_{k=1}^{\lfloor \sqrt x \rfloor}\mu(k)\left\lfloor\frac{x}{k^2}\right\rfloor.$$
再把 \(x=\left\lfloor N/d^2\right\rfloor\) 代入上式，就得到
$$S(N)=\sum_{d\le \sqrt N} d^2\sum_{k\le \sqrt{N/d^2}}\mu(k)\left\lfloor\frac{N}{d^2k^2}\right\rfloor.$$
到这里为止，平方自由条件已经被转化成了 Möbius 加权的整除计数。
现在令
$$m=d\,k.$$
只要 \(d^2k^2\le N\)，对应的贡献就会落在 \(m^2=d^2k^2\) 这一层上。于是把求和顺序从 \((d,k)\) 改成按 \(m\) 分类，可得
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor}\left(\sum_{d\mid m}\mu\!\left(\frac{m}{d}\right)d^2\right)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
这样问题被压缩成“先求出一个关于 \(m\) 的系数，再乘上 \(\lfloor N/m^2\rfloor\)”的形式。
定义二阶 Jordan totient 函数
$$J_2(m)=\sum_{d\mid m}\mu(d)\left(\frac{m}{d}\right)^2.$$
把其中的除数变量替换成 \(m/d\)，就会发现它和上一步中的内部系数完全相同。因此
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
\(J_2\) 是乘法函数，并且有积式
$$J_2(m)=m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right).$$
对素数幂 \(p^e\) 而言，它化简为
$$J_2(p^e)=p^{2e}-p^{2e-2}.$$
这正是筛法可以高效构造权重的根本原因。
先把所有 \(m\le \lfloor \sqrt N \rfloor\) 的初值设成 \(m^2\)。然后对每个素数 \(p\)，给它的所有倍数乘上因子 \((1-1/p^2)\)。当所有素数都处理完以后，位置 \(m\) 上保存的值就是
$$m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right)=J_2(m).$$
于是实现中真正使用的闭式就是
$$\boxed{S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor \pmod{10^9+7}.}$$
此时 \(\lfloor\sqrt{10}\rfloor=3\)。相应的 Jordan 权重为
$$J_2(1)=1,\qquad J_2(2)=4\left(1-\frac14\right)=3,\qquad J_2(3)=9\left(1-\frac19\right)=8.$$
而地板函数给出的倍数计数是
$$\left\lfloor\frac{10}{1^2}\right\rfloor=10,\qquad \left\lfloor\frac{10}{2^2}\right\rfloor=2,\qquad \left\lfloor\frac{10}{3^2}\right\rfloor=1.$$
所以
$$S(10)=1\cdot 10+3\cdot 2+8\cdot 1=24.$$
这和直接列出前十个数的最大平方因子 \(1,1,1,4,1,1,1,4,9,1\) 得到的总和完全一致。
C++、Python 和 Java 实现都会先精确计算 \(R=\lfloor\sqrt N\rfloor\)。然后分配一个长度为 \(R+1\) 的数组，把第 \(m\) 项初始化为 \(m^2\)。
接下来，程序在 \(1\) 到 \(R\) 之间执行一次素数筛。每遇到一个素数 \(p\)，就遍历它的所有倍数，并对这些位置应用乘法因子 \((p^2-1)/p^2\)。这样处理结束后，数组中保存的就是每个 \(m\) 对应的 \(J_2(m)\)。
最后，程序遍历 \(m=1,2,\dots,R\)，计算 \(\lfloor N/m^2\rfloor\)，把这个值和预处理好的 Jordan 权重相乘，再对 \(10^9+7\) 取模累加。实现层面真正需要注意的地方只有两点：整数平方根必须精确，模乘前的中间结果不能溢出。
记 \(R=\lfloor\sqrt N\rfloor\)。数组初始化是 \(O(R)\)。应用素数因子的筛法与经典 totient 筛同阶，时间复杂度为 \(O(R\log\log R)\)。最后的加权求和是 \(O(R)\)。空间复杂度为 \(O(R)\)。
Для каждого положительного целого \(n\) обозначим через \(g(n)\) наибольший полный квадрат, делящий \(n\). Требуется вычислить
$$S(N)=\sum_{n=1}^{N} g(n)$$
при \(N=10^{14}\), а итоговый ответ взять по модулю \(10^9+7\). В реализациях используются контрольные значения \(S(10)=24\) и \(S(100)=767\). Прямой перебор всех \(n\le N\) невозможен, поэтому сумму нужно перестроить так, чтобы считать вклад квадратных делителей, а не обрабатывать каждое число отдельно.
Ключевой шаг состоит в том, чтобы переписать задачу как взвешенную сумму по \(m\le \lfloor \sqrt N \rfloor\), где весами оказываются значения функции Жордана второго порядка \(J_2(m)\).
Любое положительное целое \(n\) единственным образом представляется в виде
$$n=s\,d^2,$$
где \(s\) свободно от квадратов. В таком представлении наибольший квадратный делитель числа \(n\) равен
$$g(n)=d^2.$$
Если сгруппировать все числа по значению \(d\), то при фиксированном \(d\) допустимы ровно те значения \(s\), которые свободны от квадратов и удовлетворяют
$$1\le s\le \left\lfloor\frac{N}{d^2}\right\rfloor.$$
Пусть \(Q(x)\) обозначает количество чисел, свободных от квадратов, не превосходящих \(x\). Тогда
$$S(N)=\sum_{d=1}^{\lfloor \sqrt N \rfloor} d^2\,Q\!\left(\left\lfloor\frac{N}{d^2}\right\rfloor\right).$$
Это уже намного лучше, чем смотреть на каждое \(n\) отдельно.
Индикатор свойства “быть свободным от квадратов” удовлетворяет классической формуле
$$\mathbf{1}_{\mathrm{sqfree}}(t)=\sum_{k^2\mid t}\mu(k),$$
потому что функция Мёбиуса уничтожает все числа, содержащие повторяющийся простой множитель. Суммируя это тождество для \(1\le t\le x\), получаем
$$Q(x)=\sum_{k=1}^{\lfloor \sqrt x \rfloor}\mu(k)\left\lfloor\frac{x}{k^2}\right\rfloor.$$
Подставляя сюда \(x=\left\lfloor N/d^2\right\rfloor\), имеем
$$S(N)=\sum_{d\le \sqrt N} d^2\sum_{k\le \sqrt{N/d^2}}\mu(k)\left\lfloor\frac{N}{d^2k^2}\right\rfloor.$$
Теперь положим
$$m=d\,k.$$
Каждая пара \((d,k)\), для которой \(d^2k^2\le N\), дает вклад в слой с \(m^2=d^2k^2\). Если переставить порядок суммирования и группировать слагаемые по \(m\), получится
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor}\left(\sum_{d\mid m}\mu\!\left(\frac{m}{d}\right)d^2\right)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
Внутренняя сумма по делителям и есть тот коэффициент, который нужно уметь быстро вычислять.
Функция Жордана второго порядка определяется формулой
$$J_2(m)=\sum_{d\mid m}\mu(d)\left(\frac{m}{d}\right)^2.$$
После замены делителя \(d\mapsto m/d\) видно, что это в точности тот же коэффициент, что и выше. Следовательно,
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
Функция \(J_2\) мультипликативна и имеет произведение по простым делителям
$$J_2(m)=m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right).$$
Для простой степени \(p^e\) это упрощается до
$$J_2(p^e)=p^{2e}-p^{2e-2}.$$
Именно эта мультипликативная структура и делает решето естественным инструментом.
Сначала для всех \(m\le \lfloor \sqrt N \rfloor\) берутся начальные значения \(m^2\). Затем каждый простой \(p\) вносит множитель \((1-1/p^2)\) во все свои кратные. После обработки всех простых в ячейке с индексом \(m\) остается значение
$$m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right)=J_2(m).$$
Тем самым задача сводится к одной итоговой формуле
$$\boxed{S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor \pmod{10^9+7}.}$$
Здесь \(\lfloor\sqrt{10}\rfloor=3\). Соответствующие веса Жордана равны
$$J_2(1)=1,\qquad J_2(2)=4\left(1-\frac14\right)=3,\qquad J_2(3)=9\left(1-\frac19\right)=8.$$
А значения функции пола таковы:
$$\left\lfloor\frac{10}{1^2}\right\rfloor=10,\qquad \left\lfloor\frac{10}{2^2}\right\rfloor=2,\qquad \left\lfloor\frac{10}{3^2}\right\rfloor=1.$$
Отсюда
$$S(10)=1\cdot 10+3\cdot 2+8\cdot 1=24.$$
Это совпадает с прямым списком наибольших квадратных делителей: \(1,1,1,4,1,1,1,4,9,1\).
Реализации на C++, Python и Java сначала точно вычисляют целое значение \(R=\lfloor\sqrt N\rfloor\). Затем выделяется массив длины \(R+1\), и элемент с индексом \(m\) инициализируется значением \(m^2\).
После этого запускается решето по простым числам до \(R\). Когда встречается простой \(p\), программа проходит по всем его кратным и применяет к ним множитель \((p^2-1)/p^2\). По завершении этой стадии массив содержит \(J_2(m)\) для всех \(1\le m\le R\).
На последнем этапе реализация перебирает \(m=1,2,\dots,R\), вычисляет \(\lfloor N/m^2\rfloor\), умножает это число на заранее подготовленный вес Жордана и накапливает ответ по модулю \(10^9+7\). Важны только точный целочисленный квадратный корень и безопасное умножение перед взятием модуля.
Пусть \(R=\lfloor\sqrt N\rfloor\). Инициализация массива требует \(O(R)\). Решето с простыми обновлениями работает за \(O(R\log\log R)\), как и стандартное тотиентное решето. Финальное взвешенное суммирование стоит \(O(R)\). Память равна \(O(R)\).
لكل عدد صحيح موجب \(n\)، نرمز بـ \(g(n)\) إلى أكبر مربع كامل يقسم \(n\). الكمية المطلوبة هي
$$S(N)=\sum_{n=1}^{N} g(n)$$
عند \(N=10^{14}\)، مع أخذ الناتج النهائي بترديد \(10^9+7\). وتستخدم التطبيقات قيمتي تحقق هما \(S(10)=24\) و \(S(100)=767\). لا يمكن المرور على جميع الأعداد حتى \(N\) مباشرة، لذلك يجب إعادة ترتيب المجموع بحسب القواسم المربعة لا بحسب الأعداد نفسها.
الفكرة الأساسية هي تحويل المسألة إلى مجموع موزون على جميع \(m\le \lfloor \sqrt N \rfloor\)، ثم يتبين أن الأوزان هي قيم دالة جوردان التوتية من الرتبة الثانية \(J_2(m)\).
يمكن كتابة كل عدد صحيح موجب \(n\) بصورة وحيدة على الشكل
$$n=s\,d^2,$$
حيث إن \(s\) عدد خال من المربعات. في هذا التمثيل يكون أكبر مربع كامل يقسم \(n\) هو بالضبط
$$g(n)=d^2.$$
إذا جمعنا الأعداد بحسب قيمة \(d\)، فإن القيم الممكنة لـ \(s\) عند تثبيت \(d\) هي الأعداد الخالية من المربعات التي تحقق
$$1\le s\le \left\lfloor\frac{N}{d^2}\right\rfloor.$$
ولنرمز بـ \(Q(x)\) إلى عدد الأعداد الخالية من المربعات التي لا تتجاوز \(x\). عندئذ نحصل على
$$S(N)=\sum_{d=1}^{\lfloor \sqrt N \rfloor} d^2\,Q\!\left(\left\lfloor\frac{N}{d^2}\right\rfloor\right).$$
بهذا لم نعد بحاجة إلى معالجة كل \(n\) منفردا.
مؤشر كون العدد خاليا من المربعات يحقق العلاقة الكلاسيكية
$$\mathbf{1}_{\mathrm{sqfree}}(t)=\sum_{k^2\mid t}\mu(k),$$
لأن دالة موبيوس تلغي تماما الأعداد التي تحتوي على عامل أولي مكرر. وبجمع هذه العلاقة من \(1\) إلى \(x\) نحصل على
$$Q(x)=\sum_{k=1}^{\lfloor \sqrt x \rfloor}\mu(k)\left\lfloor\frac{x}{k^2}\right\rfloor.$$
وبالتعويض بـ \(x=\left\lfloor N/d^2\right\rfloor\) في الصيغة السابقة نحصل على
$$S(N)=\sum_{d\le \sqrt N} d^2\sum_{k\le \sqrt{N/d^2}}\mu(k)\left\lfloor\frac{N}{d^2k^2}\right\rfloor.$$
الآن نضع
$$m=d\,k.$$
كل زوج \((d,k)\) يحقق \(d^2k^2\le N\) يساهم في الحد الموافق لـ \(m^2=d^2k^2\). وإذا أعدنا ترتيب المجموع بحسب \(m\) بدلا من الزوج \((d,k)\)، فإننا نحصل على
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor}\left(\sum_{d\mid m}\mu\!\left(\frac{m}{d}\right)d^2\right)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
إذن لب المسألة هو فهم هذا المعامل الداخلي وحسابه بسرعة.
نعرف دالة جوردان من الرتبة الثانية بالعلاقة
$$J_2(m)=\sum_{d\mid m}\mu(d)\left(\frac{m}{d}\right)^2.$$
وباستبدال القاسم \(d\) بـ \(m/d\) نرى أن هذه هي بالضبط نفس الكمية الداخلية السابقة، ولذلك
$$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor.$$
الدالة \(J_2\) ضربية، ولها الصيغة
$$J_2(m)=m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right).$$
ولقوة أولية \(p^e\) تختزل إلى
$$J_2(p^e)=p^{2e}-p^{2e-2}.$$
هذه البنية الضربية هي السبب في أن الغربال ينتج الأوزان بكفاءة.
نبدأ بالقيم \(m^2\) لكل \(m\le \lfloor \sqrt N \rfloor\). كل عدد أولي \(p\) يضيف العامل \((1-1/p^2)\) إلى جميع مضاعفاته. وبعد إنهاء جميع الأعداد الأولية تصبح القيمة المخزنة عند الفهرس \(m\) مساوية لـ
$$m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right)=J_2(m).$$
وهكذا تصبح الصيغة النهائية التي تعتمدها التطبيقات
$$\boxed{S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor \pmod{10^9+7}.}$$
هنا لدينا \(\lfloor\sqrt{10}\rfloor=3\). أوزان جوردان هي
$$J_2(1)=1,\qquad J_2(2)=4\left(1-\frac14\right)=3,\qquad J_2(3)=9\left(1-\frac19\right)=8.$$
أما عوامل الدالة الأرضية فهي
$$\left\lfloor\frac{10}{1^2}\right\rfloor=10,\qquad \left\lfloor\frac{10}{2^2}\right\rfloor=2,\qquad \left\lfloor\frac{10}{3^2}\right\rfloor=1.$$
إذن
$$S(10)=1\cdot 10+3\cdot 2+8\cdot 1=24.$$
وهذا يطابق تماما جمع أكبر القواسم المربعة للأعداد العشرة الأولى: \(1,1,1,4,1,1,1,4,9,1\).
تبدأ تطبيقات C++ و Python و Java بحساب القيمة الصحيحة تماما لـ \(R=\lfloor\sqrt N\rfloor\). بعد ذلك تخصص مصفوفة طولها \(R+1\)، وتضع في الموضع \(m\) القيمة الابتدائية \(m^2\).
ثم تشغل غربالا للأعداد الأولية حتى \(R\). وعندما يظهر عدد أولي \(p\)، تمر الشيفرة على جميع مضاعفاته وتطبق العامل الضربي \((p^2-1)/p^2\). بعد انتهاء هذه المرحلة تحتوي المصفوفة على \(J_2(m)\) لكل \(1\le m\le R\).
في المرحلة الأخيرة تمر الشيفرة على \(m=1,2,\dots,R\)، وتحسب \(\lfloor N/m^2\rfloor\)، ثم تضربه في الوزن الجاهز الموافق لـ \(m\)، وتجمع الناتج بترديد \(10^9+7\). والنقطتان اللتان تحتاجان إلى عناية هما الجذر التربيعي الصحيح بدقة، ومنع تجاوز السعة قبل أخذ الترديد.
لنكتب \(R=\lfloor\sqrt N\rfloor\). تهيئة المصفوفة تكلف \(O(R)\). أما الغربال الذي يطبق العوامل الأولية فيعمل بزمن \(O(R\log\log R)\)، وهو نفس الرتبة المعهودة لغربال شبيه بغربال التوتينت. ثم تأتي عملية الجمع النهائية بكلفة \(O(R)\). واستهلاك الذاكرة هو \(O(R)\).