For each ordered coprime pair \((a,b)\) with \(2 \le a,b \le n\), the corresponding Lissajous-curve contribution collapses to a rational expression determined by \(a\), \(b\), and by how the factors \(2\) and \(5\) of \(10\) are distributed between the two frequencies. The goal is to compute the total
$$s(n)=\sum_{\substack{2 \le a,b \le n\\ \gcd(a,b)=1}} w(a,b)$$
exactly for very large \(n\). The implementations therefore keep the integer numerator \(4s(n)\) throughout the calculation and divide by \(4\) only at the end.
Write
$$C_n=\{(a,b):2 \le a,b \le n,\ \gcd(a,b)=1\},\qquad T(k)=\frac{k(k+1)}{2}.$$
The full answer is built from two global coprime sums over \(C_n\), plus a correction on a smaller exceptional set determined only by divisibility with respect to \(10\).
The starting point is
$$\mathbf 1_{\gcd(a,b)=1}=\sum_{d \mid a,\ d \mid b}\mu(d)=\sum_{d \mid \gcd(a,b)}\mu(d).$$
This converts coprime pair sums into divisor sums. Over the full square \(1 \le a,b \le n\), the two basic aggregates become
$$S_{ab}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}ab=\sum_{d=1}^{n}\mu(d)d^2T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)^2,$$
$$S_{a}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}a=\sum_{d=1}^{n}\mu(d)d\,T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\left\lfloor\frac{n}{d}\right\rfloor.$$
These are exactly the two large Möbius sums computed first.
The target sum starts at \(2\), not \(1\), so the boundary contributions must be subtracted. Since
$$\sum_{m=1}^{n} m = T(n),$$
we obtain
$$S_{ab}(n)=S_{ab}^{\ast}(n)-2T(n)+1,$$
$$S_{a}(n)=S_{a}^{\ast}(n)-n-T(n)+1.$$
Hence
$$S_{ab}(n)=\sum_{(a,b)\in C_n}ab,\qquad S_{a}(n)=\sum_{(a,b)\in C_n}a.$$
Because \(C_n\) is symmetric under swapping the coordinates, the same \(S_a(n)\) also equals \(\sum_{(a,b)\in C_n} b\).
Define the bucket map
$$g(m)=\gcd(m,10)\in\{1,2,5,10\}.$$
The correction layer depends only on whether one frequency contributes the factor \(2\) of \(10\) and the other contributes the factor \(5\). That condition is
$$E_n=\{(a,b)\in C_n:g(a)g(b)=10\}.$$
The possible bucket matches are therefore
$$1 \leftrightarrow 10,\qquad 2 \leftrightarrow 5.$$
So the entire non-generic part of the problem reduces to counting coprime pairs in four complementary residue-type buckets.
For any subset \(U \subseteq \{1,\dots,n\}\), define for fixed \(a\)
$$N_U(a)=\sum_{d \mid a}\mu(d)\,\#\{b \in U:d \mid b\},$$
$$W_U(a)=\sum_{d \mid a}\mu(d)\sum_{\substack{b \in U\\ d \mid b}} b.$$
These give the count and weighted sum of \(b\)-values in \(U\) that are coprime to \(a\). The four needed subsets are \(g(b)=10\), \(g(b)=5\), \(g(b)=2\), and \(g(b)=1\), and each one has a closed-form arithmetic progression formula.
If \(g(b)=10\), then \(b\) is a multiple of \(10\). With \(L=\operatorname{lcm}(d,10)\),
$$C_{10}(d)=\left\lfloor\frac{n}{L}\right\rfloor,\qquad Q_{10}(d)=L\,T\left(\left\lfloor\frac{n}{L}\right\rfloor\right).$$
If \(g(b)=5\), then \(b\) is an odd multiple of \(5\). When \(2 \mid d\) there are no such multiples. Otherwise, with \(L=\operatorname{lcm}(d,5)\), \(t=\left\lfloor n/L \right\rfloor\), and \(k=\left\lceil t/2 \right\rceil\),
$$C_{5}(d)=k,\qquad Q_{5}(d)=Lk^2,$$
because \(1+3+\cdots+(2k-1)=k^2\).
If \(g(b)=2\), then \(b\) is even but not divisible by \(5\). When \(5 \mid d\) the count is zero. Otherwise, with \(L=\operatorname{lcm}(d,2)\), \(t=\left\lfloor n/L \right\rfloor\), and \(t_5=\left\lfloor n/(5L) \right\rfloor\),
$$C_{2}(d)=t-t_5,\qquad Q_{2}(d)=L\,T(t)-5L\,T(t_5).$$
If \(g(b)=1\), then \(b\) is coprime to \(10\). When \(\gcd(d,10)\ne 1\) the count is zero. Otherwise, with \(x=\left\lfloor n/d \right\rfloor\), inclusion-exclusion on divisibility by \(2\) and \(5\) gives
$$C_{1}(d)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{5}\right\rfloor+\left\lfloor\frac{x}{10}\right\rfloor,$$
$$Q_{1}(d)=d\left(T(x)-2T\left(\left\lfloor\frac{x}{2}\right\rfloor\right)-5T\left(\left\lfloor\frac{x}{5}\right\rfloor\right)+10T\left(\left\lfloor\frac{x}{10}\right\rfloor\right)\right).$$
For \(g(a)=10\), the value \(b=1\) must be removed afterward, because the global sum begins at \(2\).
Summing the exceptional counts and weighted sums over all \(a\) gives
$$N_{10}(n)=|E_n|,\qquad S_{a,10}(n)=\sum_{(a,b)\in E_n} a,\qquad S_{ab,10}(n)=\sum_{(a,b)\in E_n} ab.$$
The implementations then combine everything as
$$4s(n)=8S_{ab}(n)-12S_a(n)+6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n).$$
Equivalently,
$$s(n)=2S_{ab}(n)-3S_a(n)+\frac{6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n)}{4}.$$
This can also be read pairwise. Every \((a,b)\in C_n\) contributes
$$w(a,b)= \begin{cases} 2ab-\dfrac{3}{2}(a+b), & g(a)g(b)\ne 10,\\[6pt] \dfrac{2ab-3a-3b+4}{4}, & g(a)g(b)=10. \end{cases}$$
So the total is exactly
$$s(n)=\sum_{(a,b)\in C_n} w(a,b).$$
The quarter-factor in the exceptional case is precisely why the programs keep \(4s(n)\) as an integer.
For \(n=10\), the Möbius sums give
$$S_{ab}(10)=1554,\qquad S_a(10)=261.$$
The exceptional set \(E_{10}\) contains \(14\) ordered pairs, including \((2,5)\), \((3,10)\), \((5,8)\), \((10,3)\), and \((10,9)\). Its totals are
$$N_{10}(10)=14,\qquad S_{a,10}(10)=89,\qquad S_{ab,10}(10)=580.$$
Therefore
$$\begin{aligned} 4s(10) &=8\cdot 1554-12\cdot 261+6\cdot 89+4\cdot 14-6\cdot 580\\ &=12432-3132+534+56-3480\\ &=6410, \end{aligned}$$
so
$$s(10)=\frac{6410}{4}=1602.5.$$
This matches the checkpoint built into the implementation.
The C++, Python, and Java implementations all follow the same mathematical decomposition. First they build a Möbius table up to \(n\). Next they evaluate the two large divisor sums for \(S_{ab}^{\ast}(n)\) and \(S_a^{\ast}(n)\), then apply the boundary subtraction that removes the cases with \(a=1\) or \(b=1\).
After that, the implementation processes the four base-10 buckets. Instead of factoring every \(a\) separately and enumerating its divisors, it loops over each divisor \(d\), computes the relevant count and weighted-sum formulas once, and distributes the Möbius-weighted contribution to every multiple of \(d\). This produces per-\(a\) tables for the exceptional set in near-harmonic time. The C++ version can run the four independent bucket passes in parallel; the Python and Java versions preserve the same arithmetic structure and final exact value.
The Möbius sieve is linear, so it costs \(O(n)\) time and \(O(n)\) memory. The dominant work is the divisor-to-multiples sweep used by the four bucket tables, whose total size is controlled by
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor = O(n\log n).$$
Therefore the overall algorithm runs in \(O(n\log n)\) time and uses \(O(n)\) memory. Parallel execution improves wall-clock time in the C++ implementation but does not change the asymptotic bound.
Für jedes geordnete teilerfremde Paar \((a,b)\) mit \(2 \le a,b \le n\) vereinfacht sich der zugehörige Beitrag der Lissajous-Kurve zu einem rationalen Ausdruck, der nur von \(a\), \(b\) und davon abhängt, wie die Faktoren \(2\) und \(5\) der Zahl \(10\) zwischen den beiden Frequenzen aufgeteilt sind. Gesucht ist also
$$s(n)=\sum_{\substack{2 \le a,b \le n\\ \gcd(a,b)=1}} w(a,b)$$
für sehr große \(n\). Deshalb arbeiten die Implementierungen durchgehend mit dem ganzzahligen Zähler \(4s(n)\) und teilen erst am Ende durch \(4\).
Setze
$$C_n=\{(a,b):2 \le a,b \le n,\ \gcd(a,b)=1\},\qquad T(k)=\frac{k(k+1)}{2}.$$
Die gesamte Antwort besteht aus zwei globalen Summen über teilerfremde Paare und einer Zusatzkorrektur auf einer kleineren Ausnahmemenge, die nur durch Teilbarkeit bezüglich \(10\) bestimmt wird.
Ausgangspunkt ist
$$\mathbf 1_{\gcd(a,b)=1}=\sum_{d \mid a,\ d \mid b}\mu(d)=\sum_{d \mid \gcd(a,b)}\mu(d).$$
Dadurch werden Summen über teilerfremde Paare zu Teiler-Summen. Auf dem vollen Quadrat \(1 \le a,b \le n\) erhält man
$$S_{ab}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}ab=\sum_{d=1}^{n}\mu(d)d^2T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)^2,$$
$$S_{a}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}a=\sum_{d=1}^{n}\mu(d)d\,T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\left\lfloor\frac{n}{d}\right\rfloor.$$
Genau diese beiden großen Möbius-Summen werden zuerst berechnet.
Die eigentliche Summe beginnt bei \(2\), nicht bei \(1\). Mit
$$\sum_{m=1}^{n} m = T(n)$$
folgt daher
$$S_{ab}(n)=S_{ab}^{\ast}(n)-2T(n)+1,$$
$$S_{a}(n)=S_{a}^{\ast}(n)-n-T(n)+1.$$
Also gilt
$$S_{ab}(n)=\sum_{(a,b)\in C_n}ab,\qquad S_{a}(n)=\sum_{(a,b)\in C_n}a.$$
Wegen der Symmetrie von \(C_n\) ist derselbe Wert zugleich \(\sum_{(a,b)\in C_n} b\).
Definiere die Klassenabbildung
$$g(m)=\gcd(m,10)\in\{1,2,5,10\}.$$
Die Korrekturschicht hängt nur davon ab, ob eine Frequenz den Faktor \(2\) von \(10\) liefert und die andere den Faktor \(5\). Das wird durch
$$E_n=\{(a,b)\in C_n:g(a)g(b)=10\}$$
erfasst. Die möglichen Zuordnungen der Klassen sind also
$$1 \leftrightarrow 10,\qquad 2 \leftrightarrow 5.$$
Damit reduziert sich der gesamte nicht-generische Teil auf vier komplementäre Klassen nach \(\gcd(\,\cdot\,,10)\).
Für eine Teilmenge \(U \subseteq \{1,\dots,n\}\) definiere für festes \(a\)
$$N_U(a)=\sum_{d \mid a}\mu(d)\,\#\{b \in U:d \mid b\},$$
$$W_U(a)=\sum_{d \mid a}\mu(d)\sum_{\substack{b \in U\\ d \mid b}} b.$$
Das sind Anzahl und gewichtete Summe der \(b\)-Werte aus \(U\), die zu \(a\) teilerfremd sind. Benötigt werden die vier Fälle \(g(b)=10\), \(g(b)=5\), \(g(b)=2\) und \(g(b)=1\), und jeder davon besitzt eine geschlossene Formel über arithmetische Progressionen.
Für \(g(b)=10\) ist \(b\) ein Vielfaches von \(10\). Mit \(L=\operatorname{lcm}(d,10)\) gilt
$$C_{10}(d)=\left\lfloor\frac{n}{L}\right\rfloor,\qquad Q_{10}(d)=L\,T\left(\left\lfloor\frac{n}{L}\right\rfloor\right).$$
Für \(g(b)=5\) ist \(b\) ein ungerades Vielfaches von \(5\). Falls \(2 \mid d\), ist die Anzahl null. Sonst, mit \(L=\operatorname{lcm}(d,5)\), \(t=\left\lfloor n/L \right\rfloor\) und \(k=\left\lceil t/2 \right\rceil\), erhält man
$$C_{5}(d)=k,\qquad Q_{5}(d)=Lk^2,$$
denn \(1+3+\cdots+(2k-1)=k^2\).
Für \(g(b)=2\) ist \(b\) gerade, aber nicht durch \(5\) teilbar. Falls \(5 \mid d\), ist die Anzahl null. Andernfalls, mit \(L=\operatorname{lcm}(d,2)\), \(t=\left\lfloor n/L \right\rfloor\) und \(t_5=\left\lfloor n/(5L) \right\rfloor\), gilt
$$C_{2}(d)=t-t_5,\qquad Q_{2}(d)=L\,T(t)-5L\,T(t_5).$$
Für \(g(b)=1\) ist \(b\) zu \(10\) teilerfremd. Falls \(\gcd(d,10)\ne 1\), ist die Anzahl null. Sonst liefert Inklusion-Exklusion mit \(x=\left\lfloor n/d \right\rfloor\)
$$C_{1}(d)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{5}\right\rfloor+\left\lfloor\frac{x}{10}\right\rfloor,$$
$$Q_{1}(d)=d\left(T(x)-2T\left(\left\lfloor\frac{x}{2}\right\rfloor\right)-5T\left(\left\lfloor\frac{x}{5}\right\rfloor\right)+10T\left(\left\lfloor\frac{x}{10}\right\rfloor\right)\right).$$
Im Fall \(g(a)=10\) muss anschließend noch \(b=1\) entfernt werden, weil die globale Summe erst bei \(2\) beginnt.
Durch Summation der Ausnahme-Anzahlen und -Gewichte über alle \(a\) erhält man
$$N_{10}(n)=|E_n|,\qquad S_{a,10}(n)=\sum_{(a,b)\in E_n} a,\qquad S_{ab,10}(n)=\sum_{(a,b)\in E_n} ab.$$
Danach kombinieren die Implementierungen alles zu
$$4s(n)=8S_{ab}(n)-12S_a(n)+6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n).$$
Äquivalent dazu ist
$$s(n)=2S_{ab}(n)-3S_a(n)+\frac{6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n)}{4}.$$
Man kann dies auch paarweise lesen. Jedes \((a,b)\in C_n\) trägt bei durch
$$w(a,b)= \begin{cases} 2ab-\dfrac{3}{2}(a+b), & g(a)g(b)\ne 10,\\[6pt] \dfrac{2ab-3a-3b+4}{4}, & g(a)g(b)=10. \end{cases}$$
Somit ist
$$s(n)=\sum_{(a,b)\in C_n} w(a,b).$$
Der Viertelfaktor im Ausnahmefall erklärt genau, warum die Programme mit dem ganzzahligen Wert \(4s(n)\) arbeiten.
Für \(n=10\) liefern die Möbius-Summen
$$S_{ab}(10)=1554,\qquad S_a(10)=261.$$
Die Ausnahmemenge \(E_{10}\) enthält \(14\) geordnete Paare, darunter \((2,5)\), \((3,10)\), \((5,8)\), \((10,3)\) und \((10,9)\). Die zugehörigen Summen sind
$$N_{10}(10)=14,\qquad S_{a,10}(10)=89,\qquad S_{ab,10}(10)=580.$$
Damit folgt
$$\begin{aligned} 4s(10) &=8\cdot 1554-12\cdot 261+6\cdot 89+4\cdot 14-6\cdot 580\\ &=12432-3132+534+56-3480\\ &=6410, \end{aligned}$$
also
$$s(10)=\frac{6410}{4}=1602.5.$$
Das stimmt exakt mit dem Kontrollwert der Implementierung überein.
Die Implementierungen in C++, Python und Java folgen alle derselben mathematischen Zerlegung. Zuerst wird eine Möbius-Tabelle bis \(n\) aufgebaut. Danach werden die beiden großen Teiler-Summen für \(S_{ab}^{\ast}(n)\) und \(S_a^{\ast}(n)\) ausgewertet und durch die Randkorrektur auf den Bereich \(2 \le a,b \le n\) eingeschränkt.
Anschließend verarbeitet die Implementierung die vier Klassen modulo \(10\). Statt für jedes \(a\) alle Teiler einzeln zu betrachten, durchläuft sie jeden Teiler \(d\), berechnet die passende geschlossene Zähl- und Summenformel genau einmal und verteilt den Möbius-gewichteten Beitrag auf alle Vielfachen von \(d\). So entstehen Tabellen pro \(a\), ohne die Paare \((a,b)\) explizit aufzuzählen. Die C++-Variante kann die vier unabhängigen Klassen-Durchläufe parallel ausführen; Python und Java behalten dieselbe arithmetische Struktur und denselben exakten Endwert bei.
Das Möbius-Sieb ist linear und benötigt daher \(O(n)\) Zeit und \(O(n)\) Speicher. Der dominante Teil ist die Verteilung von Teiler-Beiträgen auf ihre Vielfachen in den vier Klassen-Tabellen. Deren Gesamtaufwand wird durch
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor = O(n\log n)$$
beschrieben. Insgesamt läuft das Verfahren also in \(O(n\log n)\) Zeit bei \(O(n)\) Speicher. Parallelisierung verbessert in C++ nur die Laufzeit in der Praxis, nicht aber die asymptotische Ordnung.
\(2 \le a,b \le n\) ve \(\gcd(a,b)=1\) olan her sıralı çift için ilgili Lissajous eğrisi katkısı, yalnızca \(a\), \(b\) ve \(10\) sayısının asal çarpanları olan \(2\) ile \(5\)'in bu iki frekans arasında nasıl paylaşıldığına bağlı rasyonel bir ifadeye indirgenir. Hesaplanmak istenen toplam
$$s(n)=\sum_{\substack{2 \le a,b \le n\\ \gcd(a,b)=1}} w(a,b)$$
olduğundan ve \(n\) çok büyük olduğundan, uygulamalar kayan nokta hatasından kaçınmak için tüm işlem boyunca \(4s(n)\) tam sayısını tutar ve en sonda \(4\)'e böler.
Şu gösterimleri kullanalım:
$$C_n=\{(a,b):2 \le a,b \le n,\ \gcd(a,b)=1\},\qquad T(k)=\frac{k(k+1)}{2}.$$
Toplam cevap iki büyük aralarında asal toplamından ve yalnızca \(10\) ile ilgili bölünebilirlik sınıflarına bağlı daha küçük bir düzeltme teriminden oluşur.
Temel kimlik şudur:
$$\mathbf 1_{\gcd(a,b)=1}=\sum_{d \mid a,\ d \mid b}\mu(d)=\sum_{d \mid \gcd(a,b)}\mu(d).$$
Böylece aralarında asal çiftler üzerindeki toplamlar, bölenler üzerinden yazılır. Tam kare \(1 \le a,b \le n\) üzerinde iki ana toplam
$$S_{ab}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}ab=\sum_{d=1}^{n}\mu(d)d^2T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)^2,$$
$$S_{a}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}a=\sum_{d=1}^{n}\mu(d)d\,T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\left\lfloor\frac{n}{d}\right\rfloor$$
şeklini alır. Kodun ilk büyük kısmı tam olarak bu iki Möbius toplamını hesaplar.
Asıl toplam \(1\)'den değil, \(2\)'den başlar. Ayrıca
$$\sum_{m=1}^{n} m = T(n)$$
olduğundan
$$S_{ab}(n)=S_{ab}^{\ast}(n)-2T(n)+1,$$
$$S_{a}(n)=S_{a}^{\ast}(n)-n-T(n)+1$$
elde edilir. Dolayısıyla
$$S_{ab}(n)=\sum_{(a,b)\in C_n}ab,\qquad S_{a}(n)=\sum_{(a,b)\in C_n}a.$$
\(C_n\) koordinat değişimine göre simetrik olduğu için aynı \(S_a(n)\) değeri \(\sum_{(a,b)\in C_n} b\) toplamına da eşittir.
Şu sınıf fonksiyonunu tanımlayalım:
$$g(m)=\gcd(m,10)\in\{1,2,5,10\}.$$
Düzeltme terimi, bir frekansın \(10\)'un içindeki \(2\) çarpanını, diğerinin ise \(5\) çarpanını taşıdığı durumlara bağlıdır. Bu da
$$E_n=\{(a,b)\in C_n:g(a)g(b)=10\}$$
kümesiyle ifade edilir. Olası eşleşmeler tam olarak
$$1 \leftrightarrow 10,\qquad 2 \leftrightarrow 5$$
şeklindedir. Yani özel durumların tamamı, \(\gcd(\,\cdot\,,10)\) ile tanımlanan dört kovadan gelir.
Herhangi bir \(U \subseteq \{1,\dots,n\}\) kümesi için, sabit bir \(a\) değerinde
$$N_U(a)=\sum_{d \mid a}\mu(d)\,\#\{b \in U:d \mid b\},$$
$$W_U(a)=\sum_{d \mid a}\mu(d)\sum_{\substack{b \in U\\ d \mid b}} b$$
tanımlarını yapalım. Bunlar, \(U\) içindeki ve \(a\) ile aralarında asal olan \(b\) değerlerinin sayısını ve ağırlıklı toplamını verir. Gerekli dört alt küme \(g(b)=10\), \(g(b)=5\), \(g(b)=2\) ve \(g(b)=1\) durumlarıdır; her biri aritmetik dizi formülleriyle kapalı biçimde sayılır.
\(g(b)=10\) ise \(b\), \(10\)'un katıdır. \(L=\operatorname{lcm}(d,10)\) için
$$C_{10}(d)=\left\lfloor\frac{n}{L}\right\rfloor,\qquad Q_{10}(d)=L\,T\left(\left\lfloor\frac{n}{L}\right\rfloor\right).$$
\(g(b)=5\) ise \(b\), \(5\)'in tek katıdır. \(2 \mid d\) olduğunda böyle bir sayı yoktur. Aksi halde \(L=\operatorname{lcm}(d,5)\), \(t=\left\lfloor n/L \right\rfloor\) ve \(k=\left\lceil t/2 \right\rceil\) ile
$$C_{5}(d)=k,\qquad Q_{5}(d)=Lk^2$$
olur; çünkü \(1+3+\cdots+(2k-1)=k^2\).
\(g(b)=2\) ise \(b\) çifttir ama \(5\)'e bölünmez. \(5 \mid d\) ise sayı sıfırdır. Aksi halde \(L=\operatorname{lcm}(d,2)\), \(t=\left\lfloor n/L \right\rfloor\), \(t_5=\left\lfloor n/(5L) \right\rfloor\) ile
$$C_{2}(d)=t-t_5,\qquad Q_{2}(d)=L\,T(t)-5L\,T(t_5).$$
\(g(b)=1\) ise \(b\), \(10\) ile aralarında asaldır. \(\gcd(d,10)\ne 1\) olduğunda sayı sıfırdır. Aksi halde \(x=\left\lfloor n/d \right\rfloor\) için \(2\) ve \(5\)'e bölünebilirlik üzerinde dahil et-çıkar uygulanır:
$$C_{1}(d)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{5}\right\rfloor+\left\lfloor\frac{x}{10}\right\rfloor,$$
$$Q_{1}(d)=d\left(T(x)-2T\left(\left\lfloor\frac{x}{2}\right\rfloor\right)-5T\left(\left\lfloor\frac{x}{5}\right\rfloor\right)+10T\left(\left\lfloor\frac{x}{10}\right\rfloor\right)\right).$$
\(g(a)=10\) olduğunda ayrıca \(b=1\) değeri sonradan çıkarılır; çünkü küresel toplam \(2\)'den başlar.
Tüm \(a\) değerleri üzerinden istisna sayıları ve ağırlıkları toplandığında
$$N_{10}(n)=|E_n|,\qquad S_{a,10}(n)=\sum_{(a,b)\in E_n} a,\qquad S_{ab,10}(n)=\sum_{(a,b)\in E_n} ab$$
elde edilir. Sonra uygulamalar şu birleşimi yapar:
$$4s(n)=8S_{ab}(n)-12S_a(n)+6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n).$$
Başka bir deyişle
$$s(n)=2S_{ab}(n)-3S_a(n)+\frac{6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n)}{4}.$$
Bunu çift bazında da okuyabiliriz. Her \((a,b)\in C_n\) için katkı
$$w(a,b)= \begin{cases} 2ab-\dfrac{3}{2}(a+b), & g(a)g(b)\ne 10,\\[6pt] \dfrac{2ab-3a-3b+4}{4}, & g(a)g(b)=10 \end{cases}$$
olur. Dolayısıyla
$$s(n)=\sum_{(a,b)\in C_n} w(a,b).$$
Özel durumda ortaya çıkan \(\tfrac14\) çarpanı, programların neden baştan sona \(4s(n)\) tam sayısını taşıdığını açıklar.
\(n=10\) için Möbius toplamları
$$S_{ab}(10)=1554,\qquad S_a(10)=261$$
değerlerini verir. İstisna kümesi \(E_{10}\), \((2,5)\), \((3,10)\), \((5,8)\), \((10,3)\) ve \((10,9)\) gibi toplam \(14\) sıralı çiftten oluşur. Bu kümenin toplamları da
$$N_{10}(10)=14,\qquad S_{a,10}(10)=89,\qquad S_{ab,10}(10)=580$$
şeklindedir. Böylece
$$\begin{aligned} 4s(10) &=8\cdot 1554-12\cdot 261+6\cdot 89+4\cdot 14-6\cdot 580\\ &=12432-3132+534+56-3480\\ &=6410, \end{aligned}$$
ve dolayısıyla
$$s(10)=\frac{6410}{4}=1602.5$$
elde edilir. Bu, uygulamanın kontrol noktasıyla tam uyumludur.
C++, Python ve Java uygulamalarının tümü aynı matematiksel ayrışmayı kullanır. Önce \(n\)'e kadar bir Möbius tablosu üretilir. Sonra \(S_{ab}^{\ast}(n)\) ve \(S_a^{\ast}(n)\) için iki büyük bölen toplamı hesaplanır ve sınır düzeltmesiyle \(a=1\) ya da \(b=1\) durumları çıkarılır.
Bundan sonra uygulama, taban \(10\)'a göre dört kovayı işler. Her \(a\) için bölenleri tekrar tekrar açmak yerine her bölen \(d\) yalnızca bir kez ele alınır, kapalı formdaki sayım ve toplam formülü hesaplanır, sonra bu Möbius ağırlıklı katkı \(d\)'nin tüm katlarına dağıtılır. Böylece istisna kümesi için \(a\)-bazlı tablolar elde edilir ve \((a,b)\) çiftleri açıkça gezilmez. C++ sürümü dört bağımsız kova hesabını paralel çalıştırabilir; Python ve Java ise aynı cebirsel yapıyı ve aynı kesin sonucu korur.
Möbius eleği lineerdir; dolayısıyla zaman maliyeti \(O(n)\), bellek maliyeti \(O(n)\)'dir. Baskın kısım, dört kova tablosunda bölen katkılarının katlara dağıtılmasıdır. Bunun toplam büyüklüğü
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor = O(n\log n)$$
ile kontrol edilir. Sonuç olarak tüm algoritma \(O(n\log n)\) zamanda ve \(O(n)\) bellekte çalışır. C++ tarafındaki paralellik yalnızca pratik çalışma süresini azaltır; asimptotik sınıfı değiştirmez.
Para cada par ordenado coprimo \((a,b)\) con \(2 \le a,b \le n\), la contribucion asociada a la curva de Lissajous se reduce a una expresion racional que depende solo de \(a\), de \(b\) y de como se reparten entre ambas frecuencias los factores \(2\) y \(5\) de \(10\). Por tanto, el objetivo es calcular
$$s(n)=\sum_{\substack{2 \le a,b \le n\\ \gcd(a,b)=1}} w(a,b)$$
de manera exacta incluso cuando \(n\) es muy grande. Las implementaciones evitan errores de punto flotante manteniendo el numerador entero \(4s(n)\) y dividiendo por \(4\) solo al final.
Escribamos
$$C_n=\{(a,b):2 \le a,b \le n,\ \gcd(a,b)=1\},\qquad T(k)=\frac{k(k+1)}{2}.$$
La respuesta completa se construye a partir de dos sumas globales sobre pares coprimos y de una correccion adicional sobre un conjunto excepcional mas pequeno, determinado unicamente por la divisibilidad respecto de \(10\).
El punto de partida es
$$\mathbf 1_{\gcd(a,b)=1}=\sum_{d \mid a,\ d \mid b}\mu(d)=\sum_{d \mid \gcd(a,b)}\mu(d).$$
Esto transforma las sumas sobre pares coprimos en sumas sobre divisores. En el cuadrado completo \(1 \le a,b \le n\), las dos agregaciones basicas son
$$S_{ab}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}ab=\sum_{d=1}^{n}\mu(d)d^2T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)^2,$$
$$S_{a}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}a=\sum_{d=1}^{n}\mu(d)d\,T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\left\lfloor\frac{n}{d}\right\rfloor.$$
Esas son exactamente las dos grandes sumas de Mobius que se calculan primero.
La suma buscada empieza en \(2\), no en \(1\). Como
$$\sum_{m=1}^{n} m = T(n),$$
se obtiene
$$S_{ab}(n)=S_{ab}^{\ast}(n)-2T(n)+1,$$
$$S_{a}(n)=S_{a}^{\ast}(n)-n-T(n)+1.$$
Por tanto,
$$S_{ab}(n)=\sum_{(a,b)\in C_n}ab,\qquad S_{a}(n)=\sum_{(a,b)\in C_n}a.$$
La simetria de \(C_n\) implica que el mismo valor tambien es \(\sum_{(a,b)\in C_n} b\).
Definimos la funcion de cubeta
$$g(m)=\gcd(m,10)\in\{1,2,5,10\}.$$
La capa de correccion solo depende de si una frecuencia aporta el factor \(2\) de \(10\) y la otra aporta el factor \(5\). Eso se codifica mediante
$$E_n=\{(a,b)\in C_n:g(a)g(b)=10\}.$$
Las correspondencias posibles entre cubetas son
$$1 \leftrightarrow 10,\qquad 2 \leftrightarrow 5.$$
Asi, toda la parte no generica del problema queda reducida a cuatro clases complementarias definidas por \(\gcd(\,\cdot\,,10)\).
Para cualquier subconjunto \(U \subseteq \{1,\dots,n\}\), definimos para un \(a\) fijo
$$N_U(a)=\sum_{d \mid a}\mu(d)\,\#\{b \in U:d \mid b\},$$
$$W_U(a)=\sum_{d \mid a}\mu(d)\sum_{\substack{b \in U\\ d \mid b}} b.$$
Estas expresiones dan el numero y la suma ponderada de los valores \(b\) en \(U\) que son coprimos con \(a\). Los cuatro subconjuntos necesarios son \(g(b)=10\), \(g(b)=5\), \(g(b)=2\) y \(g(b)=1\), y cada uno admite una formula cerrada de progresiones aritmeticas.
Si \(g(b)=10\), entonces \(b\) es multiplo de \(10\). Con \(L=\operatorname{lcm}(d,10)\),
$$C_{10}(d)=\left\lfloor\frac{n}{L}\right\rfloor,\qquad Q_{10}(d)=L\,T\left(\left\lfloor\frac{n}{L}\right\rfloor\right).$$
Si \(g(b)=5\), entonces \(b\) es un multiplo impar de \(5\). Cuando \(2 \mid d\), no hay ninguno. En caso contrario, con \(L=\operatorname{lcm}(d,5)\), \(t=\left\lfloor n/L \right\rfloor\) y \(k=\left\lceil t/2 \right\rceil\),
$$C_{5}(d)=k,\qquad Q_{5}(d)=Lk^2,$$
porque \(1+3+\cdots+(2k-1)=k^2\).
Si \(g(b)=2\), entonces \(b\) es par pero no multiplo de \(5\). Cuando \(5 \mid d\), el conteo es cero. En caso contrario, con \(L=\operatorname{lcm}(d,2)\), \(t=\left\lfloor n/L \right\rfloor\) y \(t_5=\left\lfloor n/(5L) \right\rfloor\),
$$C_{2}(d)=t-t_5,\qquad Q_{2}(d)=L\,T(t)-5L\,T(t_5).$$
Si \(g(b)=1\), entonces \(b\) es coprimo con \(10\). Cuando \(\gcd(d,10)\ne 1\), el conteo es cero. En caso contrario, con \(x=\left\lfloor n/d \right\rfloor\), la inclusion-exclusion sobre la divisibilidad por \(2\) y \(5\) produce
$$C_{1}(d)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{5}\right\rfloor+\left\lfloor\frac{x}{10}\right\rfloor,$$
$$Q_{1}(d)=d\left(T(x)-2T\left(\left\lfloor\frac{x}{2}\right\rfloor\right)-5T\left(\left\lfloor\frac{x}{5}\right\rfloor\right)+10T\left(\left\lfloor\frac{x}{10}\right\rfloor\right)\right).$$
Cuando \(g(a)=10\), despues hay que restar el valor \(b=1\), porque la suma global empieza en \(2\).
Al sumar los conteos y pesos excepcionales sobre todos los \(a\), se obtiene
$$N_{10}(n)=|E_n|,\qquad S_{a,10}(n)=\sum_{(a,b)\in E_n} a,\qquad S_{ab,10}(n)=\sum_{(a,b)\in E_n} ab.$$
Entonces las implementaciones combinan todo mediante
$$4s(n)=8S_{ab}(n)-12S_a(n)+6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n).$$
De forma equivalente,
$$s(n)=2S_{ab}(n)-3S_a(n)+\frac{6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n)}{4}.$$
Tambien puede leerse pareja por pareja. Cada \((a,b)\in C_n\) aporta
$$w(a,b)= \begin{cases} 2ab-\dfrac{3}{2}(a+b), & g(a)g(b)\ne 10,\\[6pt] \dfrac{2ab-3a-3b+4}{4}, & g(a)g(b)=10. \end{cases}$$
Por ello
$$s(n)=\sum_{(a,b)\in C_n} w(a,b).$$
El factor \(\tfrac14\) del caso excepcional explica por que el programa transporta el numerador entero \(4s(n)\) durante todo el calculo.
Para \(n=10\), las sumas de Mobius dan
$$S_{ab}(10)=1554,\qquad S_a(10)=261.$$
El conjunto excepcional \(E_{10}\) contiene \(14\) pares ordenados, entre ellos \((2,5)\), \((3,10)\), \((5,8)\), \((10,3)\) y \((10,9)\). Sus totales son
$$N_{10}(10)=14,\qquad S_{a,10}(10)=89,\qquad S_{ab,10}(10)=580.$$
Por tanto,
$$\begin{aligned} 4s(10) &=8\cdot 1554-12\cdot 261+6\cdot 89+4\cdot 14-6\cdot 580\\ &=12432-3132+534+56-3480\\ &=6410, \end{aligned}$$
y asi
$$s(10)=\frac{6410}{4}=1602.5.$$
Este es exactamente el valor de comprobacion usado por la implementacion.
Las implementaciones en C++, Python y Java siguen la misma descomposicion matematica. Primero construyen una tabla de Mobius hasta \(n\). Luego evalúan las dos grandes sumas de divisores para \(S_{ab}^{\ast}(n)\) y \(S_a^{\ast}(n)\), y aplican despues la correccion de borde que elimina los casos con \(a=1\) o \(b=1\).
A continuacion, la implementacion procesa las cuatro cubetas de base \(10\). En lugar de factorizar cada \(a\) por separado y recorrer sus divisores, recorre cada divisor \(d\), calcula una sola vez la formula cerrada de conteo y de suma ponderada, y distribuye esa contribucion ponderada por \(\mu(d)\) a todos los multiplos de \(d\). Asi se generan tablas por \(a\) para el conjunto excepcional sin enumerar los pares \((a,b)\). La version en C++ puede ejecutar en paralelo las cuatro pasadas independientes; las versiones en Python y Java conservan la misma estructura aritmetica y el mismo resultado exacto.
La criba de Mobius es lineal, de modo que cuesta \(O(n)\) tiempo y \(O(n)\) memoria. El trabajo dominante es el barrido de divisor a multiplos usado por las cuatro tablas de cubetas. Su tamaño total esta controlado por
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor = O(n\log n).$$
En consecuencia, el algoritmo completo funciona en \(O(n\log n)\) tiempo y usa \(O(n)\) memoria. La paralelizacion en C++ mejora el tiempo real, pero no modifica el orden asintotico.
对于每一个满足 \(2 \le a,b \le n\) 且 \(\gcd(a,b)=1\) 的有序频率对 \((a,b)\)，对应的 Lissajous 曲线贡献都可以化成一个有理式；它只依赖于 \(a\)、\(b\)，以及 \(10\) 的两个质因子 \(2\) 和 \(5\) 如何分布在这两个频率上。于是要求的总量是
$$s(n)=\sum_{\substack{2 \le a,b \le n\\ \gcd(a,b)=1}} w(a,b).$$
由于 \(n\) 很大，程序不能直接枚举所有频率对，所以实现始终保存整数分子 \(4s(n)\)，最后再除以 \(4\)，从而避免浮点误差。
记
$$C_n=\{(a,b):2 \le a,b \le n,\ \gcd(a,b)=1\},\qquad T(k)=\frac{k(k+1)}{2}.$$
整个答案由两类全局互素求和组成，再加上一层只和 \(10\) 的整除结构有关的特殊修正。
核心恒等式是
$$\mathbf 1_{\gcd(a,b)=1}=\sum_{d \mid a,\ d \mid b}\mu(d)=\sum_{d \mid \gcd(a,b)}\mu(d).$$
它把“互素”条件变成了对公共因子的求和。先在完整方阵 \(1 \le a,b \le n\) 上考虑，两类基础总和为
$$S_{ab}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}ab=\sum_{d=1}^{n}\mu(d)d^2T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)^2,$$
$$S_{a}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}a=\sum_{d=1}^{n}\mu(d)d\,T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\left\lfloor\frac{n}{d}\right\rfloor.$$
这正是实现首先计算的两项大规模 Möbius 和。
题目真正需要的是从 \(2\) 开始的频率，而不是从 \(1\) 开始。因此必须减去边界贡献。由于
$$\sum_{m=1}^{n} m = T(n),$$
于是有
$$S_{ab}(n)=S_{ab}^{\ast}(n)-2T(n)+1,$$
$$S_{a}(n)=S_{a}^{\ast}(n)-n-T(n)+1.$$
也就是说，
$$S_{ab}(n)=\sum_{(a,b)\in C_n}ab,\qquad S_{a}(n)=\sum_{(a,b)\in C_n}a.$$
因为集合 \(C_n\) 在交换两个坐标时保持不变，所以同一个 \(S_a(n)\) 也等于 \(\sum_{(a,b)\in C_n} b\)。
定义桶函数
$$g(m)=\gcd(m,10)\in\{1,2,5,10\}.$$
修正项只取决于这样一种情况：一个频率提供了 \(10\) 中的因子 \(2\)，另一个频率提供了因子 \(5\)。这可写成
$$E_n=\{(a,b)\in C_n:g(a)g(b)=10\}.$$
于是可能的桶匹配只有
$$1 \leftrightarrow 10,\qquad 2 \leftrightarrow 5.$$
所以，所有“非通用”的部分都可以压缩成按 \(\gcd(\,\cdot\,,10)\) 划分的四个互补类别。
对任意子集 \(U \subseteq \{1,\dots,n\}\)，固定 \(a\) 后定义
$$N_U(a)=\sum_{d \mid a}\mu(d)\,\#\{b \in U:d \mid b\},$$
$$W_U(a)=\sum_{d \mid a}\mu(d)\sum_{\substack{b \in U\\ d \mid b}} b.$$
它们分别表示：在集合 \(U\) 中，与 \(a\) 互素的 \(b\) 的个数，以及这些 \(b\) 的加权和。这里需要四个子集，对应 \(g(b)=10\)、\(g(b)=5\)、\(g(b)=2\)、\(g(b)=1\)，而每一种都能化成封闭的等差数列公式。
若 \(g(b)=10\)，则 \(b\) 必须是 \(10\) 的倍数。令 \(L=\operatorname{lcm}(d,10)\)，则
$$C_{10}(d)=\left\lfloor\frac{n}{L}\right\rfloor,\qquad Q_{10}(d)=L\,T\left(\left\lfloor\frac{n}{L}\right\rfloor\right).$$
若 \(g(b)=5\)，则 \(b\) 是 \(5\) 的奇数倍。如果 \(2 \mid d\)，这种数不存在。否则令 \(L=\operatorname{lcm}(d,5)\)、\(t=\left\lfloor n/L \right\rfloor\)、\(k=\left\lceil t/2 \right\rceil\)，有
$$C_{5}(d)=k,\qquad Q_{5}(d)=Lk^2,$$
因为 \(1+3+\cdots+(2k-1)=k^2\)。
若 \(g(b)=2\)，则 \(b\) 为偶数但不被 \(5\) 整除。若 \(5 \mid d\)，计数为零。否则令 \(L=\operatorname{lcm}(d,2)\)、\(t=\left\lfloor n/L \right\rfloor\)、\(t_5=\left\lfloor n/(5L) \right\rfloor\)，则
$$C_{2}(d)=t-t_5,\qquad Q_{2}(d)=L\,T(t)-5L\,T(t_5).$$
若 \(g(b)=1\)，则 \(b\) 与 \(10\) 互素。若 \(\gcd(d,10)\ne 1\)，计数仍为零。否则令 \(x=\left\lfloor n/d \right\rfloor\)，对能否被 \(2\) 和 \(5\) 整除使用容斥原理，可得
$$C_{1}(d)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{5}\right\rfloor+\left\lfloor\frac{x}{10}\right\rfloor,$$
$$Q_{1}(d)=d\left(T(x)-2T\left(\left\lfloor\frac{x}{2}\right\rfloor\right)-5T\left(\left\lfloor\frac{x}{5}\right\rfloor\right)+10T\left(\left\lfloor\frac{x}{10}\right\rfloor\right)\right).$$
当 \(g(a)=10\) 时，还要额外减去 \(b=1\) 这一项，因为总和的起点是 \(2\)。
把所有 \(a\) 上的特殊计数与加权和汇总后，得到
$$N_{10}(n)=|E_n|,\qquad S_{a,10}(n)=\sum_{(a,b)\in E_n} a,\qquad S_{ab,10}(n)=\sum_{(a,b)\in E_n} ab.$$
实现最终按下式组合：
$$4s(n)=8S_{ab}(n)-12S_a(n)+6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n).$$
也就是
$$s(n)=2S_{ab}(n)-3S_a(n)+\frac{6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n)}{4}.$$
这还可以改写成逐对求和。每个 \((a,b)\in C_n\) 的贡献都是
$$w(a,b)= \begin{cases} 2ab-\dfrac{3}{2}(a+b), & g(a)g(b)\ne 10,\\[6pt] \dfrac{2ab-3a-3b+4}{4}, & g(a)g(b)=10. \end{cases}$$
因此
$$s(n)=\sum_{(a,b)\in C_n} w(a,b).$$
特殊情形里出现的 \(\tfrac14\) 正是程序始终保存整数 \(4s(n)\) 的原因。
当 \(n=10\) 时，Möbius 求和给出
$$S_{ab}(10)=1554,\qquad S_a(10)=261.$$
特殊集合 \(E_{10}\) 含有 \(14\) 个有序对，其中包括 \((2,5)\)、\((3,10)\)、\((5,8)\)、\((10,3)\)、\((10,9)\)。相应的总量为
$$N_{10}(10)=14,\qquad S_{a,10}(10)=89,\qquad S_{ab,10}(10)=580.$$
代入可得
$$\begin{aligned} 4s(10) &=8\cdot 1554-12\cdot 261+6\cdot 89+4\cdot 14-6\cdot 580\\ &=12432-3132+534+56-3480\\ &=6410, \end{aligned}$$
所以
$$s(10)=\frac{6410}{4}=1602.5.$$
这与实现中的检查值完全一致。
C++、Python 和 Java 三个实现都遵循同一个数学分解。第一步是建立到 \(n\) 为止的 Möbius 表。第二步计算两项大的除数和 \(S_{ab}^{\ast}(n)\) 与 \(S_a^{\ast}(n)\)，然后做边界修正，去掉 \(a=1\) 或 \(b=1\) 的情形。
接着，程序处理与十进制有关的四个桶。它并不为每个 \(a\) 单独分解因子，而是按除数 \(d\) 进行扫描：对每个 \(d\) 只计算一次封闭的计数与加权求和公式，再把带有 \(\mu(d)\) 权重的贡献分发给所有 \(d\) 的倍数。这样就能在不显式枚举 \((a,b)\) 的前提下，为每个 \(a\) 生成特殊修正所需的表。C++ 版本在输入足够大时可以把四个独立的桶并行计算；Python 与 Java 版本则保持相同的算术结构与完全一致的最终值。
Möbius 筛本身是线性的，因此耗时 \(O(n)\)，内存 \(O(n)\)。真正占主导的是四个桶所使用的“除数到倍数”扫描，其总规模受
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor = O(n\log n)$$
控制。所以整体算法的时间复杂度为 \(O(n\log n)\)，空间复杂度为 \(O(n)\)。C++ 中的并行化只能改善实际运行时间，不改变渐近复杂度。
Для каждой упорядоченной взаимно простой пары \((a,b)\) при \(2 \le a,b \le n\) вклад соответствующей кривой Лиссажу сводится к рациональному выражению, зависящему только от \(a\), \(b\) и от того, как множители \(2\) и \(5\) числа \(10\) распределены между двумя частотами. Поэтому требуется вычислить
$$s(n)=\sum_{\substack{2 \le a,b \le n\\ \gcd(a,b)=1}} w(a,b)$$
точно даже для очень больших \(n\). Чтобы не накапливать ошибки плавающей точки, реализации всю дорогу хранят целочисленный числитель \(4s(n)\), а деление на \(4\) выполняют только в самом конце.
Обозначим
$$C_n=\{(a,b):2 \le a,b \le n,\ \gcd(a,b)=1\},\qquad T(k)=\frac{k(k+1)}{2}.$$
Полный ответ состоит из двух глобальных сумм по взаимно простым парам и одной дополнительной поправки на меньшем исключительном множестве, которое определяется только делимостью по отношению к \(10\).
Базовое тождество имеет вид
$$\mathbf 1_{\gcd(a,b)=1}=\sum_{d \mid a,\ d \mid b}\mu(d)=\sum_{d \mid \gcd(a,b)}\mu(d).$$
Оно заменяет условие взаимной простоты суммированием по общим делителям. На полном квадрате \(1 \le a,b \le n\) получаем две основные суммы
$$S_{ab}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}ab=\sum_{d=1}^{n}\mu(d)d^2T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)^2,$$
$$S_{a}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}a=\sum_{d=1}^{n}\mu(d)d\,T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\left\lfloor\frac{n}{d}\right\rfloor.$$
Именно эти две большие суммы с функцией Мёбиуса вычисляются в начале.
Искомая сумма начинается с \(2\), а не с \(1\). Поскольку
$$\sum_{m=1}^{n} m = T(n),$$
получаем
$$S_{ab}(n)=S_{ab}^{\ast}(n)-2T(n)+1,$$
$$S_{a}(n)=S_{a}^{\ast}(n)-n-T(n)+1.$$
Следовательно,
$$S_{ab}(n)=\sum_{(a,b)\in C_n}ab,\qquad S_{a}(n)=\sum_{(a,b)\in C_n}a.$$
Из симметрии множества \(C_n\) следует, что то же самое \(S_a(n)\) равно и \(\sum_{(a,b)\in C_n} b\).
Введем отображение по корзинам
$$g(m)=\gcd(m,10)\in\{1,2,5,10\}.$$
Поправка зависит только от того, дает ли одна частота множитель \(2\) числа \(10\), а другая множитель \(5\). Это условие записывается так:
$$E_n=\{(a,b)\in C_n:g(a)g(b)=10\}.$$
Возможные парные соответствия корзин таковы:
$$1 \leftrightarrow 10,\qquad 2 \leftrightarrow 5.$$
Значит, вся нестандартная часть задачи сводится к четырем дополнительным классам, определяемым значением \(\gcd(\,\cdot\,,10)\).
Для любого подмножества \(U \subseteq \{1,\dots,n\}\) и фиксированного \(a\) зададим
$$N_U(a)=\sum_{d \mid a}\mu(d)\,\#\{b \in U:d \mid b\},$$
$$W_U(a)=\sum_{d \mid a}\mu(d)\sum_{\substack{b \in U\\ d \mid b}} b.$$
Это количество и взвешенная сумма тех значений \(b\) из множества \(U\), которые взаимно просты с \(a\). Нужны четыре случая: \(g(b)=10\), \(g(b)=5\), \(g(b)=2\) и \(g(b)=1\), и для каждого из них существуют замкнутые формулы через арифметические прогрессии.
Если \(g(b)=10\), то \(b\) кратно \(10\). При \(L=\operatorname{lcm}(d,10)\) имеем
$$C_{10}(d)=\left\lfloor\frac{n}{L}\right\rfloor,\qquad Q_{10}(d)=L\,T\left(\left\lfloor\frac{n}{L}\right\rfloor\right).$$
Если \(g(b)=5\), то \(b\) является нечетным кратным \(5\). При \(2 \mid d\) таких чисел нет. Иначе, если \(L=\operatorname{lcm}(d,5)\), \(t=\left\lfloor n/L \right\rfloor\), \(k=\left\lceil t/2 \right\rceil\), то
$$C_{5}(d)=k,\qquad Q_{5}(d)=Lk^2,$$
поскольку \(1+3+\cdots+(2k-1)=k^2\).
Если \(g(b)=2\), то \(b\) четно, но не делится на \(5\). При \(5 \mid d\) счет равен нулю. Иначе, если \(L=\operatorname{lcm}(d,2)\), \(t=\left\lfloor n/L \right\rfloor\), \(t_5=\left\lfloor n/(5L) \right\rfloor\), то
$$C_{2}(d)=t-t_5,\qquad Q_{2}(d)=L\,T(t)-5L\,T(t_5).$$
Если \(g(b)=1\), то \(b\) взаимно просто с \(10\). При \(\gcd(d,10)\ne 1\) ответ снова равен нулю. Иначе, положив \(x=\left\lfloor n/d \right\rfloor\), по принципу включений-исключений для делимости на \(2\) и \(5\) получаем
$$C_{1}(d)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{5}\right\rfloor+\left\lfloor\frac{x}{10}\right\rfloor,$$
$$Q_{1}(d)=d\left(T(x)-2T\left(\left\lfloor\frac{x}{2}\right\rfloor\right)-5T\left(\left\lfloor\frac{x}{5}\right\rfloor\right)+10T\left(\left\lfloor\frac{x}{10}\right\rfloor\right)\right).$$
В случае \(g(a)=10\) потом нужно еще вычесть значение \(b=1\), потому что глобальная сумма начинается с \(2\).
Просуммировав исключительные количества и веса по всем \(a\), получаем
$$N_{10}(n)=|E_n|,\qquad S_{a,10}(n)=\sum_{(a,b)\in E_n} a,\qquad S_{ab,10}(n)=\sum_{(a,b)\in E_n} ab.$$
После этого реализации объединяют все части по формуле
$$4s(n)=8S_{ab}(n)-12S_a(n)+6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n).$$
То же самое можно записать как
$$s(n)=2S_{ab}(n)-3S_a(n)+\frac{6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n)}{4}.$$
Есть и покомпонентная интерпретация. Каждый элемент \((a,b)\in C_n\) вносит
$$w(a,b)= \begin{cases} 2ab-\dfrac{3}{2}(a+b), & g(a)g(b)\ne 10,\\[6pt] \dfrac{2ab-3a-3b+4}{4}, & g(a)g(b)=10. \end{cases}$$
Следовательно,
$$s(n)=\sum_{(a,b)\in C_n} w(a,b).$$
Появление множителя \(\tfrac14\) в исключительном случае и объясняет, почему программа на всем протяжении хранит целое число \(4s(n)\).
При \(n=10\) суммы с функцией Мёбиуса дают
$$S_{ab}(10)=1554,\qquad S_a(10)=261.$$
Исключительное множество \(E_{10}\) содержит \(14\) упорядоченных пар, среди них \((2,5)\), \((3,10)\), \((5,8)\), \((10,3)\), \((10,9)\). Для него имеем
$$N_{10}(10)=14,\qquad S_{a,10}(10)=89,\qquad S_{ab,10}(10)=580.$$
Тогда
$$\begin{aligned} 4s(10) &=8\cdot 1554-12\cdot 261+6\cdot 89+4\cdot 14-6\cdot 580\\ &=12432-3132+534+56-3480\\ &=6410, \end{aligned}$$
а значит
$$s(10)=\frac{6410}{4}=1602.5.$$
Это в точности совпадает с контрольным значением, используемым в реализации.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала строится таблица значений функции Мёбиуса до \(n\). Затем вычисляются две большие суммы по делителям для \(S_{ab}^{\ast}(n)\) и \(S_a^{\ast}(n)\), после чего применяется граничная коррекция, исключающая случаи \(a=1\) или \(b=1\).
После этого реализация обрабатывает четыре корзины, связанные с основанием \(10\). Вместо того чтобы отдельно разбирать каждый \(a\) и его делители, она проходит по каждому делителю \(d\), один раз вычисляет замкнутую формулу для количества и взвешенной суммы, а затем распределяет вклад с коэффициентом \(\mu(d)\) по всем кратным \(d\). Так получаются таблицы по \(a\) для исключительного множества без явного перебора пар \((a,b)\). Версия на C++ может запускать четыре независимых прохода параллельно; версии на Python и Java сохраняют ту же арифметическую структуру и тот же точный результат.
Решето Мёбиуса линейно, поэтому требует \(O(n)\) времени и \(O(n)\) памяти. Основная стоимость приходится на проходы от делителя к его кратным в четырех таблицах корзин. Их суммарный размер контролируется оценкой
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor = O(n\log n).$$
Следовательно, весь алгоритм работает за \(O(n\log n)\) времени и использует \(O(n)\) памяти. Параллелизм в реализации на C++ улучшает реальное время выполнения, но не меняет асимптотический порядок.
لكل زوج مرتب \((a,b)\) يحقق \(2 \le a,b \le n\) و\(\gcd(a,b)=1\)، يمكن اختزال مساهمة منحنى Lissajous الموافق إلى تعبير نسبي يعتمد فقط على \(a\) و\(b\) وعلى كيفية توزع العاملين \(2\) و\(5\) الخاصين بالعدد \(10\) بين الترددين. لذلك فالمطلوب هو حساب
$$s(n)=\sum_{\substack{2 \le a,b \le n\\ \gcd(a,b)=1}} w(a,b)$$
بدقة حتى عندما تكون \(n\) كبيرة جدا. ولهذا السبب تحتفظ التطبيقات دائما بالبسط الصحيح \(4s(n)\) ولا تجري القسمة على \(4\) إلا في النهاية.
لنكتب
$$C_n=\{(a,b):2 \le a,b \le n,\ \gcd(a,b)=1\},\qquad T(k)=\frac{k(k+1)}{2}.$$
الإجابة الكاملة تتكون من مجموعين عالميين على الأزواج المتباينة القاسم، إضافة إلى طبقة تصحيح أصغر حجما تحددها فقط علاقة الأعداد بالعدد \(10\).
الهوية الأساسية هي
$$\mathbf 1_{\gcd(a,b)=1}=\sum_{d \mid a,\ d \mid b}\mu(d)=\sum_{d \mid \gcd(a,b)}\mu(d).$$
وهذه الهوية تحول شرط التباين إلى جمع على القواسم المشتركة. على المربع الكامل \(1 \le a,b \le n\) نحصل على المجموعين الأساسيين
$$S_{ab}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}ab=\sum_{d=1}^{n}\mu(d)d^2T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)^2,$$
$$S_{a}^{\ast}(n)=\sum_{\substack{1 \le a,b \le n\\ \gcd(a,b)=1}}a=\sum_{d=1}^{n}\mu(d)d\,T\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\left\lfloor\frac{n}{d}\right\rfloor.$$
وهذان هما تماما مجموعا Mobius الكبيران اللذان تحسبهما التطبيقات أولا.
المجموع المطلوب يبدأ من \(2\) لا من \(1\). وبما أن
$$\sum_{m=1}^{n} m = T(n),$$
فإننا نحصل على
$$S_{ab}(n)=S_{ab}^{\ast}(n)-2T(n)+1,$$
$$S_{a}(n)=S_{a}^{\ast}(n)-n-T(n)+1.$$
ومن ثم
$$S_{ab}(n)=\sum_{(a,b)\in C_n}ab,\qquad S_{a}(n)=\sum_{(a,b)\in C_n}a.$$
وبسبب تناظر \(C_n\) عند تبديل الإحداثيين، فإن القيمة نفسها تساوي أيضا \(\sum_{(a,b)\in C_n} b\).
نعرف دالة التصنيف
$$g(m)=\gcd(m,10)\in\{1,2,5,10\}.$$
طبقة التصحيح تعتمد فقط على ما إذا كان أحد الترددين يزوّد العامل \(2\) من \(10\) والآخر يزوّد العامل \(5\). ويكتب هذا الشرط على الصورة
$$E_n=\{(a,b)\in C_n:g(a)g(b)=10\}.$$
وعليه فإن أزواج السلال الممكنة هي
$$1 \leftrightarrow 10,\qquad 2 \leftrightarrow 5.$$
إذن الجزء غير العام كله ينحصر في أربع فئات مكملة بعضها لبعض حسب قيمة \(\gcd(\,\cdot\,,10)\).
لأي مجموعة جزئية \(U \subseteq \{1,\dots,n\}\)، ومع تثبيت \(a\)، نعرف
$$N_U(a)=\sum_{d \mid a}\mu(d)\,\#\{b \in U:d \mid b\},$$
$$W_U(a)=\sum_{d \mid a}\mu(d)\sum_{\substack{b \in U\\ d \mid b}} b.$$
وهذا يعطينا عدد قيم \(b\) الموجودة في \(U\) والتي تكون متباينة القاسم مع \(a\)، وكذلك مجموعها الموزون. الفئات الأربع المطلوبة هي \(g(b)=10\) و\(g(b)=5\) و\(g(b)=2\) و\(g(b)=1\)، ولكل واحدة منها صيغة مغلقة تعتمد على متتاليات حسابية.
إذا كان \(g(b)=10\)، فهذا يعني أن \(b\) مضاعف للعدد \(10\). وإذا وضعنا \(L=\operatorname{lcm}(d,10)\) فإن
$$C_{10}(d)=\left\lfloor\frac{n}{L}\right\rfloor,\qquad Q_{10}(d)=L\,T\left(\left\lfloor\frac{n}{L}\right\rfloor\right).$$
إذا كان \(g(b)=5\)، فـ \(b\) مضاعف فردي للعدد \(5\). وعندما \(2 \mid d\) لا يوجد أي عنصر من هذا النوع. وإلا، إذا كان \(L=\operatorname{lcm}(d,5)\) و\(t=\left\lfloor n/L \right\rfloor\) و\(k=\left\lceil t/2 \right\rceil\)، نحصل على
$$C_{5}(d)=k,\qquad Q_{5}(d)=Lk^2,$$
لأن \(1+3+\cdots+(2k-1)=k^2\).
إذا كان \(g(b)=2\)، فـ \(b\) زوجي ولكنه غير قابل للقسمة على \(5\). وعندما \(5 \mid d\) يكون العدد صفرا. وإلا، إذا أخذنا \(L=\operatorname{lcm}(d,2)\) و\(t=\left\lfloor n/L \right\rfloor\) و\(t_5=\left\lfloor n/(5L) \right\rfloor\)، فإن
$$C_{2}(d)=t-t_5,\qquad Q_{2}(d)=L\,T(t)-5L\,T(t_5).$$
إذا كان \(g(b)=1\)، فـ \(b\) أولي نسبيا مع \(10\). وعندما \(\gcd(d,10)\ne 1\) يكون العدد صفرا أيضا. وإلا، مع \(x=\left\lfloor n/d \right\rfloor\)، يعطينا مبدأ الشمول والاستبعاد بالنسبة إلى القسمة على \(2\) و\(5\)
$$C_{1}(d)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{5}\right\rfloor+\left\lfloor\frac{x}{10}\right\rfloor,$$
$$Q_{1}(d)=d\left(T(x)-2T\left(\left\lfloor\frac{x}{2}\right\rfloor\right)-5T\left(\left\lfloor\frac{x}{5}\right\rfloor\right)+10T\left(\left\lfloor\frac{x}{10}\right\rfloor\right)\right).$$
وعندما \(g(a)=10\)، يجب بعد ذلك طرح القيمة \(b=1\)، لأن المجموع الكلي يبدأ من \(2\).
عند جمع الأعداد والأوزان الاستثنائية على جميع قيم \(a\)، نحصل على
$$N_{10}(n)=|E_n|,\qquad S_{a,10}(n)=\sum_{(a,b)\in E_n} a,\qquad S_{ab,10}(n)=\sum_{(a,b)\in E_n} ab.$$
بعد ذلك تجمع التطبيقات كل الأجزاء وفقا للعلاقة
$$4s(n)=8S_{ab}(n)-12S_a(n)+6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n).$$
وبشكل مكافئ،
$$s(n)=2S_{ab}(n)-3S_a(n)+\frac{6S_{a,10}(n)+4N_{10}(n)-6S_{ab,10}(n)}{4}.$$
كما يمكن فهم ذلك على مستوى الزوج الواحد. كل عنصر \((a,b)\in C_n\) يساهم بالمقدار
$$w(a,b)= \begin{cases} 2ab-\dfrac{3}{2}(a+b), & g(a)g(b)\ne 10,\\[6pt] \dfrac{2ab-3a-3b+4}{4}, & g(a)g(b)=10. \end{cases}$$
ومن ثم
$$s(n)=\sum_{(a,b)\in C_n} w(a,b).$$
وظهور العامل \(\tfrac14\) في الحالة الاستثنائية هو السبب المباشر في أن البرامج تحمل القيمة الصحيحة \(4s(n)\) من البداية إلى النهاية.
عند \(n=10\) تعطي مجاميع Mobius القيم
$$S_{ab}(10)=1554,\qquad S_a(10)=261.$$
أما المجموعة الاستثنائية \(E_{10}\) فتحتوي على \(14\) زوجا مرتبا، ومنها \((2,5)\) و\((3,10)\) و\((5,8)\) و\((10,3)\) و\((10,9)\). وتكون مجاميعها
$$N_{10}(10)=14,\qquad S_{a,10}(10)=89,\qquad S_{ab,10}(10)=580.$$
وبالتعويض نحصل على
$$\begin{aligned} 4s(10) &=8\cdot 1554-12\cdot 261+6\cdot 89+4\cdot 14-6\cdot 580\\ &=12432-3132+534+56-3480\\ &=6410, \end{aligned}$$
ومن ثم
$$s(10)=\frac{6410}{4}=1602.5.$$
وهذا يطابق تماما قيمة التحقق المستخدمة في التنفيذ.
تتبع تطبيقات C++ وPython وJava التفكيك الرياضي نفسه. في البداية تبني جدولا لقيم Mobius حتى \(n\). ثم تحسب مجموعي القواسم الكبيرين \(S_{ab}^{\ast}(n)\) و\(S_a^{\ast}(n)\)، وبعد ذلك تطبق تصحيح الحدود الذي يزيل الحالات \(a=1\) أو \(b=1\).
بعد ذلك تعالج الشيفرة السلال الأربع المرتبطة بالعدد \(10\). وبدلا من تحليل كل \(a\) على حدة وتعداد قواسمة، تمر على كل قاسم \(d\)، وتحسب مرة واحدة صيغة العدد وصيغة المجموع الموزون، ثم توزع المساهمة المضروبة في \(\mu(d)\) على جميع مضاعفات \(d\). بهذه الطريقة تتكون جداول بحسب \(a\) للمجموعة الاستثنائية من غير تعداد الأزواج \((a,b)\) صراحة. يمكن لنسخة C++ تشغيل المسارات الأربع المستقلة على التوازي عندما يكون الإدخال كبيرا بما يكفي، بينما تحافظ نسختا Python وJava على البنية الحسابية نفسها وعلى القيمة الدقيقة نفسها في النهاية.
غربال Mobius خطي، ولذلك يكلف \(O(n)\) زمنا و\(O(n)\) ذاكرة. أما الجزء المهيمن فهو المرور من القاسم إلى مضاعفاته في جداول السلال الأربع، ويخضع حجمه الكلي للتقدير
$$\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor = O(n\log n).$$
إذن تعمل الخوارزمية كلها في \(O(n\log n)\) زمنيا وتحتاج إلى \(O(n)\) ذاكرة. التنفيذ المتوازي في نسخة C++ يحسن الزمن الفعلي فقط، ولا يغير الرتبة التقاربية.