The ellipse geometry in Problem 471 reduces to the arithmetic sum
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor} r(a,b), \qquad r(a,b)=\frac{b(a-2b)}{a-b}.$$
Each admissible pair \((a,b)\) contributes one radius term. The challenge is that the real input is enormous, so a direct double loop is far too slow. The implementations therefore reorganize the sum into two closed polynomial pieces and one harmonic interval.
The small checkpoints used by the implementations are \(r(3,1)=1/2\), \(r(6,2)=1\), \(r(12,3)=2\), \(G(10)=2.059722222\times 10^1\), and \(G(100)=1.922360980\times 10^4\).
Start from
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor}\frac{b(a-2b)}{a-b}.$$
The decisive simplification is to sum by the denominator \(a-b\) instead of summing by \(a\) first.
Set
$$c=a-b,$$
so \(a=b+c\). Then the summand becomes
$$r(a,b)=\frac{b(c-b)}{c}=b-\frac{b^2}{c}.$$
The original bounds are
$$b\ge 1,\qquad b\le \left\lfloor\frac{a-1}{2}\right\rfloor,\qquad a\le n.$$
After substituting \(a=b+c\), they become
$$1\le b\le c-1,\qquad 1\le b\le n-c.$$
Hence for fixed \(c\) the inner index runs over
$$1\le b\le B(c),\qquad B(c)=\min(c-1,n-c),$$
and the whole sum rewrites as
$$G(n)=\sum_{c=2}^{n-1}\sum_{b=1}^{B(c)}\left(b-\frac{b^2}{c}\right).$$
Define
$$q=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
If \(2\le c\le q\), then \(c-1\le n-c\), so \(B(c)=c-1\).
If \(q\lt c\le n-1\), then \(n-c\lt c\), so \(B(c)=n-c\).
Therefore
$$G(n)=\sum_{c=2}^{q}\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)+\sum_{c=q+1}^{n-1}\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right).$$
The low-denominator block becomes a pure polynomial. The high-denominator block is also mostly polynomial, except for one harmonic contribution.
For \(2\le c\le q\),
$$\sum_{b=1}^{c-1} b=\frac{(c-1)c}{2},\qquad \sum_{b=1}^{c-1} b^2=\frac{(c-1)c(2c-1)}{6}.$$
So the inner sum is
$$\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)=\frac{(c-1)c}{2}-\frac{(c-1)c(2c-1)}{6c}=\frac{c^2-1}{6}.$$
Summing over \(c\) gives
$$G_{\text{low}}(n)=\sum_{c=2}^{q}\frac{c^2-1}{6}=\frac{q(2q^2+3q-5)}{36}.$$
This is the first closed polynomial used by the implementation.
For \(q\lt c\le n-1\), the upper limit is \(n-c\). Thus
$$\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right)=\frac{(n-c)(n-c+1)}{2}-\frac{(n-c)(n-c+1)(2n-2c+1)}{6c}.$$
The first term is polynomial. Writing \(x=n-c\), where \(x=1,2,\dots,m\), gives
$$\sum_{c=n-m}^{n-1}\frac{(n-c)(n-c+1)}{2}=\sum_{x=1}^{m}\frac{x(x+1)}{2}=\frac{m(m+1)(m+2)}{6}.$$
The second term is the only non-polynomial piece. Expand its numerator over the denominator \(c\):
$$\frac{(n-c)(n-c+1)(2n-2c+1)}{c}=\frac{n(n+1)(2n+1)}{c}-(6n^2+6n+1)+(6n+3)c-2c^2.$$
Now set
$$L=n-m,\qquad R=n-1,\qquad H_{L,R}=\sum_{k=L}^{R}\frac{1}{k}.$$
Also define the elementary sums
$$S_1=\sum_{k=L}^{R}k=\frac{(L+R)m}{2},$$
$$S_2=\sum_{k=L}^{R}k^2=\frac{R(R+1)(2R+1)-(L-1)L(2L-1)}{6}.$$
Then the rational tail becomes
$$T(n)=n(n+1)(2n+1)H_{L,R}-(6n^2+6n+1)m+(6n+3)S_1-2S_2.$$
Combining the low block, the polynomial part of the high block, and the rational tail gives
$$\boxed{G(n)=\frac{q(2q^2+3q-5)}{36}+\frac{m(m+1)(m+2)}{6}-\frac{T(n)}{6}.}$$
So the entire problem has been reduced to evaluating a single harmonic interval. For short intervals the implementations sum reciprocals directly. For large intervals they use the Euler-Maclaurin expansion
$$H_t=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}+\frac{1}{240t^8}-\frac{5}{660t^{10}}+O(t^{-12}),$$
and then compute \(H_{L,R}=H_R-H_{L-1}\).
Here
$$q=\left\lfloor\frac{10}{2}\right\rfloor=5,\qquad m=\left\lfloor\frac{9}{2}\right\rfloor=4,\qquad L=6,\qquad R=9.$$
The low block is
$$G_{\text{low}}(10)=\frac{5(2\cdot 5^2+3\cdot 5-5)}{36}=\frac{25}{3}.$$
The polynomial part of the high block is
$$\frac{4\cdot 5\cdot 6}{6}=20.$$
The harmonic interval is
$$H_{6,9}=\frac16+\frac17+\frac18+\frac19=\frac{275}{504}.$$
Also
$$S_1=6+7+8+9=30,\qquad S_2=6^2+7^2+8^2+9^2=230.$$
Therefore
$$T(10)=10\cdot 11\cdot 21\cdot \frac{275}{504}-661\cdot 4+63\cdot 30-2\cdot 230=\frac{557}{12}.$$
So
$$G(10)=\frac{25}{3}+20-\frac{1}{6}\cdot\frac{557}{12}=\frac{1483}{72}=20.597222\ldots,$$
which matches the checkpoint \(2.059722222\times 10^1\).
The C++, Python, and Java implementations all evaluate the same closed form. They compute \(q\), \(m\), \(L\), and \(R\), evaluate the two polynomial pieces, and then evaluate the harmonic interval \(H_{L,R}\).
When the harmonic interval is small, the implementation sums reciprocals directly. When the interval is large, it evaluates the truncated Euler-Maclaurin series for \(H_R\) and \(H_{L-1}\) and subtracts them. The C++ implementation also keeps a direct double-sum routine for checkpoint validation on small inputs.
Finally, the implementation forms \(T(n)\), combines the three contributions, and prints the result in scientific notation with one digit before the decimal point and nine digits after it.
The fast method uses \(O(1)\) memory. For very large inputs its running time is effectively \(O(1)\), because the only non-polynomial piece is replaced by a constant-length asymptotic expansion. For short harmonic intervals the code may still do a direct reciprocal sum up to a fixed cutoff, so the practical fast path is bounded independently of \(n\). The validation path that literally enumerates admissible pairs remains \(O(n^2)\) time and \(O(1)\) extra memory.
Die Geometrie von Problem 471 wird auf die arithmetische Summe
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor} r(a,b), \qquad r(a,b)=\frac{b(a-2b)}{a-b}$$
zurückgeführt. Jedes zulässige Paar \((a,b)\) liefert genau einen Radiusbeitrag. Für die echten Eingaben ist die Doppelsumme aber viel zu groß, daher formen die Implementierungen sie in zwei geschlossene Polynomteile und ein harmonisches Intervall um.
Verwendete Kontrollwerte sind \(r(3,1)=1/2\), \(r(6,2)=1\), \(r(12,3)=2\), \(G(10)=2.059722222\times 10^1\) und \(G(100)=1.922360980\times 10^4\).
Ausgangspunkt ist
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor}\frac{b(a-2b)}{a-b}.$$
Der entscheidende Schritt ist, nicht zuerst nach \(a\), sondern nach dem Nenner \(a-b\) zu summieren.
Setze
$$c=a-b,$$
dann ist \(a=b+c\). Der Summand wird zu
$$r(a,b)=\frac{b(c-b)}{c}=b-\frac{b^2}{c}.$$
Die ursprünglichen Bedingungen lauten
$$b\ge 1,\qquad b\le \left\lfloor\frac{a-1}{2}\right\rfloor,\qquad a\le n.$$
Nach dem Einsetzen von \(a=b+c\) werden daraus
$$1\le b\le c-1,\qquad 1\le b\le n-c.$$
Für festes \(c\) läuft \(b\) also über
$$1\le b\le B(c),\qquad B(c)=\min(c-1,n-c),$$
und damit gilt
$$G(n)=\sum_{c=2}^{n-1}\sum_{b=1}^{B(c)}\left(b-\frac{b^2}{c}\right).$$
Definiere
$$q=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
Für \(2\le c\le q\) ist \(c-1\le n-c\), also \(B(c)=c-1\).
Für \(q\lt c\le n-1\) ist \(n-c\lt c\), also \(B(c)=n-c\).
Daher zerfällt die Summe in
$$G(n)=\sum_{c=2}^{q}\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)+\sum_{c=q+1}^{n-1}\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right).$$
Der erste Block wird ein reines Polynom, der zweite Block ist fast polynomial und enthält nur noch einen harmonischen Rest.
Für \(2\le c\le q\) gilt
$$\sum_{b=1}^{c-1} b=\frac{(c-1)c}{2},\qquad \sum_{b=1}^{c-1} b^2=\frac{(c-1)c(2c-1)}{6}.$$
Somit ist die innere Summe
$$\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)=\frac{(c-1)c}{2}-\frac{(c-1)c(2c-1)}{6c}=\frac{c^2-1}{6}.$$
Über alle \(c\) summiert ergibt das
$$G_{\text{low}}(n)=\sum_{c=2}^{q}\frac{c^2-1}{6}=\frac{q(2q^2+3q-5)}{36}.$$
Genau dieses Polynom bildet den ersten geschlossenen Term der Implementierung.
Für \(q\lt c\le n-1\) ist die obere Grenze \(n-c\). Also
$$\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right)=\frac{(n-c)(n-c+1)}{2}-\frac{(n-c)(n-c+1)(2n-2c+1)}{6c}.$$
Der erste Teil ist wieder polynomial. Mit \(x=n-c\), also \(x=1,2,\dots,m\), erhält man
$$\sum_{c=n-m}^{n-1}\frac{(n-c)(n-c+1)}{2}=\sum_{x=1}^{m}\frac{x(x+1)}{2}=\frac{m(m+1)(m+2)}{6}.$$
Der zweite Teil ist der einzige nichtpolynomiale Rest. Der Zähler wird über dem Nenner \(c\) entwickelt:
$$\frac{(n-c)(n-c+1)(2n-2c+1)}{c}=\frac{n(n+1)(2n+1)}{c}-(6n^2+6n+1)+(6n+3)c-2c^2.$$
Setze nun
$$L=n-m,\qquad R=n-1,\qquad H_{L,R}=\sum_{k=L}^{R}\frac{1}{k}.$$
Dazu kommen die elementaren Summen
$$S_1=\sum_{k=L}^{R}k=\frac{(L+R)m}{2},$$
$$S_2=\sum_{k=L}^{R}k^2=\frac{R(R+1)(2R+1)-(L-1)L(2L-1)}{6}.$$
Dann lautet der rationale Rest
$$T(n)=n(n+1)(2n+1)H_{L,R}-(6n^2+6n+1)m+(6n+3)S_1-2S_2.$$
Aus dem kleinen Block, dem polynomialen Anteil des großen Blocks und dem rationalen Rest folgt
$$\boxed{G(n)=\frac{q(2q^2+3q-5)}{36}+\frac{m(m+1)(m+2)}{6}-\frac{T(n)}{6}.}$$
Damit ist das ganze Problem auf ein einziges harmonisches Intervall reduziert. Für kurze Intervalle summieren die Implementierungen die Kehrwerte direkt. Für große Intervalle verwenden sie die Euler-Maclaurin-Entwicklung
$$H_t=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}+\frac{1}{240t^8}-\frac{5}{660t^{10}}+O(t^{-12}),$$
und setzen dann \(H_{L,R}=H_R-H_{L-1}\).
Hier ist
$$q=\left\lfloor\frac{10}{2}\right\rfloor=5,\qquad m=\left\lfloor\frac{9}{2}\right\rfloor=4,\qquad L=6,\qquad R=9.$$
Der kleine Block ergibt
$$G_{\text{low}}(10)=\frac{5(2\cdot 5^2+3\cdot 5-5)}{36}=\frac{25}{3}.$$
Der polynomiale Anteil des großen Blocks ist
$$\frac{4\cdot 5\cdot 6}{6}=20.$$
Das harmonische Intervall ist
$$H_{6,9}=\frac16+\frac17+\frac18+\frac19=\frac{275}{504}.$$
Außerdem gilt
$$S_1=6+7+8+9=30,\qquad S_2=6^2+7^2+8^2+9^2=230.$$
Also
$$T(10)=10\cdot 11\cdot 21\cdot \frac{275}{504}-661\cdot 4+63\cdot 30-2\cdot 230=\frac{557}{12}.$$
Damit folgt
$$G(10)=\frac{25}{3}+20-\frac{1}{6}\cdot\frac{557}{12}=\frac{1483}{72}=20.597222\ldots,$$
genau passend zum Kontrollwert \(2.059722222\times 10^1\).
Die C++-, Python- und Java-Implementierungen werten alle dieselbe geschlossene Formel aus. Sie berechnen \(q\), \(m\), \(L\) und \(R\), bestimmen die beiden Polynomteile und berechnen danach das harmonische Intervall \(H_{L,R}\).
Ist das harmonische Intervall klein, summiert die Implementierung die Kehrwerte direkt. Ist es groß, wird die abgeschnittene Euler-Maclaurin-Reihe für \(H_R\) und \(H_{L-1}\) ausgewertet und die Differenz gebildet. Die C++-Implementierung enthält zusätzlich eine direkte Doppelsumme zur Kontrolle kleiner Eingaben.
Zum Schluss wird \(T(n)\) gebildet, alles zusammengefügt und das Ergebnis in wissenschaftlicher Schreibweise mit einer Ziffer vor dem Komma und neun Ziffern danach ausgegeben.
Die schnelle Methode benötigt \(O(1)\) Speicher. Für sehr große Eingaben ist die Laufzeit praktisch \(O(1)\), weil der einzige nichtpolynomiale Anteil durch eine feste asymptotische Entwicklung ersetzt wird. Bei kurzen harmonischen Intervallen kann der Code noch eine direkte Kehrwertsumme bis zu einer festen Grenze ausführen, aber auch diese Grenze hängt nicht von \(n\) ab. Der Kontrollpfad mit expliziter Enumeration aller zulässigen Paare bleibt \(O(n^2)\) Zeit und \(O(1)\) Zusatzspeicher.
Problem 471'deki elips geometrisi şu aritmetik toplama indirgenir:
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor} r(a,b), \qquad r(a,b)=\frac{b(a-2b)}{a-b}.$$
Her uygun \((a,b)\) çifti bir yarıçap terimi üretir. Gerçek giriş çok büyük olduğu için doğrudan çift döngü kullanmak aşırı yavaştır. Bu yüzden uygulamalar toplamı iki kapalı polinom parçaya ve bir harmonik aralığa dönüştürür.
Uygulamalarda kullanılan küçük kontrol değerleri şunlardır: \(r(3,1)=1/2\), \(r(6,2)=1\), \(r(12,3)=2\), \(G(10)=2.059722222\times 10^1\) ve \(G(100)=1.922360980\times 10^4\).
Başlangıç noktamız
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor}\frac{b(a-2b)}{a-b}$$
toplamıdır. Kritik fikir, önce \(a\)'ya göre değil, paydadaki \(a-b\) değerine göre toplamaktır.
Şunu tanımlayalım:
$$c=a-b,$$
böylece \(a=b+c\) olur. Toplanan ifade
$$r(a,b)=\frac{b(c-b)}{c}=b-\frac{b^2}{c}$$
şekline dönüşür. İlk sınırlar
$$b\ge 1,\qquad b\le \left\lfloor\frac{a-1}{2}\right\rfloor,\qquad a\le n$$
idi. \(a=b+c\) yazınca bunlar
$$1\le b\le c-1,\qquad 1\le b\le n-c$$
olur. Demek ki sabit bir \(c\) için iç indis aralığı
$$1\le b\le B(c),\qquad B(c)=\min(c-1,n-c)$$
ve tüm toplam
$$G(n)=\sum_{c=2}^{n-1}\sum_{b=1}^{B(c)}\left(b-\frac{b^2}{c}\right)$$
biçiminde yeniden yazılır.
Şunları tanımlayalım:
$$q=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
\(2\le c\le q\) iken \(c-1\le n-c\) olduğundan \(B(c)=c-1\) olur.
\(q\lt c\le n-1\) iken \(n-c\lt c\) olduğundan \(B(c)=n-c\) olur.
Böylece
$$G(n)=\sum_{c=2}^{q}\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)+\sum_{c=q+1}^{n-1}\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right)$$
elde edilir. Küçük payda bloğu tamamen polinoma dönüşür. Büyük payda bloğu ise bir harmonik terim dışında yine kapalı biçimdedir.
\(2\le c\le q\) için
$$\sum_{b=1}^{c-1} b=\frac{(c-1)c}{2},\qquad \sum_{b=1}^{c-1} b^2=\frac{(c-1)c(2c-1)}{6}$$
olur. Dolayısıyla iç toplam
$$\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)=\frac{(c-1)c}{2}-\frac{(c-1)c(2c-1)}{6c}=\frac{c^2-1}{6}$$
şeklindedir. Tüm \(c\) değerleri için toplarsak
$$G_{\text{low}}(n)=\sum_{c=2}^{q}\frac{c^2-1}{6}=\frac{q(2q^2+3q-5)}{36}$$
sonucuna ulaşırız. Bu, uygulamanın kullandığı ilk kapalı polinomdur.
\(q\lt c\le n-1\) için üst sınır \(n-c\)'dir. Bu yüzden
$$\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right)=\frac{(n-c)(n-c+1)}{2}-\frac{(n-c)(n-c+1)(2n-2c+1)}{6c}$$
elde edilir. İlk parça polinomdur. \(x=n-c\) yazarsak \(x=1,2,\dots,m\) olur ve
$$\sum_{c=n-m}^{n-1}\frac{(n-c)(n-c+1)}{2}=\sum_{x=1}^{m}\frac{x(x+1)}{2}=\frac{m(m+1)(m+2)}{6}$$
bulunur. İkinci parça ise tek gerçek rasyonel kuyruktur. Payı \(c\)'ye göre açarsak
$$\frac{(n-c)(n-c+1)(2n-2c+1)}{c}=\frac{n(n+1)(2n+1)}{c}-(6n^2+6n+1)+(6n+3)c-2c^2$$
olur. Şimdi
$$L=n-m,\qquad R=n-1,\qquad H_{L,R}=\sum_{k=L}^{R}\frac{1}{k}$$
tanımlarını yapalım. Ayrıca
$$S_1=\sum_{k=L}^{R}k=\frac{(L+R)m}{2},$$
$$S_2=\sum_{k=L}^{R}k^2=\frac{R(R+1)(2R+1)-(L-1)L(2L-1)}{6}$$
olsun. O zaman rasyonel kuyruk
$$T(n)=n(n+1)(2n+1)H_{L,R}-(6n^2+6n+1)m+(6n+3)S_1-2S_2$$
şekline iner.
Küçük blok, büyük bloğun polinom kısmı ve rasyonel kuyruk birleştirilince
$$\boxed{G(n)=\frac{q(2q^2+3q-5)}{36}+\frac{m(m+1)(m+2)}{6}-\frac{T(n)}{6}.}$$
Böylece bütün zorluk tek bir harmonik aralığın hesaplanmasına indirgenmiş olur. Aralık kısa ise uygulamalar tersleri doğrudan toplar. Aralık büyükse Euler-Maclaurin açılımını kullanırlar:
$$H_t=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}+\frac{1}{240t^8}-\frac{5}{660t^{10}}+O(t^{-12}),$$
ve sonra \(H_{L,R}=H_R-H_{L-1}\) hesaplanır.
Burada
$$q=\left\lfloor\frac{10}{2}\right\rfloor=5,\qquad m=\left\lfloor\frac{9}{2}\right\rfloor=4,\qquad L=6,\qquad R=9$$
olur. Küçük blok
$$G_{\text{low}}(10)=\frac{5(2\cdot 5^2+3\cdot 5-5)}{36}=\frac{25}{3}$$
verir. Büyük bloğun polinom kısmı
$$\frac{4\cdot 5\cdot 6}{6}=20$$
olur. Harmonik aralık ise
$$H_{6,9}=\frac16+\frac17+\frac18+\frac19=\frac{275}{504}$$
şeklindedir. Ayrıca
$$S_1=6+7+8+9=30,\qquad S_2=6^2+7^2+8^2+9^2=230$$
olduğundan
$$T(10)=10\cdot 11\cdot 21\cdot \frac{275}{504}-661\cdot 4+63\cdot 30-2\cdot 230=\frac{557}{12}$$
bulunur. Sonuç olarak
$$G(10)=\frac{25}{3}+20-\frac{1}{6}\cdot\frac{557}{12}=\frac{1483}{72}=20.597222\ldots,$$
yani kontrol değeri \(2.059722222\times 10^1\) tam olarak elde edilir.
C++, Python ve Java uygulamaları aynı kapalı formu değerlendirir. Önce \(q\), \(m\), \(L\) ve \(R\) hesaplanır; sonra iki polinom parça bulunur; ardından harmonik aralık \(H_{L,R}\) hesaplanır.
Harmonik aralık küçükse uygulama \(1/L+1/(L+1)+\dots+1/R\) toplamını doğrudan yapar. Aralık büyükse \(H_R\) ve \(H_{L-1}\) için kesilmiş Euler-Maclaurin serisi hesaplanır ve fark alınır. C++ uygulaması ayrıca küçük girdilerde doğrulama için doğrudan çift toplamı da korur.
Son adımda \(T(n)\) oluşturulur, üç katkı birleştirilir ve sonuç bilimsel gösterimde, on anlamlı basamağa karşılık gelen biçimde yazdırılır.
Hızlı yöntem \(O(1)\) bellek kullanır. Çok büyük girdilerde çalışma süresi pratikte \(O(1)\)'dir; çünkü polinom olmayan tek bölüm sabit uzunluklu bir asimptotik açılımla değerlendirilir. Kısa harmonik aralıklarda kod sabit bir eşik kadar doğrudan ters toplamı yapabilir, fakat bu maliyet de \(n\)'e bağlı büyümez. Uygun çiftleri tek tek gezen doğrulama yolu ise \(O(n^2)\) zaman ve \(O(1)\) ek bellek gerektirir.
La geometría de la elipse en el Problema 471 se reduce a la suma aritmética
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor} r(a,b), \qquad r(a,b)=\frac{b(a-2b)}{a-b}.$$
Cada par admisible \((a,b)\) aporta un término de radio. Como la entrada real es enorme, el doble bucle directo es inviable. Por eso las implementaciones reorganizan la suma en dos partes polinómicas cerradas y un único intervalo armónico.
Los puntos de control usados por las implementaciones son \(r(3,1)=1/2\), \(r(6,2)=1\), \(r(12,3)=2\), \(G(10)=2.059722222\times 10^1\) y \(G(100)=1.922360980\times 10^4\).
Partimos de
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor}\frac{b(a-2b)}{a-b}.$$
La simplificación clave consiste en sumar por el denominador \(a-b\) en lugar de sumar primero por \(a\).
Tomemos
$$c=a-b,$$
de modo que \(a=b+c\). Entonces el sumando se convierte en
$$r(a,b)=\frac{b(c-b)}{c}=b-\frac{b^2}{c}.$$
Las restricciones originales son
$$b\ge 1,\qquad b\le \left\lfloor\frac{a-1}{2}\right\rfloor,\qquad a\le n.$$
Al sustituir \(a=b+c\), pasan a ser
$$1\le b\le c-1,\qquad 1\le b\le n-c.$$
Por lo tanto, para un \(c\) fijo, el índice interior recorre
$$1\le b\le B(c),\qquad B(c)=\min(c-1,n-c),$$
y la suma completa queda
$$G(n)=\sum_{c=2}^{n-1}\sum_{b=1}^{B(c)}\left(b-\frac{b^2}{c}\right).$$
Definimos
$$q=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
Si \(2\le c\le q\), entonces \(c-1\le n-c\), así que \(B(c)=c-1\).
Si \(q\lt c\le n-1\), entonces \(n-c\lt c\), así que \(B(c)=n-c\).
En consecuencia,
$$G(n)=\sum_{c=2}^{q}\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)+\sum_{c=q+1}^{n-1}\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right).$$
El bloque de denominadores pequeños se vuelve puramente polinómico. El bloque de denominadores grandes también es casi polinómico, salvo por una contribución armónica.
Para \(2\le c\le q\),
$$\sum_{b=1}^{c-1} b=\frac{(c-1)c}{2},\qquad \sum_{b=1}^{c-1} b^2=\frac{(c-1)c(2c-1)}{6}.$$
Por tanto, la suma interior es
$$\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)=\frac{(c-1)c}{2}-\frac{(c-1)c(2c-1)}{6c}=\frac{c^2-1}{6}.$$
Al sumar sobre \(c\), obtenemos
$$G_{\text{low}}(n)=\sum_{c=2}^{q}\frac{c^2-1}{6}=\frac{q(2q^2+3q-5)}{36}.$$
Este es el primer polinomio cerrado que usa la implementación.
Para \(q\lt c\le n-1\), el límite superior es \(n-c\). Entonces
$$\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right)=\frac{(n-c)(n-c+1)}{2}-\frac{(n-c)(n-c+1)(2n-2c+1)}{6c}.$$
La primera parte es polinómica. Si escribimos \(x=n-c\), con \(x=1,2,\dots,m\), resulta
$$\sum_{c=n-m}^{n-1}\frac{(n-c)(n-c+1)}{2}=\sum_{x=1}^{m}\frac{x(x+1)}{2}=\frac{m(m+1)(m+2)}{6}.$$
La segunda parte es el único resto no polinómico. Al expandir su numerador sobre el denominador \(c\), se obtiene
$$\frac{(n-c)(n-c+1)(2n-2c+1)}{c}=\frac{n(n+1)(2n+1)}{c}-(6n^2+6n+1)+(6n+3)c-2c^2.$$
Ahora definimos
$$L=n-m,\qquad R=n-1,\qquad H_{L,R}=\sum_{k=L}^{R}\frac{1}{k}.$$
También usamos
$$S_1=\sum_{k=L}^{R}k=\frac{(L+R)m}{2},$$
$$S_2=\sum_{k=L}^{R}k^2=\frac{R(R+1)(2R+1)-(L-1)L(2L-1)}{6}.$$
Así, la cola racional queda
$$T(n)=n(n+1)(2n+1)H_{L,R}-(6n^2+6n+1)m+(6n+3)S_1-2S_2.$$
Al combinar el bloque bajo, la parte polinómica del bloque alto y la cola racional, aparece
$$\boxed{G(n)=\frac{q(2q^2+3q-5)}{36}+\frac{m(m+1)(m+2)}{6}-\frac{T(n)}{6}.}$$
Todo el problema queda reducido a evaluar un solo intervalo armónico. Si el intervalo es corto, las implementaciones suman los recíprocos directamente. Si es largo, usan la expansión de Euler-Maclaurin
$$H_t=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}+\frac{1}{240t^8}-\frac{5}{660t^{10}}+O(t^{-12}),$$
y luego calculan \(H_{L,R}=H_R-H_{L-1}\).
Aquí
$$q=\left\lfloor\frac{10}{2}\right\rfloor=5,\qquad m=\left\lfloor\frac{9}{2}\right\rfloor=4,\qquad L=6,\qquad R=9.$$
El bloque bajo vale
$$G_{\text{low}}(10)=\frac{5(2\cdot 5^2+3\cdot 5-5)}{36}=\frac{25}{3}.$$
La parte polinómica del bloque alto es
$$\frac{4\cdot 5\cdot 6}{6}=20.$$
El intervalo armónico es
$$H_{6,9}=\frac16+\frac17+\frac18+\frac19=\frac{275}{504}.$$
Además,
$$S_1=6+7+8+9=30,\qquad S_2=6^2+7^2+8^2+9^2=230.$$
Por lo tanto,
$$T(10)=10\cdot 11\cdot 21\cdot \frac{275}{504}-661\cdot 4+63\cdot 30-2\cdot 230=\frac{557}{12}.$$
Y entonces
$$G(10)=\frac{25}{3}+20-\frac{1}{6}\cdot\frac{557}{12}=\frac{1483}{72}=20.597222\ldots,$$
que coincide exactamente con el punto de control \(2.059722222\times 10^1\).
Las implementaciones en C++, Python y Java evalúan la misma fórmula cerrada. Primero calculan \(q\), \(m\), \(L\) y \(R\); luego obtienen las dos partes polinómicas; después calculan el intervalo armónico \(H_{L,R}\).
Si el intervalo armónico es pequeño, la implementación suma los recíprocos directamente. Si es grande, evalúa la serie truncada de Euler-Maclaurin para \(H_R\) y \(H_{L-1}\) y toma la diferencia. La implementación en C++ además conserva una doble suma directa para validar pequeños casos de prueba.
Al final, la implementación forma \(T(n)\), combina las tres contribuciones y muestra el resultado en notación científica con una cifra antes del punto decimal y nueve después.
El método rápido usa \(O(1)\) memoria. Para entradas muy grandes, el tiempo es efectivamente \(O(1)\), porque la única parte no polinómica se sustituye por una expansión asintótica de longitud fija. En intervalos armónicos cortos, el código todavía puede hacer una suma directa de recíprocos hasta un umbral fijo, pero ese coste tampoco crece con \(n\). La ruta de validación que enumera literalmente los pares admisibles sigue siendo \(O(n^2)\) en tiempo y \(O(1)\) en memoria extra.
第 471 题中的椭圆几何最终化成下面这个算术求和：
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor} r(a,b), \qquad r(a,b)=\frac{b(a-2b)}{a-b}.$$
每一个合法的 \((a,b)\) 都贡献一个半径项。真正的输入规模极大，所以直接枚举双重循环完全不现实。实现采取的做法是把总和改写成两个闭式多项式部分，再加上一个调和区间，从而把核心计算压缩到常数规模。
程序使用的小规模校验点包括 \(r(3,1)=1/2\)、\(r(6,2)=1\)、\(r(12,3)=2\)、\(G(10)=2.059722222\times 10^1\) 以及 \(G(100)=1.922360980\times 10^4\)。
从原始求和式开始：
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor}\frac{b(a-2b)}{a-b}.$$
真正的突破点不是继续按 \(a\) 来做内外层求和，而是改成按分母 \(a-b\) 来整理所有项。
令
$$c=a-b,$$
于是 \(a=b+c\)。原来的被加项立刻化简为
$$r(a,b)=\frac{b(c-b)}{c}=b-\frac{b^2}{c}.$$
原始约束是
$$b\ge 1,\qquad b\le \left\lfloor\frac{a-1}{2}\right\rfloor,\qquad a\le n.$$
把 \(a=b+c\) 代入后，第二个条件等价于 \(b\le c-1\)，第三个条件等价于 \(b\le n-c\)。因此固定 \(c\) 时，\(b\) 的范围就是
$$1\le b\le B(c),\qquad B(c)=\min(c-1,n-c).$$
整道题的总和于是改写成
$$G(n)=\sum_{c=2}^{n-1}\sum_{b=1}^{B(c)}\left(b-\frac{b^2}{c}\right).$$
这样做的好处是，几何条件已经完全吸收到一个非常简单的上界函数 \(B(c)\) 里了。
记
$$q=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
当 \(2\le c\le q\) 时，有 \(c-1\le n-c\)，所以上界是 \(B(c)=c-1\)。
当 \(q\lt c\le n-1\) 时，有 \(n-c\lt c\)，所以上界变成 \(B(c)=n-c\)。
因此总和自然拆成两部分：
$$G(n)=\sum_{c=2}^{q}\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)+\sum_{c=q+1}^{n-1}\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right).$$
前一部分会完全化为多项式；后一部分也几乎都是多项式，只剩下一段调和和。
对于 \(2\le c\le q\)，有标准求和公式
$$\sum_{b=1}^{c-1} b=\frac{(c-1)c}{2},\qquad \sum_{b=1}^{c-1} b^2=\frac{(c-1)c(2c-1)}{6}.$$
于是内层和可以直接化简：
$$\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)=\frac{(c-1)c}{2}-\frac{(c-1)c(2c-1)}{6c}=\frac{c^2-1}{6}.$$
再对 \(c\) 从 \(2\) 加到 \(q\)，得到
$$G_{\text{low}}(n)=\sum_{c=2}^{q}\frac{c^2-1}{6}=\frac{q(2q^2+3q-5)}{36}.$$
这就是实现中第一个闭式多项式块。也就是说，整个前半段求和根本不需要逐项循环。
对于 \(q\lt c\le n-1\)，上界是 \(n-c\)，所以内层和变成
$$\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right)=\frac{(n-c)(n-c+1)}{2}-\frac{(n-c)(n-c+1)(2n-2c+1)}{6c}.$$
第一项仍然是多项式。如果设 \(x=n-c\)，那么 \(x\) 正好从 \(1\) 跑到 \(m\)，于是
$$\sum_{c=n-m}^{n-1}\frac{(n-c)(n-c+1)}{2}=\sum_{x=1}^{m}\frac{x(x+1)}{2}=\frac{m(m+1)(m+2)}{6}.$$
第二项才是真正需要额外处理的“有分母”部分。把它的分子按 \(c\) 展开，可以得到
$$\frac{(n-c)(n-c+1)(2n-2c+1)}{c}=\frac{n(n+1)(2n+1)}{c}-(6n^2+6n+1)+(6n+3)c-2c^2.$$
这一步很关键，因为它把复杂的有理式拆成了四个标准对象：一个调和和、一个常数项、一个一次幂求和、一个平方和。
记
$$L=n-m,\qquad R=n-1,\qquad H_{L,R}=\sum_{k=L}^{R}\frac{1}{k}.$$
另外再写出两个基本和式：
$$S_1=\sum_{k=L}^{R}k=\frac{(L+R)m}{2},$$
$$S_2=\sum_{k=L}^{R}k^2=\frac{R(R+1)(2R+1)-(L-1)L(2L-1)}{6}.$$
于是整段有理尾项可以统一写成
$$T(n)=n(n+1)(2n+1)H_{L,R}-(6n^2+6n+1)m+(6n+3)S_1-2S_2.$$
现在把“小分母块”“大分母块中的多项式部分”“有理尾项”三者合并，得到
$$\boxed{G(n)=\frac{q(2q^2+3q-5)}{36}+\frac{m(m+1)(m+2)}{6}-\frac{T(n)}{6}.}$$
到这里，题目已经从一个二维求和问题变成了一个调和区间求值问题。若区间很短，直接累加 \(1/L,1/(L+1),\dots,1/R\) 就行。若区间很长，就使用调和数的 Euler-Maclaurin 渐近展开：
$$H_t=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}+\frac{1}{240t^8}-\frac{5}{660t^{10}}+O(t^{-12}),$$
然后计算 \(H_{L,R}=H_R-H_{L-1}\)。实现中的高精度部分正是围绕这个公式展开的。
取 \(n=10\) 时，
$$q=\left\lfloor\frac{10}{2}\right\rfloor=5,\qquad m=\left\lfloor\frac{9}{2}\right\rfloor=4,\qquad L=6,\qquad R=9.$$
小分母块为
$$G_{\text{low}}(10)=\frac{5(2\cdot 5^2+3\cdot 5-5)}{36}=\frac{25}{3}.$$
大分母块中的多项式部分为
$$\frac{4\cdot 5\cdot 6}{6}=20.$$
调和区间为
$$H_{6,9}=\frac16+\frac17+\frac18+\frac19=\frac{275}{504}.$$
同时
$$S_1=6+7+8+9=30,\qquad S_2=6^2+7^2+8^2+9^2=230.$$
因此
$$T(10)=10\cdot 11\cdot 21\cdot \frac{275}{504}-661\cdot 4+63\cdot 30-2\cdot 230=\frac{557}{12}.$$
代回总公式后得到
$$G(10)=\frac{25}{3}+20-\frac{1}{6}\cdot\frac{557}{12}=\frac{1483}{72}=20.597222\ldots,$$
这与程序校验值 \(2.059722222\times 10^1\) 完全一致。
C++、Python 和 Java 三个实现都在计算同一个闭式。它们先求出 \(q\)、\(m\)、\(L\)、\(R\)，然后直接计算两个多项式块，再去处理调和区间 \(H_{L,R}\)。
如果调和区间比较短，实现就直接逐项累加倒数；如果区间很长，就分别估算 \(H_R\) 与 \(H_{L-1}\) 的 Euler-Maclaurin 截断展开，再取差值。C++ 版本另外保留了一个直接双重求和的验证路径，用来检查小输入时快速公式是否正确。
最后，程序构造 \(T(n)\)，把三部分结果合并，并按科学计数法输出，格式是一位整数部分加九位小数部分。
快速算法使用 \(O(1)\) 额外空间。对于很大的输入，它的运行时间可以看作 \(O(1)\)，因为唯一的非多项式部分被固定长度的渐近展开所替代。对于较短的调和区间，实现仍可能直接做一段倒数求和，但这个代价有固定上限，并不会随着 \(n\) 继续增长。至于逐项枚举所有合法 \((a,b)\) 的验证路径，则仍然是 \(O(n^2)\) 时间和 \(O(1)\) 额外空间。
Геометрия задачи 471 сводится к арифметической сумме
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor} r(a,b), \qquad r(a,b)=\frac{b(a-2b)}{a-b}.$$
Каждая допустимая пара \((a,b)\) дает один вклад в радиус. Реальное значение \(n\) очень велико, поэтому прямой двойной цикл непригоден. Реализации перестраивают сумму в два замкнутых полиномиальных блока и один гармонический интервал.
Контрольные значения в коде таковы: \(r(3,1)=1/2\), \(r(6,2)=1\), \(r(12,3)=2\), \(G(10)=2.059722222\times 10^1\) и \(G(100)=1.922360980\times 10^4\).
Исходная формула имеет вид
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor}\frac{b(a-2b)}{a-b}.$$
Главный ход состоит в том, чтобы суммировать не по \(a\), а по знаменателю \(a-b\).
Положим
$$c=a-b,$$
тогда \(a=b+c\). Слагаемое превращается в
$$r(a,b)=\frac{b(c-b)}{c}=b-\frac{b^2}{c}.$$
Изначальные ограничения таковы:
$$b\ge 1,\qquad b\le \left\lfloor\frac{a-1}{2}\right\rfloor,\qquad a\le n.$$
После подстановки \(a=b+c\) они становятся
$$1\le b\le c-1,\qquad 1\le b\le n-c.$$
Следовательно, при фиксированном \(c\) внутренняя переменная пробегает
$$1\le b\le B(c),\qquad B(c)=\min(c-1,n-c),$$
и вся сумма переписывается как
$$G(n)=\sum_{c=2}^{n-1}\sum_{b=1}^{B(c)}\left(b-\frac{b^2}{c}\right).$$
Обозначим
$$q=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
Если \(2\le c\le q\), то \(c-1\le n-c\), значит \(B(c)=c-1\).
Если \(q\lt c\le n-1\), то \(n-c\lt c\), значит \(B(c)=n-c\).
Поэтому
$$G(n)=\sum_{c=2}^{q}\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)+\sum_{c=q+1}^{n-1}\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right).$$
Первый блок полностью сводится к полиному. Второй блок тоже почти полиномиален, но содержит один гармонический хвост.
Для \(2\le c\le q\) имеем
$$\sum_{b=1}^{c-1} b=\frac{(c-1)c}{2},\qquad \sum_{b=1}^{c-1} b^2=\frac{(c-1)c(2c-1)}{6}.$$
Отсюда внутренняя сумма равна
$$\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)=\frac{(c-1)c}{2}-\frac{(c-1)c(2c-1)}{6c}=\frac{c^2-1}{6}.$$
Суммируя по \(c\), получаем
$$G_{\text{low}}(n)=\sum_{c=2}^{q}\frac{c^2-1}{6}=\frac{q(2q^2+3q-5)}{36}.$$
Именно этот полиномиальный блок используется в реализации первым.
Для \(q\lt c\le n-1\) верхняя граница равна \(n-c\), поэтому
$$\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right)=\frac{(n-c)(n-c+1)}{2}-\frac{(n-c)(n-c+1)(2n-2c+1)}{6c}.$$
Первая часть является полиномом. Если положить \(x=n-c\), то \(x=1,2,\dots,m\), и
$$\sum_{c=n-m}^{n-1}\frac{(n-c)(n-c+1)}{2}=\sum_{x=1}^{m}\frac{x(x+1)}{2}=\frac{m(m+1)(m+2)}{6}.$$
Вторая часть и есть единственный неполиномиальный остаток. Разложим числитель по знаменателю \(c\):
$$\frac{(n-c)(n-c+1)(2n-2c+1)}{c}=\frac{n(n+1)(2n+1)}{c}-(6n^2+6n+1)+(6n+3)c-2c^2.$$
Теперь введем
$$L=n-m,\qquad R=n-1,\qquad H_{L,R}=\sum_{k=L}^{R}\frac{1}{k}.$$
И еще два элементарных суммирования:
$$S_1=\sum_{k=L}^{R}k=\frac{(L+R)m}{2},$$
$$S_2=\sum_{k=L}^{R}k^2=\frac{R(R+1)(2R+1)-(L-1)L(2L-1)}{6}.$$
Тогда рациональный хвост записывается как
$$T(n)=n(n+1)(2n+1)H_{L,R}-(6n^2+6n+1)m+(6n+3)S_1-2S_2.$$
Объединяя малый блок, полиномиальную часть большого блока и рациональный хвост, получаем
$$\boxed{G(n)=\frac{q(2q^2+3q-5)}{36}+\frac{m(m+1)(m+2)}{6}-\frac{T(n)}{6}.}$$
Тем самым задача сведена к вычислению одного гармонического интервала. Если интервал короткий, реализации просто суммируют обратные величины напрямую. Если интервал длинный, используется разложение Эйлера-Маклорена
$$H_t=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}+\frac{1}{240t^8}-\frac{5}{660t^{10}}+O(t^{-12}),$$
после чего берется разность \(H_{L,R}=H_R-H_{L-1}\).
В этом случае
$$q=\left\lfloor\frac{10}{2}\right\rfloor=5,\qquad m=\left\lfloor\frac{9}{2}\right\rfloor=4,\qquad L=6,\qquad R=9.$$
Малый блок дает
$$G_{\text{low}}(10)=\frac{5(2\cdot 5^2+3\cdot 5-5)}{36}=\frac{25}{3}.$$
Полиномиальная часть большого блока равна
$$\frac{4\cdot 5\cdot 6}{6}=20.$$
Гармонический интервал равен
$$H_{6,9}=\frac16+\frac17+\frac18+\frac19=\frac{275}{504}.$$
Кроме того,
$$S_1=6+7+8+9=30,\qquad S_2=6^2+7^2+8^2+9^2=230.$$
Значит,
$$T(10)=10\cdot 11\cdot 21\cdot \frac{275}{504}-661\cdot 4+63\cdot 30-2\cdot 230=\frac{557}{12}.$$
И потому
$$G(10)=\frac{25}{3}+20-\frac{1}{6}\cdot\frac{557}{12}=\frac{1483}{72}=20.597222\ldots,$$
что в точности совпадает с контрольной записью \(2.059722222\times 10^1\).
Реализации на C++, Python и Java вычисляют одну и ту же закрытую формулу. Сначала они находят \(q\), \(m\), \(L\) и \(R\), затем считают два полиномиальных блока и после этого вычисляют гармонический интервал \(H_{L,R}\).
Если гармонический интервал мал, реализация суммирует обратные числа напрямую. Если он велик, вычисляется усеченный ряд Эйлера-Маклорена для \(H_R\) и \(H_{L-1}\), а затем берется разность. В версии на C++ дополнительно оставлена прямая двойная сумма для проверки на малых входах.
На последнем этапе программа формирует \(T(n)\), объединяет три вклада и выводит результат в научной записи: одна цифра до десятичной точки и девять после нее.
Быстрый метод использует \(O(1)\) памяти. Для очень больших входов его время работы практически равно \(O(1)\), потому что единственная неполиномиальная часть заменяется асимптотическим разложением фиксированной длины. Для коротких гармонических интервалов код может выполнить прямое суммирование обратных значений до фиксированного порога, но и этот расход не растет вместе с \(n\). Проверочный путь с явным перебором всех допустимых пар остается \(O(n^2)\) по времени и \(O(1)\) по дополнительной памяти.
الهندسة في المسألة 471 تتحول في النهاية إلى المجموع الحسابي
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor} r(a,b), \qquad r(a,b)=\frac{b(a-2b)}{a-b}.$$
كل زوج مسموح \((a,b)\) يضيف حدًا واحدًا من نوع نصف القطر. وبما أن قيمة \(n\) الحقيقية ضخمة جدًا، فإن الجمع المباشر بحلقتين متداخلتين غير عملي. لذلك تعيد التطبيقات تنظيم المجموع إلى جزأين كثيري حدود بصيغة مغلقة، بالإضافة إلى مجال توافقي واحد.
قيم التحقق الصغيرة المستخدمة في التنفيذ هي \(r(3,1)=1/2\)، و\(r(6,2)=1\)، و\(r(12,3)=2\)، و\(G(10)=2.059722222\times 10^1\)، و\(G(100)=1.922360980\times 10^4\).
نبدأ من الصيغة
$$G(n)=\sum_{a=3}^{n}\sum_{b=1}^{\lfloor (a-1)/2 \rfloor}\frac{b(a-2b)}{a-b}.$$
الفكرة الحاسمة هي ألا نجمع أولًا بحسب \(a\)، بل بحسب المقام \(a-b\).
لنضع
$$c=a-b,$$
وعندئذ يصبح \(a=b+c\). ويتحول الحد المجمع إلى
$$r(a,b)=\frac{b(c-b)}{c}=b-\frac{b^2}{c}.$$
القيود الأصلية هي
$$b\ge 1,\qquad b\le \left\lfloor\frac{a-1}{2}\right\rfloor,\qquad a\le n.$$
وبعد التعويض عن \(a\) بـ \(b+c\) تصبح
$$1\le b\le c-1,\qquad 1\le b\le n-c.$$
إذًا عند تثبيت \(c\) يكون مجال \(b\) هو
$$1\le b\le B(c),\qquad B(c)=\min(c-1,n-c),$$
وبالتالي يعاد كتابة المجموع كله بالشكل
$$G(n)=\sum_{c=2}^{n-1}\sum_{b=1}^{B(c)}\left(b-\frac{b^2}{c}\right).$$
نعرّف
$$q=\left\lfloor\frac{n}{2}\right\rfloor,\qquad m=\left\lfloor\frac{n-1}{2}\right\rfloor.$$
إذا كان \(2\le c\le q\)، فإن \(c-1\le n-c\)، ومن ثم \(B(c)=c-1\).
أما إذا كان \(q\lt c\le n-1\)، فإن \(n-c\lt c\)، ومن ثم \(B(c)=n-c\).
إذن ينقسم المجموع إلى
$$G(n)=\sum_{c=2}^{q}\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)+\sum_{c=q+1}^{n-1}\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right).$$
الجزء الأول يتحول بالكامل إلى كثير حدود، والجزء الثاني يكاد يكون كذلك، لكنه يحتوي على ذيل توافقي واحد.
عندما \(2\le c\le q\) نحصل على
$$\sum_{b=1}^{c-1} b=\frac{(c-1)c}{2},\qquad \sum_{b=1}^{c-1} b^2=\frac{(c-1)c(2c-1)}{6}.$$
ومن ثم فإن المجموع الداخلي يساوي
$$\sum_{b=1}^{c-1}\left(b-\frac{b^2}{c}\right)=\frac{(c-1)c}{2}-\frac{(c-1)c(2c-1)}{6c}=\frac{c^2-1}{6}.$$
وبالجمع على جميع قيم \(c\) نحصل على
$$G_{\text{low}}(n)=\sum_{c=2}^{q}\frac{c^2-1}{6}=\frac{q(2q^2+3q-5)}{36}.$$
وهذا هو أول جزء كثير حدود مغلق تستعمله التطبيقات.
عندما \(q\lt c\le n-1\)، يكون الحد الأعلى هو \(n-c\)، ولذلك
$$\sum_{b=1}^{n-c}\left(b-\frac{b^2}{c}\right)=\frac{(n-c)(n-c+1)}{2}-\frac{(n-c)(n-c+1)(2n-2c+1)}{6c}.$$
الحد الأول كثير حدود خالص. وإذا كتبنا \(x=n-c\)، فإن \(x\) يجري من \(1\) إلى \(m\)، ومن ثم
$$\sum_{c=n-m}^{n-1}\frac{(n-c)(n-c+1)}{2}=\sum_{x=1}^{m}\frac{x(x+1)}{2}=\frac{m(m+1)(m+2)}{6}.$$
أما الحد الثاني فهو الجزء غير كثير الحدود الوحيد. وعند توسيع البسط على المقام \(c\) نحصل على
$$\frac{(n-c)(n-c+1)(2n-2c+1)}{c}=\frac{n(n+1)(2n+1)}{c}-(6n^2+6n+1)+(6n+3)c-2c^2.$$
نعرّف الآن
$$L=n-m,\qquad R=n-1,\qquad H_{L,R}=\sum_{k=L}^{R}\frac{1}{k}.$$
كما نستخدم المجموعين الابتدائيين
$$S_1=\sum_{k=L}^{R}k=\frac{(L+R)m}{2},$$
$$S_2=\sum_{k=L}^{R}k^2=\frac{R(R+1)(2R+1)-(L-1)L(2L-1)}{6}.$$
وعندها يصبح الذيل الكسري كله
$$T(n)=n(n+1)(2n+1)H_{L,R}-(6n^2+6n+1)m+(6n+3)S_1-2S_2.$$
بجمع الجزء السفلي، والجزء كثير الحدود من النصف العلوي، والذيل الكسري، نحصل على
$$\boxed{G(n)=\frac{q(2q^2+3q-5)}{36}+\frac{m(m+1)(m+2)}{6}-\frac{T(n)}{6}.}$$
وهكذا تنحصر صعوبة المسألة كلها في تقييم مجال توافقي واحد. إذا كان المجال قصيرًا تجمع التطبيقات المقلوبات مباشرة. وإذا كان طويلًا فإنها تستعمل توسع Euler-Maclaurin للأعداد التوافقية:
$$H_t=\log t+\gamma+\frac{1}{2t}-\frac{1}{12t^2}+\frac{1}{120t^4}-\frac{1}{252t^6}+\frac{1}{240t^8}-\frac{5}{660t^{10}}+O(t^{-12}),$$
ثم تحسب \(H_{L,R}=H_R-H_{L-1}\).
في هذه الحالة
$$q=\left\lfloor\frac{10}{2}\right\rfloor=5,\qquad m=\left\lfloor\frac{9}{2}\right\rfloor=4,\qquad L=6,\qquad R=9.$$
يعطي الجزء السفلي
$$G_{\text{low}}(10)=\frac{5(2\cdot 5^2+3\cdot 5-5)}{36}=\frac{25}{3}.$$
أما الجزء كثير الحدود من النصف العلوي فيساوي
$$\frac{4\cdot 5\cdot 6}{6}=20.$$
والمجال التوافقي هو
$$H_{6,9}=\frac16+\frac17+\frac18+\frac19=\frac{275}{504}.$$
وكذلك
$$S_1=6+7+8+9=30,\qquad S_2=6^2+7^2+8^2+9^2=230.$$
إذًا
$$T(10)=10\cdot 11\cdot 21\cdot \frac{275}{504}-661\cdot 4+63\cdot 30-2\cdot 230=\frac{557}{12}.$$
ومن ثم
$$G(10)=\frac{25}{3}+20-\frac{1}{6}\cdot\frac{557}{12}=\frac{1483}{72}=20.597222\ldots,$$
وهو بالضبط نفس تحقق البرنامج \(2.059722222\times 10^1\).
تنفذ برامج C++ وPython وJava الصيغة المغلقة نفسها. فهي تحسب أولًا \(q\) و\(m\) و\(L\) و\(R\)، ثم تحسب الجزأين كثيري الحدود، وبعد ذلك تقيّم المجال التوافقي \(H_{L,R}\).
إذا كان المجال التوافقي صغيرًا، يجمع التنفيذ المقلوبات مباشرة. وإذا كان كبيرًا، فإنه يقيّم متسلسلة Euler-Maclaurin المقطوعة لكل من \(H_R\) و\(H_{L-1}\) ثم يأخذ الفرق. كما يحتفظ تنفيذ C++ بمسار جمع مباشر بحلقتين من أجل التحقق على المدخلات الصغيرة.
في النهاية يُبنى المقدار \(T(n)\)، وتُدمج المساهمات الثلاث، ثم يُطبع الناتج بصيغة علمية فيها رقم واحد قبل الفاصلة وتسعة أرقام بعدها.
تستخدم الطريقة السريعة ذاكرة \(O(1)\). وبالنسبة إلى القيم الكبيرة جدًا، يكون الزمن عمليًا \(O(1)\)، لأن الجزء الوحيد غير كثير الحدود يستبدل بتوسع تقاربي ذي طول ثابت. وعند المجالات التوافقية القصيرة قد يجري التنفيذ جمعًا مباشرًا للمقلوبات حتى حد ثابت، لكن هذه الكلفة أيضًا لا تنمو مع \(n\). أما مسار التحقق الذي يعدد كل الأزواج المسموح بها صراحة فيبقى \(O(n^2)\) زمنًا و\(O(1)\) ذاكرة إضافية.