We need to evaluate
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$$
for \(n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\) and \(m=10^{11}\), then report the last 9 digits. A direct loop over \(10^{11}\) terms is impossible, so the solution must exploit the arithmetic structure of \(n\) and the summatory behavior of Euler's totient.
Let
$$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$$
Since \(n\) is squarefree,
$$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$$
The implementation turns the original sum into a weighted sum of values of \(\Phi\).
Fix an integer \(i\), and write its prime factorization locally as \(p^a\parallel i\). The contribution of each prime to \(\varphi(ni)/\varphi(n)\) depends on whether that prime already divides \(n\).
If \(p\notin P\), then \(p\) is coprime to \(n\), so multiplicativity gives
$$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a).$$
If \(p\in P\), then \(n\) already contains one factor of \(p\), and because \(n\) is squarefree we get
$$\frac{\varphi(np^a)}{\varphi(n)}=p^a.$$
Now use the classical identity
$$\sum_{j=0}^{a}\varphi(p^j)=p^a.$$
Therefore the local factor can be written as
$$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P. \end{cases}$$
Multiplying these local identities over all prime powers dividing \(i\) yields a restricted divisor sum. If we call an integer \(d\) \(P\)-smooth when all prime divisors of \(d\) lie in \(P\), then
$$\boxed{\varphi(ni)=\varphi(n)\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).}$$
This is the crucial transformation behind the whole solver.
Insert the identity above into \(S(n,m)\):
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni)=\varphi(n)\sum_{i=1}^{m}\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).$$
Now write \(i=dk\). For each fixed \(P\)-smooth \(d\le m\), the inner variable \(k\) ranges from \(1\) to \(\left\lfloor m/d\right\rfloor\). Hence
$$S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\sum_{k\le m/d}\varphi(k).$$
With the summatory totient function \(\Phi\), this becomes
$$\boxed{S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\Phi\!\left(\left\lfloor\frac{m}{d}\right\rfloor\right).}$$
So the original problem is reduced to two tasks:
1. enumerate all \(P\)-smooth numbers \(d\le m\);
2. evaluate \(\Phi(x)\) quickly for the quotients \(x=\left\lfloor m/d\right\rfloor\).
Because \(P\) has only seven primes, every relevant \(d\) has the form
$$d=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}\le 10^{11}.$$
A depth-first search over the exponent choices generates every such value exactly once. This is practical because the smoothness condition is extremely restrictive compared with all integers up to \(10^{11}\).
For the actual parameters, the enumeration contains only \(152751\) smooth numbers. Many of them lead to the same quotient \(\left\lfloor m/d\right\rfloor\), so the implementation deduplicates those quotients before evaluating \(\Phi\).
The key identity is
$$\sum_{d\mid t}\varphi(d)=t.$$
Summing over \(1\le t\le x\) gives
$$\sum_{t=1}^{x} t=\sum_{t=1}^{x}\sum_{d\mid t}\varphi(d)=\sum_{u=1}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).$$
If we write the triangular number as
$$T(x)=\frac{x(x+1)}{2},$$
then isolating the \(u=1\) term yields the recursion
$$\boxed{\Phi(x)=T(x)-\sum_{u=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).}$$
The floor quotient stays constant on intervals. If
$$q=\left\lfloor\frac{x}{\ell}\right\rfloor,\qquad r=\left\lfloor\frac{x}{q}\right\rfloor,$$
then \(\left\lfloor x/u\right\rfloor=q\) for every \(u\in[\ell,r]\), so the recursion can be blocked as
$$\Phi(x)=T(x)-\sum_{\text{quotient blocks}}(r-\ell+1)\,\Phi(q).$$
This reduces the work dramatically, because the number of distinct floor quotients is only \(O(\sqrt{x})\). The implementation stores small values in a totient-prefix table and memoizes large recursive calls.
It is helpful to test the formula on a smaller squarefree value, say \(n=6=2\cdot 3\) and \(m=5\). Then \(P=\{2,3\}\), \(\varphi(6)=2\), and the \(P\)-smooth numbers up to \(5\) are
$$1,2,3,4.$$
Therefore
$$S(6,5)=2\left(\Phi(5)+\Phi(2)+\Phi(1)+\Phi(1)\right).$$
Since
$$\Phi(1)=1,\qquad \Phi(2)=1+1=2,\qquad \Phi(5)=1+1+2+2+4=10,$$
we get
$$S(6,5)=2(10+2+1+1)=28.$$
Direct verification matches:
$$\varphi(6)+\varphi(12)+\varphi(18)+\varphi(24)+\varphi(30)=2+4+6+8+8=28.$$
The C++, Python, and Java implementations use the same arithmetic strategy. First they factor \(n\), compute \(\varphi(n)\), and generate every \(P\)-smooth number \(d\le m\). Next they form the quotient list \(\left\lfloor m/d\right\rfloor\), sort it, remove duplicates, and evaluate each distinct \(\Phi(q)\) only once.
For small \(q\), the implementation uses a linear totient sieve and prefix sums up to \(12000000\). For larger \(q\), it applies the quotient-block recursion above and memoizes the results. After all required \(\Phi(q)\) values are available, it sums them with multiplicity, multiplies by \(\varphi(n)\), and obtains \(S(n,m)\).
The implementation also validates itself before attacking \(10^{11}\): it compares against direct summation for several small values of \(m\), and it checks the published checkpoint
$$S(510510,10^6)=45480596821125120.$$
The final accumulation can be split across multiple threads, but the arithmetic formula itself is unchanged.
Let \(A(m)\) be the number of \(P\)-smooth integers \(d\le m\), and let
$$Q(m)=\#\left\{\left\lfloor\frac{m}{d}\right\rfloor : d\le m,\ d\text{ is }P\text{-smooth}\right\}.$$
Enumerating the smooth numbers costs \(O(A(m))\). Sorting and deduplicating the quotients costs \(O(A(m)\log A(m))\). Each new summatory-totient value \(\Phi(q)\) is computed by quotient blocking plus memoization, so a single uncached query touches only the distinct floor-division blocks, which is \(O(\sqrt{q})\) in the classical analysis.
For the actual input,
$$A(10^{11})=152751,\qquad Q(10^{11})=20313,$$
which explains why the method is feasible even though the original sum has \(10^{11}\) terms. Memory usage is dominated by the totient-prefix table, the memoization cache, and the arrays storing the smooth numbers and quotient values.
Gesucht ist
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$$
für \(n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\) und \(m=10^{11}\); ausgegeben werden die letzten 9 Ziffern. Eine direkte Summation über \(10^{11}\) Terme ist unmöglich, daher nutzt die Lösung die quadratfreie Struktur von \(n\) und eine schnelle Berechnung der summierten Phi-Funktion.
Setze
$$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$$
Da \(n\) quadratfrei ist, gilt
$$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$$
Die Implementierung verwandelt die ursprüngliche Summe in eine gewichtete Summe von Werten der Funktion \(\Phi\).
Fixiere ein \(i\), und betrachte lokal eine Primzahlpotenz \(p^a\parallel i\). Der Beitrag jedes Prims zu \(\varphi(ni)/\varphi(n)\) hängt davon ab, ob \(p\) bereits in \(n\) vorkommt.
Für \(p\notin P\) ist \(p\) teilerfremd zu \(n\), also liefert die Multiplikativität
$$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a).$$
Für \(p\in P\) enthält \(n\) bereits genau einen Faktor \(p\), und wegen der Quadratfreiheit folgt
$$\frac{\varphi(np^a)}{\varphi(n)}=p^a.$$
Nun verwendet man die klassische Identität
$$\sum_{j=0}^{a}\varphi(p^j)=p^a.$$
Damit lässt sich der lokale Faktor schreiben als
$$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P. \end{cases}$$
Multipliziert man diese lokalen Beiträge über alle Primzahlpotenzen von \(i\), erhält man eine eingeschränkte Teilersumme. Nennen wir eine Zahl \(d\) \(P\)-glatt, wenn alle Primteiler von \(d\) in \(P\) liegen. Dann gilt
$$\boxed{\varphi(ni)=\varphi(n)\sum_{\substack{d\mid i\\ d\text{ ist }P\text{-glatt}}}\varphi\!\left(\frac{i}{d}\right).}$$
Diese Umformung ist der zentrale Schritt der gesamten Lösung.
Setzt man diese Identität in \(S(n,m)\) ein, so erhält man
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni)=\varphi(n)\sum_{i=1}^{m}\sum_{\substack{d\mid i\\ d\text{ ist }P\text{-glatt}}}\varphi\!\left(\frac{i}{d}\right).$$
Schreibt man nun \(i=dk\), dann läuft für jedes feste \(P\)-glatte \(d\le m\) die Variable \(k\) von \(1\) bis \(\left\lfloor m/d\right\rfloor\). Also
$$S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ ist }P\text{-glatt}}}\sum_{k\le m/d}\varphi(k).$$
Mit der summierten Phi-Funktion wird daraus
$$\boxed{S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ ist }P\text{-glatt}}}\Phi\!\left(\left\lfloor\frac{m}{d}\right\rfloor\right).}$$
Damit reduziert sich das Problem auf zwei Teilaufgaben:
1. alle \(P\)-glatten Zahlen \(d\le m\) erzeugen;
2. \(\Phi(x)\) für die Quotienten \(x=\left\lfloor m/d\right\rfloor\) schnell berechnen.
Da \(P\) nur aus sieben Primzahlen besteht, hat jedes relevante \(d\) die Form
$$d=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}\le 10^{11}.$$
Eine Tiefensuche über die Exponenten erzeugt jeden solchen Wert genau einmal. Das ist praktikabel, weil die Glattheitsbedingung viel restriktiver ist als eine Betrachtung aller Zahlen bis \(10^{11}\).
Für die echten Parameter entstehen nur \(152751\) glatte Zahlen. Viele davon liefern denselben Quotienten \(\left\lfloor m/d\right\rfloor\), deshalb entfernt die Implementierung diese Wiederholungen vor der Berechnung von \(\Phi\).
Die Ausgangsidentität lautet
$$\sum_{d\mid t}\varphi(d)=t.$$
Summiert über \(1\le t\le x\) ergibt das
$$\sum_{t=1}^{x} t=\sum_{t=1}^{x}\sum_{d\mid t}\varphi(d)=\sum_{u=1}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).$$
Mit der Dreieckszahl
$$T(x)=\frac{x(x+1)}{2}$$
folgt durch Herausziehen des Terms \(u=1\)
$$\boxed{\Phi(x)=T(x)-\sum_{u=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).}$$
Der Quotient \(\left\lfloor x/u\right\rfloor\) bleibt auf ganzen Intervallen konstant. Sind
$$q=\left\lfloor\frac{x}{\ell}\right\rfloor,\qquad r=\left\lfloor\frac{x}{q}\right\rfloor,$$
dann gilt \(\left\lfloor x/u\right\rfloor=q\) für alle \(u\in[\ell,r]\). Die Rekursion lässt sich also blockweise schreiben als
$$\Phi(x)=T(x)-\sum_{\text{Quotientenblöcke}}(r-\ell+1)\,\Phi(q).$$
Dadurch sinkt der Aufwand stark, denn die Anzahl verschiedener Quotienten ist nur \(O(\sqrt{x})\). Kleine Werte speichert die Implementierung in einer Totient-Präfixtabelle, große rekursive Werte werden memoisiert.
Zum Verständnis ist ein kleineres quadratfreies Beispiel hilfreich, etwa \(n=6=2\cdot 3\) und \(m=5\). Dann ist \(P=\{2,3\}\), \(\varphi(6)=2\), und die \(P\)-glatten Zahlen bis \(5\) sind
$$1,2,3,4.$$
Daher
$$S(6,5)=2\left(\Phi(5)+\Phi(2)+\Phi(1)+\Phi(1)\right).$$
Weil
$$\Phi(1)=1,\qquad \Phi(2)=1+1=2,\qquad \Phi(5)=1+1+2+2+4=10,$$
erhält man
$$S(6,5)=2(10+2+1+1)=28.$$
Die direkte Kontrolle stimmt überein:
$$\varphi(6)+\varphi(12)+\varphi(18)+\varphi(24)+\varphi(30)=2+4+6+8+8=28.$$
Die C++-, Python- und Java-Implementierungen verwenden dieselbe arithmetische Strategie. Zuerst werden \(n\) faktorisiert, \(\varphi(n)\) berechnet und alle \(P\)-glatten Zahlen \(d\le m\) erzeugt. Danach entsteht die Quotientenliste \(\left\lfloor m/d\right\rfloor\); diese wird sortiert, dedupliziert und für jeden verschiedenen Wert \(q\) genau einmal \(\Phi(q)\) berechnet.
Für kleine \(q\) nutzt die Implementierung ein lineares Totient-Sieb mit Präfixsummen bis \(12000000\). Für größere \(q\) kommt die blockweise Quotientenrekursion mit Memoisierung zum Einsatz. Sind alle benötigten \(\Phi(q)\)-Werte vorhanden, werden sie mit ihren Vielfachheiten aufsummiert und anschließend mit \(\varphi(n)\) multipliziert.
Bevor der eigentliche Fall \(10^{11}\) berechnet wird, validiert sich die Implementierung selbst: Sie vergleicht mehrere kleine Werte von \(m\) mit direkter Summation und prüft zusätzlich den veröffentlichten Kontrollwert
$$S(510510,10^6)=45480596821125120.$$
Die abschließende Akkumulation kann außerdem auf mehrere Threads verteilt werden; an der mathematischen Formel ändert das nichts.
Sei \(A(m)\) die Anzahl der \(P\)-glatten Zahlen \(d\le m\), und sei
$$Q(m)=\#\left\{\left\lfloor\frac{m}{d}\right\rfloor : d\le m,\ d\text{ ist }P\text{-glatt}\right\}.$$
Das Erzeugen der glatten Zahlen kostet \(O(A(m))\). Das Sortieren und Deduplizieren der Quotienten kostet \(O(A(m)\log A(m))\). Jeder neue Wert \(\Phi(q)\) wird per Quotientenblock-Zerlegung und Memoisierung berechnet, sodass eine einzelne noch nicht gecachte Anfrage im klassischen Sinn nur \(O(\sqrt{q})\) verschiedene Blöcke berührt.
Für die eigentliche Eingabe gilt
$$A(10^{11})=152751,\qquad Q(10^{11})=20313,$$
und genau deshalb ist die Methode praktikabel, obwohl die Ursprungssumme \(10^{11}\) Terme besitzt. Der Speicherbedarf wird vor allem durch die Totient-Präfixtabelle, den Memoisierungscache sowie die Arrays für glatte Zahlen und Quotienten bestimmt.
Hesaplanmak istenen toplam
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$$
ifadesidir. Burada \(n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\) ve \(m=10^{11}\) olup sonuçtan son 9 basamak istenir. \(10^{11}\) terimi tek tek toplamak mümkün olmadığı için çözüm, \(n\)'nin karesiz yapısını ve Euler phi fonksiyonunun kümülatif davranışını kullanır.
Şöyle tanımlayalım:
$$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$$
\(n\) karesiz olduğundan
$$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$$
Uygulama, orijinal toplamı \(\Phi\) değerlerinin ağırlıklı bir toplamına dönüştürür.
Bir \(i\) sayısını sabitleyelim ve \(p^a\parallel i\) olan bir asal kuvveti inceleyelim. \(\varphi(ni)/\varphi(n)\) içindeki yerel katkı, o asalin \(n\)'yi bölüp bölmemesine göre değişir.
Eğer \(p\notin P\) ise \(p\), \(n\) ile aralarında asaldır ve çarpımsallıktan
$$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a)$$
gelir.
Eğer \(p\in P\) ise \(n\) zaten tam bir tane \(p\) çarpanı içerir; \(n\) karesiz olduğu için
$$\frac{\varphi(np^a)}{\varphi(n)}=p^a$$
olur.
Şimdi klasik özdeşliği kullanalım:
$$\sum_{j=0}^{a}\varphi(p^j)=p^a.$$
Böylece yerel çarpan şu biçimde yazılabilir:
$$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P. \end{cases}$$
Bu yerel özdeşlikleri \(i\)'yi bölen tüm asal kuvvetler üzerinde çarptığımızda, kısıtlı bir bölen toplamı elde ederiz. Tüm asal bölenleri \(P\) kümesinde olan \(d\) sayısına \(P\)-smooth diyelim. O halde
$$\boxed{\varphi(ni)=\varphi(n)\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).}$$
Tüm çözücünün temel dönüşümü budur.
Bu özdeşliği \(S(n,m)\) içine yerleştirirsek
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni)=\varphi(n)\sum_{i=1}^{m}\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right)$$
olur.
Şimdi \(i=dk\) yazalım. Sabit bir \(P\)-smooth \(d\le m\) için iç değişken \(k\), \(1\) ile \(\left\lfloor m/d\right\rfloor\) arasında değişir. Böylece
$$S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\sum_{k\le m/d}\varphi(k).$$
\(\Phi\) tanımıyla bu ifade
$$\boxed{S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\Phi\!\left(\left\lfloor\frac{m}{d}\right\rfloor\right).}$$
şeklini alır. Böylece problem iki alt göreve iner:
1. \(d\le m\) olan tüm \(P\)-smooth sayıları üretmek;
2. \(x=\left\lfloor m/d\right\rfloor\) değerleri için \(\Phi(x)\)'i hızlı hesaplamak.
\(P\) sadece yedi asal içerdiği için her ilgili \(d\) şu biçimdedir:
$$d=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}\le 10^{11}.$$
Üsler üzerinde derinlik öncelikli arama yapılarak bu değerlerin her biri tam bir kez üretilir. Bu yöntem uygulanabilirdir, çünkü smooth koşulu, \(10^{11}\)'e kadarki tüm sayılara bakmaktan çok daha dar bir küme bırakır.
Gerçek parametrelerde bu sayım yalnızca \(152751\) adet smooth sayı üretir. Bunların önemli bir kısmı aynı \(\left\lfloor m/d\right\rfloor\) bölümünü verdiğinden, uygulama \(\Phi\) hesaplamasından önce bu bölümleri tekilleştirir.
Temel özdeşlik şudur:
$$\sum_{d\mid t}\varphi(d)=t.$$
Bunu \(1\le t\le x\) için toplarsak
$$\sum_{t=1}^{x} t=\sum_{t=1}^{x}\sum_{d\mid t}\varphi(d)=\sum_{u=1}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right)$$
elde edilir.
Üçgensel toplamı
$$T(x)=\frac{x(x+1)}{2}$$
olarak yazarsak ve \(u=1\) terimini ayırırsak
$$\boxed{\Phi(x)=T(x)-\sum_{u=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).}$$
Taban bölüm değeri aralıklarda sabittir. Eğer
$$q=\left\lfloor\frac{x}{\ell}\right\rfloor,\qquad r=\left\lfloor\frac{x}{q}\right\rfloor$$
ise, \(u\in[\ell,r]\) için \(\left\lfloor x/u\right\rfloor=q\) olur. Dolayısıyla özyineleme bloklanmış biçimde
$$\Phi(x)=T(x)-\sum_{\text{bölüm blokları}}(r-\ell+1)\,\Phi(q)$$
şeklinde uygulanabilir. Böylece iş yükü büyük ölçüde azalır; çünkü farklı bölüm sayısı yalnızca \(O(\sqrt{x})\) mertebesindedir. Uygulama küçük değerleri önceden hesaplanmış bir phi-önek tablosunda, büyük değerleri ise memoization ile saklar.
Formülü küçük bir karesiz örnek üzerinde görmek yararlıdır: \(n=6=2\cdot 3\) ve \(m=5\). Bu durumda \(P=\{2,3\}\), \(\varphi(6)=2\), ve \(5\)'e kadar olan \(P\)-smooth sayılar
$$1,2,3,4$$
olur.
Dolayısıyla
$$S(6,5)=2\left(\Phi(5)+\Phi(2)+\Phi(1)+\Phi(1)\right).$$
Şunları kullanırsak
$$\Phi(1)=1,\qquad \Phi(2)=1+1=2,\qquad \Phi(5)=1+1+2+2+4=10,$$
şu sonucu elde ederiz:
$$S(6,5)=2(10+2+1+1)=28.$$
Doğrudan kontrol de aynısını verir:
$$\varphi(6)+\varphi(12)+\varphi(18)+\varphi(24)+\varphi(30)=2+4+6+8+8=28.$$
C++, Python ve Java implementasyonları aynı aritmetik stratejiyi kullanır. Önce \(n\)'nin asal çarpanları çıkarılır, \(\varphi(n)\) hesaplanır ve tüm \(P\)-smooth \(d\le m\) değerleri üretilir. Daha sonra \(\left\lfloor m/d\right\rfloor\) listesi oluşturulur, sıralanır, tekrar edenler silinir ve her farklı \(q\) için \(\Phi(q)\) yalnızca bir kez hesaplanır.
Küçük \(q\) değerlerinde uygulama \(12000000\)'ye kadar lineer phi eleği ve önek toplamları kullanır. Daha büyük \(q\) için yukarıdaki bölüm-bloklu özyineleme memoization ile çalıştırılır. Gerekli tüm \(\Phi(q)\) değerleri hazır olduğunda bunlar tekrar sayılarıyla toplanır ve sonuç \(\varphi(n)\) ile çarpılır.
Uygulama \(10^{11}\) hedefine geçmeden önce kendini doğrular: birkaç küçük \(m\) değeri için doğrudan toplama ile karşılaştırma yapar ve ayrıca şu kontrol değerini sınar:
$$S(510510,10^6)=45480596821125120.$$
Son toplama işlemi isteğe bağlı olarak birden fazla iş parçacığına bölünebilir; fakat kullanılan matematiksel formül değişmez.
\(A(m)\), \(d\le m\) olan \(P\)-smooth sayıların sayısı olsun. Ayrıca
$$Q(m)=\#\left\{\left\lfloor\frac{m}{d}\right\rfloor : d\le m,\ d\text{ is }P\text{-smooth}\right\}$$
olsun.
Smooth sayıların üretilmesi \(O(A(m))\) zaman alır. Bölümlerin sıralanıp tekilleştirilmesi \(O(A(m)\log A(m))\) maliyetlidir. Her yeni \(\Phi(q)\) değeri, bölüm blokları ve memoization ile hesaplandığından, klasik analizde tek bir önbelleksiz sorgu yalnızca \(O(\sqrt{q})\) kadar farklı blok gezer.
Gerçek girdi için
$$A(10^{11})=152751,\qquad Q(10^{11})=20313,$$
olur. Orijinal toplam \(10^{11}\) terim içerse de yöntemin uygulanabilir olmasının nedeni budur. Bellek kullanımını esas olarak phi-önek tablosu, memoization önbelleği ve smooth sayı ile bölüm dizileri belirler.
Debemos evaluar
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$$
con \(n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\) y \(m=10^{11}\), y luego tomar sus últimos 9 dígitos. Una suma directa sobre \(10^{11}\) términos es inviable, así que la solución aprovecha que \(n\) es libre de cuadrados y que la función totiente acumulada puede calcularse mucho más rápido que término a término.
Definimos
$$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$$
Como \(n\) es libre de cuadrados, se obtiene
$$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$$
La implementación transforma la suma original en una suma ponderada de valores de \(\Phi\).
Fijemos un entero \(i\) y consideremos localmente una potencia prima \(p^a\parallel i\). La contribución de cada primo a \(\varphi(ni)/\varphi(n)\) depende de si ese primo ya divide a \(n\).
Si \(p\notin P\), entonces \(p\) es coprimo con \(n\), y por multiplicatividad
$$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a).$$
Si \(p\in P\), entonces \(n\) ya contiene exactamente un factor \(p\), y como \(n\) es libre de cuadrados tenemos
$$\frac{\varphi(np^a)}{\varphi(n)}=p^a.$$
Ahora usamos la identidad clásica
$$\sum_{j=0}^{a}\varphi(p^j)=p^a.$$
Por tanto, el factor local puede escribirse como
$$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P. \end{cases}$$
Al multiplicar estas identidades locales sobre todos los primos que dividen a \(i\), aparece una suma restringida sobre divisores. Diremos que \(d\) es \(P\)-smooth si todos sus divisores primos pertenecen a \(P\). Entonces
$$\boxed{\varphi(ni)=\varphi(n)\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).}$$
Este es el paso decisivo de toda la solución.
Sustituyendo la identidad anterior en \(S(n,m)\), obtenemos
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni)=\varphi(n)\sum_{i=1}^{m}\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).$$
Ahora escribimos \(i=dk\). Para cada \(d\) \(P\)-smooth fijo con \(d\le m\), la variable \(k\) recorre \(1\le k\le \left\lfloor m/d\right\rfloor\). Así,
$$S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\sum_{k\le m/d}\varphi(k).$$
Usando la función totiente acumulada \(\Phi\), esto se convierte en
$$\boxed{S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\Phi\!\left(\left\lfloor\frac{m}{d}\right\rfloor\right).}$$
Por tanto, el problema se reduce a dos tareas:
1. enumerar todos los \(d\) \(P\)-smooth con \(d\le m\);
2. calcular rápidamente \(\Phi(x)\) para los cocientes \(x=\left\lfloor m/d\right\rfloor\).
Como \(P\) solo tiene siete primos, todo \(d\) relevante tiene la forma
$$d=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}\le 10^{11}.$$
Una búsqueda en profundidad sobre los exponentes genera cada uno de esos valores exactamente una vez. Esto es práctico porque la condición de smooth reduce muchísimo el espacio de búsqueda frente al intervalo completo hasta \(10^{11}\).
Para los parámetros reales solo aparecen \(152751\) números smooth. Muchos de ellos producen el mismo cociente \(\left\lfloor m/d\right\rfloor\), y por eso la implementación deduplica esos cocientes antes de evaluar \(\Phi\).
La identidad básica es
$$\sum_{d\mid t}\varphi(d)=t.$$
Al sumar para \(1\le t\le x\), resulta
$$\sum_{t=1}^{x} t=\sum_{t=1}^{x}\sum_{d\mid t}\varphi(d)=\sum_{u=1}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).$$
Si escribimos el número triangular como
$$T(x)=\frac{x(x+1)}{2},$$
y aislamos el término \(u=1\), obtenemos la recurrencia
$$\boxed{\Phi(x)=T(x)-\sum_{u=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).}$$
El cociente entero permanece constante en intervalos. Si
$$q=\left\lfloor\frac{x}{\ell}\right\rfloor,\qquad r=\left\lfloor\frac{x}{q}\right\rfloor,$$
entonces \(\left\lfloor x/u\right\rfloor=q\) para todo \(u\in[\ell,r]\), y la recurrencia puede agruparse por bloques:
$$\Phi(x)=T(x)-\sum_{\text{bloques de cociente}}(r-\ell+1)\,\Phi(q).$$
Esto reduce drásticamente el trabajo, porque el número de cocientes distintos es solo \(O(\sqrt{x})\). La implementación guarda los valores pequeños en una tabla prefijo de totientes y memoiza las llamadas recursivas grandes.
Para ver la fórmula en acción, consideremos un caso cuadrado-libre pequeño: \(n=6=2\cdot 3\) y \(m=5\). Entonces \(P=\{2,3\}\), \(\varphi(6)=2\), y los números \(P\)-smooth hasta \(5\) son
$$1,2,3,4.$$
Por tanto,
$$S(6,5)=2\left(\Phi(5)+\Phi(2)+\Phi(1)+\Phi(1)\right).$$
Como
$$\Phi(1)=1,\qquad \Phi(2)=1+1=2,\qquad \Phi(5)=1+1+2+2+4=10,$$
se obtiene
$$S(6,5)=2(10+2+1+1)=28.$$
La comprobación directa coincide:
$$\varphi(6)+\varphi(12)+\varphi(18)+\varphi(24)+\varphi(30)=2+4+6+8+8=28.$$
Las implementaciones en C++, Python y Java usan la misma estrategia aritmética. Primero factorizan \(n\), calculan \(\varphi(n)\) y generan todos los valores \(d\) \(P\)-smooth con \(d\le m\). Después forman la lista de cocientes \(\left\lfloor m/d\right\rfloor\), la ordenan, eliminan repeticiones y calculan cada \(\Phi(q)\) distinta una sola vez.
Para \(q\) pequeños, la implementación usa una criba lineal de totientes y sumas prefijo hasta \(12000000\). Para \(q\) más grandes aplica la recurrencia por bloques de cociente con memoización. Una vez disponibles todos los valores \(\Phi(q)\), los suma con su multiplicidad y multiplica el total por \(\varphi(n)\).
Antes de abordar \(10^{11}\), la implementación se valida a sí misma: compara varios valores pequeños de \(m\) con suma directa y además verifica el control publicado
$$S(510510,10^6)=45480596821125120.$$
La acumulación final también puede repartirse entre varios hilos, aunque la fórmula matemática no cambia.
Sea \(A(m)\) el número de enteros \(P\)-smooth \(d\le m\), y sea
$$Q(m)=\#\left\{\left\lfloor\frac{m}{d}\right\rfloor : d\le m,\ d\text{ is }P\text{-smooth}\right\}.$$
Enumerar los números smooth cuesta \(O(A(m))\). Ordenar y deduplicar los cocientes cuesta \(O(A(m)\log A(m))\). Cada nuevo valor \(\Phi(q)\) se calcula mediante bloques de cociente y memoización, de modo que una consulta no cacheada toca solo los bloques distintos de división entera, es decir, \(O(\sqrt{q})\) en el análisis clásico.
Para la entrada real,
$$A(10^{11})=152751,\qquad Q(10^{11})=20313,$$
lo cual explica por qué el método es viable aunque la suma original tenga \(10^{11}\) términos. La memoria está dominada por la tabla prefijo de totientes, la caché de memoización y los arreglos de números smooth y cocientes.
我们要计算
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$$
其中 \(n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\)，\(m=10^{11}\)，最后只取结果的末 9 位。直接枚举 \(10^{11}\) 项显然不可行，因此必须利用 \(n\) 的平方自由结构，以及欧拉函数前缀和的快速算法。
记
$$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$$
由于 \(n\) 是平方自由数，所以
$$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$$
程序的核心是把原问题改写成若干个 \(\Phi\) 值的加权求和。
固定一个整数 \(i\)，并看其中某个素数幂 \(p^a\parallel i\)。\(\varphi(ni)/\varphi(n)\) 的局部贡献取决于这个素数是否已经出现在 \(n\) 中。
若 \(p\notin P\)，则 \(p\) 与 \(n\) 互素，由乘法性可得
$$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a).$$
若 \(p\in P\)，则 \(n\) 中已经恰好含有一个 \(p\)，而且 \(n\) 是平方自由的，因此
$$\frac{\varphi(np^a)}{\varphi(n)}=p^a.$$
再用经典恒等式
$$\sum_{j=0}^{a}\varphi(p^j)=p^a,$$
于是局部因子可以写成
$$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P. \end{cases}$$
把这些局部恒等式对所有 \(i\) 的素因子相乘，就会得到一个受限的约数求和。若把所有素因子都属于 \(P\) 的整数称为 \(P\)-smooth，则有
$$\boxed{\varphi(ni)=\varphi(n)\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).}$$
这就是整个求解器最关键的变形。
把上式代入 \(S(n,m)\)，得到
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni)=\varphi(n)\sum_{i=1}^{m}\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).$$
现在写成 \(i=dk\)。对每个固定的 \(P\)-smooth 数 \(d\le m\)，内层变量 \(k\) 满足 \(1\le k\le \left\lfloor m/d\right\rfloor\)。因此
$$S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\sum_{k\le m/d}\varphi(k).$$
用前缀函数 \(\Phi\) 表示，就是
$$\boxed{S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\Phi\!\left(\left\lfloor\frac{m}{d}\right\rfloor\right).}$$
这样原问题就变成两部分：
1. 枚举所有满足 \(d\le m\) 的 \(P\)-smooth 数；
2. 快速计算所有形如 \(\left\lfloor m/d\right\rfloor\) 的 \(\Phi\) 值。
由于 \(P\) 只有七个素数，每个相关的 \(d\) 都可以写成
$$d=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}\le 10^{11}.$$
对这些指数做深度优先搜索，就能把所有这样的 \(d\) 恰好生成一次。这是可行的，因为 smooth 条件把搜索空间从“所有不超过 \(10^{11}\) 的整数”缩小到了一个很小的集合。
对真实参数而言，枚举出来的 smooth 数只有 \(152751\) 个。其中很多 \(d\) 会对应同一个商 \(\left\lfloor m/d\right\rfloor\)，所以程序先把这些商去重，再去计算 \(\Phi\)。
基本恒等式是
$$\sum_{d\mid t}\varphi(d)=t.$$
对 \(1\le t\le x\) 求和，可得
$$\sum_{t=1}^{x} t=\sum_{t=1}^{x}\sum_{d\mid t}\varphi(d)=\sum_{u=1}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).$$
若把三角数记为
$$T(x)=\frac{x(x+1)}{2},$$
把 \(u=1\) 这一项单独拿出来，就得到递推式
$$\boxed{\Phi(x)=T(x)-\sum_{u=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).}$$
整除商会在一段区间内保持不变。若
$$q=\left\lfloor\frac{x}{\ell}\right\rfloor,\qquad r=\left\lfloor\frac{x}{q}\right\rfloor,$$
那么对所有 \(u\in[\ell,r]\) 都有 \(\left\lfloor x/u\right\rfloor=q\)。于是可按块写成
$$\Phi(x)=T(x)-\sum_{\text{商块}}(r-\ell+1)\,\Phi(q).$$
这样工作量会显著下降，因为不同的整除商个数只有 \(O(\sqrt{x})\)。程序把较小的值存在 totient 前缀表中，而较大的递归结果通过记忆化复用。
先看一个较小的平方自由例子：\(n=6=2\cdot 3\)，\(m=5\)。这时 \(P=\{2,3\}\)，\(\varphi(6)=2\)，而不超过 \(5\) 的 \(P\)-smooth 数是
$$1,2,3,4.$$
因此
$$S(6,5)=2\left(\Phi(5)+\Phi(2)+\Phi(1)+\Phi(1)\right).$$
又因为
$$\Phi(1)=1,\qquad \Phi(2)=1+1=2,\qquad \Phi(5)=1+1+2+2+4=10,$$
所以
$$S(6,5)=2(10+2+1+1)=28.$$
直接验证也完全一致：
$$\varphi(6)+\varphi(12)+\varphi(18)+\varphi(24)+\varphi(30)=2+4+6+8+8=28.$$
C++、Python 和 Java 实现采用相同的算术路线。它们先分解 \(n\)，求出 \(\varphi(n)\)，并生成所有满足 \(d\le m\) 的 \(P\)-smooth 数。然后构造商列表 \(\left\lfloor m/d\right\rfloor\)，排序、去重，并对每个不同的 \(q\) 只计算一次 \(\Phi(q)\)。
当 \(q\) 较小时，程序使用到 \(12000000\) 为止的线性 phi 筛和前缀和；当 \(q\) 较大时，则调用上面的整除分块递推并配合记忆化。等所有需要的 \(\Phi(q)\) 都准备好后，再按出现次数求和，并乘上 \(\varphi(n)\) 得到 \(S(n,m)\)。
在处理 \(10^{11}\) 之前，程序还会做自检：既对若干较小的 \(m\) 与直接求和比较，也验证题目给出的检查点
$$S(510510,10^6)=45480596821125120.$$
最后的累加阶段还可以按线程分块，但数学公式本身完全不变。
设 \(A(m)\) 是不超过 \(m\) 的 \(P\)-smooth 数个数，并设
$$Q(m)=\#\left\{\left\lfloor\frac{m}{d}\right\rfloor : d\le m,\ d\text{ is }P\text{-smooth}\right\}.$$
枚举 smooth 数的成本是 \(O(A(m))\)。对商进行排序和去重的成本是 \(O(A(m)\log A(m))\)。每个新的 \(\Phi(q)\) 通过整除分块和记忆化求得，因此在经典分析下，一次未缓存查询只会访问 \(O(\sqrt{q})\) 个不同的块。
对本题实际输入，有
$$A(10^{11})=152751,\qquad Q(10^{11})=20313,$$
这正是该方法能够落地的原因，尽管原始求和有 \(10^{11}\) 项。内存主要由 totient 前缀表、记忆化缓存以及 smooth 数和商数组成。
Нужно вычислить
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$$
где \(n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\), \(m=10^{11}\), а затем взять последние 9 цифр результата. Прямое суммирование по \(10^{11}\) значениям нереально, поэтому решение использует квадратсвободность числа \(n\) и быстрый подсчет суммарной функции Эйлера.
Обозначим
$$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$$
Так как \(n\) квадратсвободно, имеем
$$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$$
Программа сводит исходную сумму к взвешенной сумме значений \(\Phi\).
Зафиксируем число \(i\) и рассмотрим локально степень простого \(p^a\parallel i\). Вклад этого простого в \(\varphi(ni)/\varphi(n)\) зависит от того, делит ли \(p\) уже число \(n\).
Если \(p\notin P\), то \(p\) взаимно просто с \(n\), и по мультипликативности
$$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a).$$
Если \(p\in P\), то в \(n\) уже есть ровно один множитель \(p\), и из квадратсвободности следует
$$\frac{\varphi(np^a)}{\varphi(n)}=p^a.$$
Далее используется классическое тождество
$$\sum_{j=0}^{a}\varphi(p^j)=p^a.$$
Поэтому локальный множитель можно записать так:
$$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P. \end{cases}$$
Если перемножить эти локальные формулы по всем простым делителям числа \(i\), получится ограниченная сумма по делителям. Назовем число \(d\) \(P\)-smooth, если все его простые делители лежат в \(P\). Тогда
$$\boxed{\varphi(ni)=\varphi(n)\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).}$$
Именно это преобразование лежит в основе всего метода.
Подставим полученную формулу в \(S(n,m)\):
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni)=\varphi(n)\sum_{i=1}^{m}\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).$$
Теперь запишем \(i=dk\). Для каждого фиксированного \(P\)-smooth числа \(d\le m\) переменная \(k\) пробегает диапазон от \(1\) до \(\left\lfloor m/d\right\rfloor\). Значит,
$$S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\sum_{k\le m/d}\varphi(k).$$
С помощью суммарной функции Эйлера это записывается как
$$\boxed{S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\Phi\!\left(\left\lfloor\frac{m}{d}\right\rfloor\right).}$$
После этого задача распадается на две части:
1. перечислить все \(P\)-smooth числа \(d\le m\);
2. быстро вычислить \(\Phi(x)\) для значений \(x=\left\lfloor m/d\right\rfloor\).
Так как множество \(P\) содержит только семь простых, каждое нужное число \(d\) имеет вид
$$d=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}\le 10^{11}.$$
Поиск в глубину по наборам показателей степеней порождает каждое такое \(d\) ровно один раз. Это практично, потому что условие smooth резко сужает множество кандидатов по сравнению со всеми числами до \(10^{11}\).
Для реальных параметров получается всего \(152751\) smooth-число. Многие из них дают один и тот же частный \(\left\lfloor m/d\right\rfloor\), поэтому программа сначала устраняет повторы, а уже потом вычисляет \(\Phi\).
Базовое тождество имеет вид
$$\sum_{d\mid t}\varphi(d)=t.$$
Просуммируем его по всем \(1\le t\le x\):
$$\sum_{t=1}^{x} t=\sum_{t=1}^{x}\sum_{d\mid t}\varphi(d)=\sum_{u=1}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).$$
Если обозначить треугольное число через
$$T(x)=\frac{x(x+1)}{2},$$
то, выделяя слагаемое \(u=1\), получаем рекурсию
$$\boxed{\Phi(x)=T(x)-\sum_{u=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).}$$
Целая часть \(\left\lfloor x/u\right\rfloor\) постоянна на целых интервалах. Если
$$q=\left\lfloor\frac{x}{\ell}\right\rfloor,\qquad r=\left\lfloor\frac{x}{q}\right\rfloor,$$
то для любого \(u\in[\ell,r]\) выполняется \(\left\lfloor x/u\right\rfloor=q\). Поэтому рекурсию удобно группировать по блокам:
$$\Phi(x)=T(x)-\sum_{\text{блоки частного}}(r-\ell+1)\,\Phi(q).$$
Это резко уменьшает объем работы, поскольку число различных частных равно лишь \(O(\sqrt{x})\). Малые значения программа хранит в префиксной таблице totient, а большие рекурсивные значения кэширует.
Для наглядности возьмем небольшой квадратсвободный пример: \(n=6=2\cdot 3\) и \(m=5\). Тогда \(P=\{2,3\}\), \(\varphi(6)=2\), а \(P\)-smooth числа, не превосходящие \(5\), таковы:
$$1,2,3,4.$$
Следовательно,
$$S(6,5)=2\left(\Phi(5)+\Phi(2)+\Phi(1)+\Phi(1)\right).$$
Поскольку
$$\Phi(1)=1,\qquad \Phi(2)=1+1=2,\qquad \Phi(5)=1+1+2+2+4=10,$$
получаем
$$S(6,5)=2(10+2+1+1)=28.$$
Прямая проверка дает тот же результат:
$$\varphi(6)+\varphi(12)+\varphi(18)+\varphi(24)+\varphi(30)=2+4+6+8+8=28.$$
Реализации на C++, Python и Java используют одну и ту же арифметическую схему. Сначала они раскладывают \(n\) на простые множители, вычисляют \(\varphi(n)\) и порождают все \(P\)-smooth числа \(d\le m\). Затем формируется список частных \(\left\lfloor m/d\right\rfloor\), он сортируется, из него убираются повторы, и каждое различное значение \(\Phi(q)\) вычисляется ровно один раз.
Для малых \(q\) программа использует линейное решето totient и префиксные суммы до \(12000000\). Для больших \(q\) применяется описанная выше рекурсия по блокам частного с кэшированием. После этого все значения \(\Phi(q)\) суммируются с учетом кратности и умножаются на \(\varphi(n)\).
Перед расчетом случая \(10^{11}\) программа проходит проверку: сравнивает несколько малых значений \(m\) с прямым подсчетом и дополнительно проверяет опубликованный контроль
$$S(510510,10^6)=45480596821125120.$$
Финальное накопление также можно распараллелить по потокам, но сама математическая формула при этом не меняется.
Пусть \(A(m)\) обозначает число \(P\)-smooth целых \(d\le m\), а
$$Q(m)=\#\left\{\left\lfloor\frac{m}{d}\right\rfloor : d\le m,\ d\text{ is }P\text{-smooth}\right\}.$$
Перечисление smooth-чисел требует \(O(A(m))\). Сортировка и дедупликация частных требуют \(O(A(m)\log A(m))\). Каждое новое значение \(\Phi(q)\) считается с помощью разбиения по блокам частного и кэширования, поэтому одна незакэшированная заявка в классическом анализе затрагивает лишь \(O(\sqrt{q})\) различных блоков.
Для реального входа имеем
$$A(10^{11})=152751,\qquad Q(10^{11})=20313,$$
и именно это делает метод практически выполнимым, хотя исходная сумма содержит \(10^{11}\) слагаемых. Память в основном расходуется на префиксную таблицу totient, кэш рекурсии и массивы smooth-чисел и частных.
نريد حساب
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$$
حيث \(n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\) و\(m=10^{11}\)، ثم نأخذ آخر 9 أرقام من الناتج. من المستحيل عمليًا جمع \(10^{11}\) حدًا مباشرة، لذلك يعتمد الحل على كون \(n\) خاليًا من المربعات وعلى إمكانية حساب مجموع دالة أويلر التراكمي بسرعة.
لنضع
$$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$$
وبما أن \(n\) خالٍ من المربعات، فإن
$$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$$
الفكرة الأساسية في التنفيذ هي تحويل المجموع الأصلي إلى مجموع موزون لقيم \(\Phi\).
ثبّت عددًا \(i\)، وانظر إلى قوة أولية محلية \(p^a\parallel i\). مساهمة هذا العدد الأولي في \(\varphi(ni)/\varphi(n)\) تعتمد على ما إذا كان \(p\) يقسم \(n\) أصلًا أم لا.
إذا كان \(p\notin P\)، فإن \(p\) أولي نسبيًا مع \(n\)، ومن خاصية الضربية نحصل على
$$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a).$$
أما إذا كان \(p\in P\)، فإن \(n\) يحتوي أصلًا على عامل واحد فقط من \(p\)، ولأن \(n\) خالٍ من المربعات نحصل على
$$\frac{\varphi(np^a)}{\varphi(n)}=p^a.$$
الآن نستخدم الهوية الكلاسيكية
$$\sum_{j=0}^{a}\varphi(p^j)=p^a.$$
ومن ثم يمكن كتابة العامل المحلي على الصورة
$$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P. \end{cases}$$
وعند ضرب هذه الصيغ المحلية على جميع العوامل الأولية لـ \(i\)، نحصل على مجموع مقيد على القواسم. ولنسمّ العدد \(d\) \(P\)-smooth إذا كانت جميع قواسمه الأولية تنتمي إلى \(P\). عندها يصبح
$$\boxed{\varphi(ni)=\varphi(n)\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).}$$
وهذا هو التحويل الحاسم الذي يقوم عليه الحل كله.
بإدخال الهوية السابقة في \(S(n,m)\) نحصل على
$$S(n,m)=\sum_{i=1}^{m}\varphi(ni)=\varphi(n)\sum_{i=1}^{m}\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).$$
الآن نكتب \(i=dk\). ولكل \(d\) ثابت من الأعداد \(P\)-smooth بحيث \(d\le m\)، فإن \(k\) يمتد من \(1\) إلى \(\left\lfloor m/d\right\rfloor\). لذلك
$$S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\sum_{k\le m/d}\varphi(k).$$
وباستخدام الدالة التراكمية \(\Phi\) يصبح هذا
$$\boxed{S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\Phi\!\left(\left\lfloor\frac{m}{d}\right\rfloor\right).}$$
وهكذا تختزل المسألة إلى مهمتين:
1. توليد جميع الأعداد \(P\)-smooth التي لا تتجاوز \(m\)؛
2. حساب \(\Phi(x)\) بسرعة للقيم \(x=\left\lfloor m/d\right\rfloor\).
بما أن \(P\) يحوي سبعة أعداد أولية فقط، فإن كل \(d\) مطلوب يكتب على الصورة
$$d=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}\le 10^{11}.$$
يمكن لتعداد عمقي على الأسس أن يولد كل قيمة من هذه القيم مرة واحدة بالضبط. وهذا عملي لأن شرط smooth يضيق مجموعة المرشحين كثيرًا مقارنة بجميع الأعداد حتى \(10^{11}\).
بالنسبة للمعطيات الفعلية، لا يظهر إلا \(152751\) عددًا smooth. كما أن عددًا كبيرًا منها يعطي نفس الحاصل \(\left\lfloor m/d\right\rfloor\)، ولهذا يقوم التنفيذ بإزالة التكرارات قبل حساب \(\Phi\).
الهوية الأساسية هي
$$\sum_{d\mid t}\varphi(d)=t.$$
وبجمعها على \(1\le t\le x\) نحصل على
$$\sum_{t=1}^{x} t=\sum_{t=1}^{x}\sum_{d\mid t}\varphi(d)=\sum_{u=1}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).$$
إذا كتبنا العدد المثلثي على الصورة
$$T(x)=\frac{x(x+1)}{2},$$
ثم فصلنا الحد الموافق لـ \(u=1\)، نحصل على العلاقة العودية
$$\boxed{\Phi(x)=T(x)-\sum_{u=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).}$$
يبقى خارج القسمة ثابتًا على فترات كاملة. فإذا كان
$$q=\left\lfloor\frac{x}{\ell}\right\rfloor,\qquad r=\left\lfloor\frac{x}{q}\right\rfloor,$$
فإن \(\left\lfloor x/u\right\rfloor=q\) لكل \(u\in[\ell,r]\). ومن ثم يمكن تجميع العودية على شكل كتل:
$$\Phi(x)=T(x)-\sum_{\text{blocks}}(r-\ell+1)\,\Phi(q).$$
وهذا يخفض العمل كثيرًا لأن عدد الحواصل المختلفة لا يتجاوز رتبة \(O(\sqrt{x})\). القيم الصغيرة تحفظ في جدول prefix للـ totient، والقيم الكبيرة يعاد استعمالها عبر memoization.
لرؤية الفكرة بشكل أوضح، خذ مثالًا أصغر حيث \(n=6=2\cdot 3\) و\(m=5\). عندئذٍ \(P=\{2,3\}\)، و\(\varphi(6)=2\)، والأعداد \(P\)-smooth التي لا تتجاوز \(5\) هي
$$1,2,3,4.$$
وبالتالي
$$S(6,5)=2\left(\Phi(5)+\Phi(2)+\Phi(1)+\Phi(1)\right).$$
وبما أن
$$\Phi(1)=1,\qquad \Phi(2)=1+1=2,\qquad \Phi(5)=1+1+2+2+4=10,$$
فإننا نحصل على
$$S(6,5)=2(10+2+1+1)=28.$$
والتحقق المباشر يطابق ذلك:
$$\varphi(6)+\varphi(12)+\varphi(18)+\varphi(24)+\varphi(30)=2+4+6+8+8=28.$$
تعتمد تطبيقات C++ وPython وJava على المسار الحسابي نفسه. فهي تبدأ بتحليل \(n\) إلى عوامله الأولية، ثم تحسب \(\varphi(n)\)، ثم تولد جميع الأعداد \(P\)-smooth التي تحقق \(d\le m\). بعد ذلك تُبنى قائمة الحواصل \(\left\lfloor m/d\right\rfloor\)، وتُرتب، وتُزال التكرارات منها، ويُحسب كل \(\Phi(q)\) مميز مرة واحدة فقط.
بالنسبة للقيم الصغيرة من \(q\)، يستخدم التنفيذ غربالًا خطيًا للـ totient مع مجاميع prefix حتى \(12000000\). أما القيم الأكبر فتُحسب بواسطة العودية المبنية على كتل الحواصل مع التخزين التذكري. وبعد تجهيز جميع قيم \(\Phi(q)\)، تُجمع مع تكراراتها ثم تُضرب في \(\varphi(n)\) للحصول على \(S(n,m)\).
قبل الانتقال إلى الحالة \(10^{11}\)، يقوم التنفيذ بالتحقق من صحة نفسه: فهو يقارن عدة قيم صغيرة من \(m\) مع الجمع المباشر، كما يتحقق من نقطة الفحص المنشورة
$$S(510510,10^6)=45480596821125120.$$
ويمكن أيضًا تقسيم مرحلة الجمع الأخيرة على عدة خيوط، لكن الصيغة الرياضية نفسها لا تتغير.
لتكن \(A(m)\) عدد الأعداد \(P\)-smooth التي لا تتجاوز \(m\)، ولتكن
$$Q(m)=\#\left\{\left\lfloor\frac{m}{d}\right\rfloor : d\le m,\ d\text{ is }P\text{-smooth}\right\}.$$
توليد الأعداد smooth يكلف \(O(A(m))\). أما ترتيب الحواصل وإزالة التكرارات فيكلف \(O(A(m)\log A(m))\). وكل قيمة جديدة من \(\Phi(q)\) تُحسب بواسطة كتل الحواصل مع التخزين التذكري، ولذلك فإن استعلامًا واحدًا غير مخزن يزور فقط \(O(\sqrt{q})\) من الكتل المختلفة في التحليل الكلاسيكي.
في الحالة الفعلية، لدينا
$$A(10^{11})=152751,\qquad Q(10^{11})=20313,$$
وهذا يفسر لماذا تصبح الطريقة عملية رغم أن المجموع الأصلي يحوي \(10^{11}\) حدًا. أما الذاكرة فتسيطر عليها أساسًا جداول prefix للـ totient، وذاكرة memoization، ومصفوفات الأعداد smooth والحواصل.