The arithmetic reduction used by the implementation rewrites the polygonal-number question as a sum over odd shape parameters \(k\ge 3\). For each odd \(k\), define
$$\delta=k-2,\qquad \gamma=(k-4)^2.$$
Every admissible configuration is then indexed by an integer \(t\ge 1\) and contributes two nonnegative quantities
$$X_{k,t}=(2\delta t+1)^2,\qquad Y_{k,t}=\frac{\gamma}{2}\left(\delta t^2+t\right).$$
A pair \((k,t)\) is valid only when both \(X_{k,t}\le N\) and \(Y_{k,t}\le N\). The total quantity to compute is therefore
$$S(N)=\sum_{\substack{k\ge 3\\ k\equiv 1 \!\!\!\pmod 2}}\ \sum_{\substack{t\ge 1\\ X_{k,t}\le N,\ Y_{k,t}\le N}}\left(X_{k,t}+Y_{k,t}\right).$$
The challenge is that \(N\) is enormous, so the useful task is to collapse the inner summation to a closed form and to stop the outer loop as soon as no larger odd \(k\) can contribute.
For fixed odd \(k\), let \(C_k(N)\) be the total contribution of that single value of \(k\). The derivation below matches exactly the arithmetic carried out by the implementations.
Once \(k\) is fixed, the only free parameter is \(t\ge 1\). Because \(\delta=k-2>0\) and \(\gamma=(k-4)^2>0\), the sequences \(X_{k,t}\) and \(Y_{k,t}\) both grow with \(t\).
Also, \(k\) is odd, so \(\delta\) is odd. Hence
$$\delta t^2+t=t(\delta t+1)$$
is always even: if \(t\) is odd then \(\delta t\) is odd and \(\delta t+1\) is even, while if \(t\) is even then the factor \(t\) itself is even. Therefore \(Y_{k,t}\) is always an integer.
Since both expressions increase with \(t\), the feasible values form an initial interval
$$1\le t\le T_k(N),$$
and the contribution for this \(k\) is
$$C_k(N)=\sum_{t=1}^{T_k(N)}\left(X_{k,t}+Y_{k,t}\right).$$
Let
$$R=\left\lfloor\sqrt{N}\right\rfloor.$$
The inequality \(X_{k,t}\le N\) becomes
$$\left(2\delta t+1\right)^2\le N.$$
All quantities are nonnegative, so this is equivalent to
$$2\delta t+1\le R,$$
which yields the exact upper bound
$$T_A(k,N)=\left\lfloor\frac{R-1}{2\delta}\right\rfloor.$$
Now use the second feasibility condition \(Y_{k,t}\le N\):
$$\frac{\gamma}{2}\left(\delta t^2+t\right)\le N.$$
Since \(\gamma>0\), divide by \(\gamma\) and define
$$M=\left\lfloor\frac{2N}{\gamma}\right\rfloor.$$
Then \(t\) must satisfy
$$\delta t^2+t\le M.$$
This is a quadratic inequality. Solving \(\delta t^2+t-M=0\) gives the positive root
$$\frac{-1+\sqrt{1+4\delta M}}{2\delta}.$$
Therefore the exact integer bound is
$$T_B(k,N)=\left\lfloor\frac{\left\lfloor\sqrt{1+4\delta M}\right\rfloor-1}{2\delta}\right\rfloor.$$
The actual usable range is the intersection of the two bounds:
$$T_k(N)=\min\!\bigl(T_A(k,N),T_B(k,N)\bigr).$$
Let \(T=T_k(N)\). Introduce the standard sums
$$S_1(T)=\sum_{t=1}^{T} t=\frac{T(T+1)}{2},\qquad S_2(T)=\sum_{t=1}^{T} t^2=\frac{T(T+1)(2T+1)}{6}.$$
Expanding \(X_{k,t}\) gives
$$X_{k,t}=4\delta^2 t^2+4\delta t+1,$$
hence
$$\sum_{t=1}^{T} X_{k,t}=4\delta^2S_2(T)+4\delta S_1(T)+T.$$
For the second term,
$$\sum_{t=1}^{T} Y_{k,t}=\frac{\gamma}{2}\sum_{t=1}^{T}\left(\delta t^2+t\right)=\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).$$
So the whole contribution of one odd \(k\) is
$$\boxed{C_k(N)=T+4\delta S_1(T)+4\delta^2S_2(T)+\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).}$$
This is the key optimization: after computing \(T_k(N)\), the contribution of that \(k\) is obtained in constant time.
The smallest admissible parameter is always \(t=1\). Therefore a necessary condition for any contribution from a given odd \(k\) is
$$X_{k,1}=(2k-3)^2\le N,\qquad Y_{k,1}=\frac{(k-4)^2(k-1)}{2}\le N.$$
If either inequality already fails at \(t=1\), then no larger \(t\) can work, because both \(X_{k,t}\) and \(Y_{k,t}\) increase with \(t\).
Moreover, both \(X_{k,1}\) and \(Y_{k,1}\) increase as odd \(k\) increases. So once one odd \(k\) fails this test, every larger odd \(k\) fails as well. That is why the outer loop can terminate immediately instead of checking all remaining values.
This small case is large enough to show every ingredient of the method but still easy to check by hand.
For \(k=3\), we have \(\delta=1\) and \(\gamma=1\). Since \(\lfloor\sqrt{100}\rfloor=10\),
$$T_A(3,100)=\left\lfloor\frac{10-1}{2}\right\rfloor=4.$$
Also
$$M=\left\lfloor\frac{2\cdot 100}{1}\right\rfloor=200,\qquad 1+4\delta M=801,\qquad \left\lfloor\sqrt{801}\right\rfloor=28,$$
so
$$T_B(3,100)=\left\lfloor\frac{28-1}{2}\right\rfloor=13.$$
Thus \(T_3(100)=4\). With \(S_1(4)=10\) and \(S_2(4)=30\),
$$C_3(100)=4+4\cdot 10+4\cdot 30+\frac{1}{2}(30+10)=164+20=184.$$
For \(k=5\), we have \(\delta=3\) and \(\gamma=1\). Then
$$T_A(5,100)=\left\lfloor\frac{10-1}{6}\right\rfloor=1,$$
and
$$1+4\delta M=1+4\cdot 3\cdot 200=2401,\qquad \left\lfloor\sqrt{2401}\right\rfloor=49,$$
so
$$T_B(5,100)=\left\lfloor\frac{49-1}{6}\right\rfloor=8.$$
Hence \(T_5(100)=1\), and the contribution is simply
$$C_5(100)=(2\cdot 3\cdot 1+1)^2+\frac{1}{2}(3\cdot 1^2+1)=49+2=51.$$
For \(k=7\), the very first square term already fails:
$$X_{7,1}=(2\cdot 7-3)^2=11^2=121>100.$$
So no larger odd \(k\) can contribute, and the final total is
$$S(100)=184+51=235.$$
The C++, Python, and Java implementations all follow the same plan. They iterate only over odd \(k\ge 3\), compute the two exact bounds \(T_A\) and \(T_B\) using integer square roots, and keep the minimum as the last admissible \(t\).
If that minimum is \(0\), the current odd \(k\) contributes nothing. Otherwise the implementation evaluates \(S_1(T)\) and \(S_2(T)\), substitutes them into the closed-form expressions above, and adds the result to the running total.
No implementation performs a full inner loop over \(t\). The only loop that remains is the outer loop over odd \(k\), and it stops as soon as the \(t=1\) test proves that the current \(k\) and all larger odd \(k\) are impossible.
Each admissible odd \(k\) is processed in \(O(1)\) arithmetic time after a constant number of integer-square-root evaluations, and the memory usage is \(O(1)\).
Let \(K_{\max}\) be the largest odd \(k\) that can pass the \(t=1\) test. Since
$$Y_{k,1}=\frac{(k-4)^2(k-1)}{2}=\Theta(k^3),$$
we have \(K_{\max}=O(N^{1/3})\). The bound coming from \(X_{k,1}=(2k-3)^2\) is only \(O(\sqrt{N})\), so the cubic term is the one that controls the asymptotic stopping point. Therefore the full running time is
$$O(N^{1/3}),$$
with constant extra memory.
Die arithmetische Reduktion hinter der Lösung schreibt die ursprüngliche Frage zu Polygonalzahlen als Summe über ungerade Formparameter \(k\ge 3\) um. Für jedes ungerade \(k\) setzen wir
$$\delta=k-2,\qquad \gamma=(k-4)^2.$$
Jede zulässige Konfiguration wird dann durch eine ganze Zahl \(t\ge 1\) parametrisiert und liefert zwei nichtnegative Beiträge
$$X_{k,t}=(2\delta t+1)^2,\qquad Y_{k,t}=\frac{\gamma}{2}\left(\delta t^2+t\right).$$
Ein Paar \((k,t)\) ist nur dann gültig, wenn gleichzeitig \(X_{k,t}\le N\) und \(Y_{k,t}\le N\) gilt. Die gesuchte Gesamtgröße ist also
$$S(N)=\sum_{\substack{k\ge 3\\ k\equiv 1 \!\!\!\pmod 2}}\ \sum_{\substack{t\ge 1\\ X_{k,t}\le N,\ Y_{k,t}\le N}}\left(X_{k,t}+Y_{k,t}\right).$$
Die eigentliche Aufgabe besteht darin, diese Summe für sehr große \(N\) effizient auszuwerten, also die innere Summe in geschlossene Formeln zu überführen und die äußere Schleife früh abzubrechen.
Für festes ungerades \(k\) bezeichne \(C_k(N)\) den Beitrag genau dieses einen Werts. Die folgende Herleitung entspricht Schritt für Schritt der verwendeten Rechnung.
Ist \(k\) fest, dann bleibt nur noch \(t\ge 1\) als freier Parameter. Da \(\delta=k-2>0\) und \(\gamma=(k-4)^2>0\) sind, wachsen sowohl \(X_{k,t}\) als auch \(Y_{k,t}\) streng mit \(t\).
Außerdem ist \(\delta\) wegen des ungeraden \(k\) selbst ungerade. Damit ist
$$\delta t^2+t=t(\delta t+1)$$
immer gerade: Ist \(t\) ungerade, dann ist \(\delta t\) ungerade und \(\delta t+1\) gerade; ist \(t\) gerade, dann ist bereits der Faktor \(t\) gerade. Also ist \(Y_{k,t}\) trotz des Faktors \(1/2\) stets ganzzahlig.
Wegen der Monotonie bilden die zulässigen \(t\)-Werte ein Anfangsintervall
$$1\le t\le T_k(N),$$
und der Beitrag dieses \(k\) lautet
$$C_k(N)=\sum_{t=1}^{T_k(N)}\left(X_{k,t}+Y_{k,t}\right).$$
Setze
$$R=\left\lfloor\sqrt{N}\right\rfloor.$$
Die Bedingung \(X_{k,t}\le N\) wird zu
$$\left(2\delta t+1\right)^2\le N.$$
Da alle Größen nichtnegativ sind, ist das äquivalent zu
$$2\delta t+1\le R,$$
also erhält man die exakte obere Grenze
$$T_A(k,N)=\left\lfloor\frac{R-1}{2\delta}\right\rfloor.$$
Nun betrachten wir die zweite Zulässigkeitsbedingung:
$$\frac{\gamma}{2}\left(\delta t^2+t\right)\le N.$$
Weil \(\gamma>0\) ist, teilen wir durch \(\gamma\) und definieren
$$M=\left\lfloor\frac{2N}{\gamma}\right\rfloor.$$
Dann muss
$$\delta t^2+t\le M$$
gelten. Das ist eine quadratische Ungleichung. Die positive Nullstelle von \(\delta t^2+t-M=0\) ist
$$\frac{-1+\sqrt{1+4\delta M}}{2\delta}.$$
Daraus folgt die exakte ganzzahlige Schranke
$$T_B(k,N)=\left\lfloor\frac{\left\lfloor\sqrt{1+4\delta M}\right\rfloor-1}{2\delta}\right\rfloor.$$
Die tatsächliche Reichweite ist also
$$T_k(N)=\min\!\bigl(T_A(k,N),T_B(k,N)\bigr).$$
Sei \(T=T_k(N)\). Dann verwenden wir die Standardsummen
$$S_1(T)=\sum_{t=1}^{T} t=\frac{T(T+1)}{2},\qquad S_2(T)=\sum_{t=1}^{T} t^2=\frac{T(T+1)(2T+1)}{6}.$$
Aus
$$X_{k,t}=4\delta^2 t^2+4\delta t+1$$
folgt
$$\sum_{t=1}^{T} X_{k,t}=4\delta^2S_2(T)+4\delta S_1(T)+T.$$
Für den zweiten Teil erhalten wir
$$\sum_{t=1}^{T} Y_{k,t}=\frac{\gamma}{2}\sum_{t=1}^{T}\left(\delta t^2+t\right)=\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).$$
Damit ist der Gesamtbeitrag eines einzelnen ungeraden \(k\)
$$\boxed{C_k(N)=T+4\delta S_1(T)+4\delta^2S_2(T)+\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).}$$
Genau hier steckt die Beschleunigung: Ist \(T_k(N)\) bekannt, kostet der gesamte Beitrag dieses \(k\) nur noch konstante Zeit.
Der kleinste mögliche Parameter ist immer \(t=1\). Also ist eine notwendige Bedingung für einen nichtverschwindenden Beitrag
$$X_{k,1}=(2k-3)^2\le N,\qquad Y_{k,1}=\frac{(k-4)^2(k-1)}{2}\le N.$$
Falls schon bei \(t=1\) eine dieser Ungleichungen verletzt ist, kann kein größeres \(t\) mehr funktionieren, weil beide Folgen mit \(t\) anwachsen.
Außerdem wachsen auch \(X_{k,1}\) und \(Y_{k,1}\) mit zunehmendem ungeradem \(k\). Sobald also ein ungerades \(k\) an dieser Stelle scheitert, scheitern alle größeren ungeraden \(k\) ebenfalls. Deshalb darf die äußere Schleife sofort abbrechen.
Dieser kleine Fall zeigt alle Bausteine der Methode und lässt sich trotzdem vollständig von Hand nachvollziehen.
Für \(k=3\) gilt \(\delta=1\) und \(\gamma=1\). Da \(\lfloor\sqrt{100}\rfloor=10\), ist
$$T_A(3,100)=\left\lfloor\frac{10-1}{2}\right\rfloor=4.$$
Außerdem
$$M=\left\lfloor\frac{2\cdot 100}{1}\right\rfloor=200,\qquad 1+4\delta M=801,\qquad \left\lfloor\sqrt{801}\right\rfloor=28,$$
also
$$T_B(3,100)=\left\lfloor\frac{28-1}{2}\right\rfloor=13.$$
Damit ist \(T_3(100)=4\). Mit \(S_1(4)=10\) und \(S_2(4)=30\) erhält man
$$C_3(100)=4+4\cdot 10+4\cdot 30+\frac{1}{2}(30+10)=164+20=184.$$
Für \(k=5\) gilt \(\delta=3\) und \(\gamma=1\). Dann ist
$$T_A(5,100)=\left\lfloor\frac{10-1}{6}\right\rfloor=1,$$
und
$$1+4\delta M=1+4\cdot 3\cdot 200=2401,\qquad \left\lfloor\sqrt{2401}\right\rfloor=49,$$
sodass
$$T_B(5,100)=\left\lfloor\frac{49-1}{6}\right\rfloor=8.$$
Also ist \(T_5(100)=1\), und der Beitrag lautet
$$C_5(100)=(2\cdot 3\cdot 1+1)^2+\frac{1}{2}(3\cdot 1^2+1)=49+2=51.$$
Für \(k=7\) scheitert bereits der erste Quadratterm:
$$X_{7,1}=(2\cdot 7-3)^2=11^2=121>100.$$
Also kann kein größeres ungerades \(k\) mehr beitragen, und insgesamt ergibt sich
$$S(100)=184+51=235.$$
Die C++-, Python- und Java-Implementierungen verwenden denselben Rechenweg. Sie iterieren nur über ungerade \(k\ge 3\), bestimmen per ganzzahliger Quadratwurzel die beiden exakten Schranken \(T_A\) und \(T_B\) und nehmen davon das Minimum als letzten zulässigen Wert von \(t\).
Ist dieses Minimum gleich \(0\), liefert das aktuelle ungerade \(k\) keinen Beitrag. Andernfalls werden \(S_1(T)\) und \(S_2(T)\) ausgewertet, in die geschlossenen Formeln eingesetzt und zum laufenden Ergebnis addiert.
Keine der Implementierungen läuft die inneren \(t\)-Werte einzeln ab. Die einzige echte Schleife bleibt die äußere Schleife über ungerade \(k\), und auch diese endet sofort, sobald der Test mit \(t=1\) zeigt, dass das aktuelle \(k\) und alle größeren ungeraden \(k\) unmöglich sind.
Jedes zulässige ungerade \(k\) wird nach einer konstanten Anzahl ganzzahliger Quadratwurzelberechnungen in \(O(1)\) Zeit verarbeitet, und der Speicherverbrauch bleibt \(O(1)\).
Sei \(K_{\max}\) das größte ungerade \(k\), das den Test bei \(t=1\) noch bestehen kann. Wegen
$$Y_{k,1}=\frac{(k-4)^2(k-1)}{2}=\Theta(k^3)$$
gilt \(K_{\max}=O(N^{1/3})\). Die Schranke aus \(X_{k,1}=(2k-3)^2\) liefert nur \(O(\sqrt{N})\), also bestimmt der kubische Term den asymptotischen Abbruchpunkt. Damit beträgt die Gesamtlaufzeit
$$O(N^{1/3}),$$
bei konstantem Zusatzspeicher.
Çözümde kullanılan aritmetik indirgeme, çokgensel sayılarla ilgili özgün soruyu tek tek tekil şekil parametreleri \(k\ge 3\) üzerinden yazılan bir toplama dönüştürür. Her tek \(k\) için
$$\delta=k-2,\qquad \gamma=(k-4)^2$$
tanımlanır. Her uygun konfigürasyon daha sonra \(t\ge 1\) olan bir tamsayı ile parametrik hale gelir ve iki adet negatif olmayan katkı üretir:
$$X_{k,t}=(2\delta t+1)^2,\qquad Y_{k,t}=\frac{\gamma}{2}\left(\delta t^2+t\right).$$
Bir \((k,t)\) çifti ancak hem \(X_{k,t}\le N\) hem de \(Y_{k,t}\le N\) ise geçerlidir. Dolayısıyla hesaplanacak toplam
$$S(N)=\sum_{\substack{k\ge 3\\ k\equiv 1 \!\!\!\pmod 2}}\ \sum_{\substack{t\ge 1\\ X_{k,t}\le N,\ Y_{k,t}\le N}}\left(X_{k,t}+Y_{k,t}\right).$$
olur. Asıl amaç, \(N\) çok büyükken bu toplamı hızlı hesaplamak, yani iç toplamı kapalı formüllere indirip dış döngüyü mümkün olan en erken noktada kesmektir.
Sabit bir tek \(k\) için, sadece o \(k\)'nin toplam katkısını \(C_k(N)\) ile gösterelim. Aşağıdaki türetim, üç uygulamanın yaptığı hesabın birebir matematiksel karşılığıdır.
\(k\) sabitlendiğinde geriye yalnızca \(t\ge 1\) serbest parametresi kalır. \(\delta=k-2>0\) ve \(\gamma=(k-4)^2>0\) olduğundan, hem \(X_{k,t}\) hem de \(Y_{k,t}\) ifadeleri \(t\) arttıkça büyür.
Ayrıca \(k\) tek olduğu için \(\delta\) da tektir. Bu nedenle
$$\delta t^2+t=t(\delta t+1)$$
her zaman çifttir: \(t\) tekse \(\delta t\) tek, dolayısıyla \(\delta t+1\) çifttir; \(t\) çiftse zaten \(t\) çifttir. Böylece \(Y_{k,t}\), önündeki \(1/2\) katsayısına rağmen daima tam sayıdır.
Monotonluk yüzünden uygun \(t\) değerleri bir başlangıç aralığı oluşturur:
$$1\le t\le T_k(N).$$
Buna göre sabit \(k\) için toplam katkı
$$C_k(N)=\sum_{t=1}^{T_k(N)}\left(X_{k,t}+Y_{k,t}\right)$$
şeklindedir.
Önce
$$R=\left\lfloor\sqrt{N}\right\rfloor$$
tanımını yapalım. \(X_{k,t}\le N\) koşulu
$$\left(2\delta t+1\right)^2\le N$$
eşitsizliğine eşdeğerdir. Tüm terimler negatif olmadığından bu da
$$2\delta t+1\le R$$
demektir. Böylece ilk kesin sınır
$$T_A(k,N)=\left\lfloor\frac{R-1}{2\delta}\right\rfloor$$
olarak elde edilir.
Şimdi ikinci uygunluk koşulunu kullanalım:
$$\frac{\gamma}{2}\left(\delta t^2+t\right)\le N.$$
\(\gamma>0\) olduğundan bölüp
$$M=\left\lfloor\frac{2N}{\gamma}\right\rfloor$$
tanımını yapabiliriz. O zaman \(t\) için gerekli eşitsizlik
$$\delta t^2+t\le M$$
olur. Bu bir ikinci derece eşitsizliktir. \(\delta t^2+t-M=0\) denkleminin pozitif kökü
$$\frac{-1+\sqrt{1+4\delta M}}{2\delta}$$
olduğundan, tam sayı üst sınırı
$$T_B(k,N)=\left\lfloor\frac{\left\lfloor\sqrt{1+4\delta M}\right\rfloor-1}{2\delta}\right\rfloor$$
şeklini alır. Gerçek kullanılabilir aralık ise iki sınırın kesişimidir:
$$T_k(N)=\min\!\bigl(T_A(k,N),T_B(k,N)\bigr).$$
\(T=T_k(N)\) olsun. Standart toplamları
$$S_1(T)=\sum_{t=1}^{T} t=\frac{T(T+1)}{2},\qquad S_2(T)=\sum_{t=1}^{T} t^2=\frac{T(T+1)(2T+1)}{6}$$
olarak tanımlayalım. Önce
$$X_{k,t}=4\delta^2 t^2+4\delta t+1$$
olduğundan
$$\sum_{t=1}^{T} X_{k,t}=4\delta^2S_2(T)+4\delta S_1(T)+T$$
elde edilir. İkinci kısım için de
$$\sum_{t=1}^{T} Y_{k,t}=\frac{\gamma}{2}\sum_{t=1}^{T}\left(\delta t^2+t\right)=\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right)$$
yazılır. Sonuç olarak tek bir tek \(k\)'nin toplam katkısı
$$\boxed{C_k(N)=T+4\delta S_1(T)+4\delta^2S_2(T)+\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right)}$$
olur. Ana hızlanma tam burada gelir: \(T_k(N)\) bulunduktan sonra o \(k\) için iç döngüyü hiç dolaşmadan sabit zamanda sonuç alınır.
Her zaman en küçük aday \(t=1\) olduğuna göre, sabit bir tek \(k\)'nin katkı vermesi için gerekli koşul
$$X_{k,1}=(2k-3)^2\le N,\qquad Y_{k,1}=\frac{(k-4)^2(k-1)}{2}\le N$$
olmalıdır. Eğer bu iki koşuldan biri daha \(t=1\)'de bozuluyorsa, daha büyük hiçbir \(t\) çalışamaz; çünkü her iki ifade de \(t\) ile birlikte artar.
Dahası, \(X_{k,1}\) ve \(Y_{k,1}\) değerleri de tek \(k\) büyüdükçe artar. Bu yüzden bir tek \(k\) için test bozulduğu anda, daha büyük tüm tek \(k\) değerleri de otomatik olarak elenir. Dış döngünün kesme kuralı tam olarak buna dayanır.
Bu küçük örnek, yöntemin bütün parçalarını gösterir ve elle kontrol edilebilecek kadar da sadedir.
\(k=3\) için \(\delta=1\) ve \(\gamma=1\) olur. \(\lfloor\sqrt{100}\rfloor=10\) olduğundan
$$T_A(3,100)=\left\lfloor\frac{10-1}{2}\right\rfloor=4.$$
Ayrıca
$$M=\left\lfloor\frac{2\cdot 100}{1}\right\rfloor=200,\qquad 1+4\delta M=801,\qquad \left\lfloor\sqrt{801}\right\rfloor=28,$$
dolayısıyla
$$T_B(3,100)=\left\lfloor\frac{28-1}{2}\right\rfloor=13.$$
Böylece \(T_3(100)=4\). \(S_1(4)=10\) ve \(S_2(4)=30\) ile
$$C_3(100)=4+4\cdot 10+4\cdot 30+\frac{1}{2}(30+10)=164+20=184$$
bulunur.
\(k=5\) için \(\delta=3\) ve \(\gamma=1\) olur. Bu kez
$$T_A(5,100)=\left\lfloor\frac{10-1}{6}\right\rfloor=1,$$
ve
$$1+4\delta M=1+4\cdot 3\cdot 200=2401,\qquad \left\lfloor\sqrt{2401}\right\rfloor=49,$$
yani
$$T_B(5,100)=\left\lfloor\frac{49-1}{6}\right\rfloor=8.$$
Dolayısıyla \(T_5(100)=1\) ve katkı doğrudan
$$C_5(100)=(2\cdot 3\cdot 1+1)^2+\frac{1}{2}(3\cdot 1^2+1)=49+2=51$$
çıkar.
\(k=7\) için ise ilk kare terimi daha baştan sınırı aşar:
$$X_{7,1}=(2\cdot 7-3)^2=11^2=121>100.$$
Bu nedenle daha büyük tek \(k\) değerlerine geçmeye gerek yoktur ve toplam sonuç
$$S(100)=184+51=235$$
olur.
C++, Python ve Java uygulamalarının üçü de aynı planı izler. Sadece tek \(k\ge 3\) değerleri dolaşılır, iki uygunluk sınırı \(T_A\) ve \(T_B\) tam sayı karekökleriyle hesaplanır ve bunların küçüğü son geçerli \(t\) olarak alınır.
Bu minimum \(0\) ise mevcut tek \(k\) katkı vermez. Aksi halde \(S_1(T)\) ve \(S_2(T)\) hesaplanır, yukarıdaki kapalı formüllere yerleştirilir ve sonuç birikimli toplama eklenir.
Uygulama hiçbir zaman tüm \(t\) değerlerini tek tek gezmez. Geriye sadece tek \(k\) üzerinde dış döngü kalır; o da \(t=1\) testi, mevcut \(k\) ve ondan büyük tüm tek değerlerin imkansız olduğunu gösterdiği anda biter.
Geçerli olabilecek her tek \(k\), sabit sayıda tam sayı karekökü ve aritmetik işlemle \(O(1)\) zamanda işlenir. Bellek kullanımı da \(O(1)\) düzeyindedir.
\(t=1\) testini geçebilen en büyük tek \(k\) değerine \(K_{\max}\) diyelim. Şu ifade
$$Y_{k,1}=\frac{(k-4)^2(k-1)}{2}=\Theta(k^3)$$
olduğundan \(K_{\max}=O(N^{1/3})\) elde edilir. \(X_{k,1}=(2k-3)^2\) koşulu yalnızca \(O(\sqrt{N})\) verir; asimptotik kesme noktasını belirleyen terim kübik olan ikinci koşuldur. Bu nedenle toplam süre
$$O(N^{1/3})$$
ve ek bellek gereksinimi sabittir.
La reducción aritmética utilizada por la solución reescribe la pregunta original sobre números poligonales como una suma sobre parámetros impares \(k\ge 3\). Para cada \(k\) impar se define
$$\delta=k-2,\qquad \gamma=(k-4)^2.$$
Cada configuración válida queda entonces indexada por un entero \(t\ge 1\) y produce dos cantidades no negativas:
$$X_{k,t}=(2\delta t+1)^2,\qquad Y_{k,t}=\frac{\gamma}{2}\left(\delta t^2+t\right).$$
Un par \((k,t)\) solo cuenta cuando se cumplen simultáneamente \(X_{k,t}\le N\) y \(Y_{k,t}\le N\). Por tanto, la magnitud total que se debe calcular es
$$S(N)=\sum_{\substack{k\ge 3\\ k\equiv 1 \!\!\!\pmod 2}}\ \sum_{\substack{t\ge 1\\ X_{k,t}\le N,\ Y_{k,t}\le N}}\left(X_{k,t}+Y_{k,t}\right).$$
El objetivo real es evaluar esta suma para valores enormes de \(N\), así que la clave está en eliminar el bucle interno sobre \(t\) y en detener el bucle externo tan pronto como ningún \(k\) impar mayor pueda aportar nada.
Para un \(k\) impar fijo, llamemos \(C_k(N)\) a la contribución total de ese único valor. La derivación siguiente coincide exactamente con la aritmética que usan las implementaciones.
Una vez fijado \(k\), el único parámetro libre es \(t\ge 1\). Como \(\delta=k-2>0\) y \(\gamma=(k-4)^2>0\), tanto \(X_{k,t}\) como \(Y_{k,t}\) crecen con \(t\).
Además, si \(k\) es impar entonces \(\delta\) también es impar. Por eso
$$\delta t^2+t=t(\delta t+1)$$
siempre es par: si \(t\) es impar, \(\delta t\) es impar y \(\delta t+1\) es par; si \(t\) es par, el propio factor \(t\) ya es par. En consecuencia, \(Y_{k,t}\) es entero a pesar del factor \(1/2\).
Como ambas expresiones son monótonas, los valores factibles de \(t\) forman un intervalo inicial
$$1\le t\le T_k(N),$$
y la aportación de ese \(k\) es
$$C_k(N)=\sum_{t=1}^{T_k(N)}\left(X_{k,t}+Y_{k,t}\right).$$
Sea
$$R=\left\lfloor\sqrt{N}\right\rfloor.$$
La desigualdad \(X_{k,t}\le N\) equivale a
$$\left(2\delta t+1\right)^2\le N.$$
Como todas las cantidades son no negativas, esto es lo mismo que exigir
$$2\delta t+1\le R,$$
de donde sale la cota exacta
$$T_A(k,N)=\left\lfloor\frac{R-1}{2\delta}\right\rfloor.$$
Ahora usamos la segunda condición de factibilidad:
$$\frac{\gamma}{2}\left(\delta t^2+t\right)\le N.$$
Como \(\gamma>0\), dividimos por \(\gamma\) y definimos
$$M=\left\lfloor\frac{2N}{\gamma}\right\rfloor.$$
Entonces \(t\) debe satisfacer
$$\delta t^2+t\le M.$$
Esta es una desigualdad cuadrática. La raíz positiva de \(\delta t^2+t-M=0\) es
$$\frac{-1+\sqrt{1+4\delta M}}{2\delta}.$$
Por tanto, la cota entera exacta es
$$T_B(k,N)=\left\lfloor\frac{\left\lfloor\sqrt{1+4\delta M}\right\rfloor-1}{2\delta}\right\rfloor.$$
El rango realmente utilizable es la intersección de ambas restricciones:
$$T_k(N)=\min\!\bigl(T_A(k,N),T_B(k,N)\bigr).$$
Sea \(T=T_k(N)\). Introducimos las sumas estándar
$$S_1(T)=\sum_{t=1}^{T} t=\frac{T(T+1)}{2},\qquad S_2(T)=\sum_{t=1}^{T} t^2=\frac{T(T+1)(2T+1)}{6}.$$
Al expandir \(X_{k,t}\) obtenemos
$$X_{k,t}=4\delta^2 t^2+4\delta t+1,$$
y por ello
$$\sum_{t=1}^{T} X_{k,t}=4\delta^2S_2(T)+4\delta S_1(T)+T.$$
Para la segunda parte,
$$\sum_{t=1}^{T} Y_{k,t}=\frac{\gamma}{2}\sum_{t=1}^{T}\left(\delta t^2+t\right)=\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).$$
Así, la contribución total de un único \(k\) impar queda
$$\boxed{C_k(N)=T+4\delta S_1(T)+4\delta^2S_2(T)+\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).}$$
Esta es la optimización decisiva: una vez calculado \(T_k(N)\), el aporte de ese \(k\) se obtiene en tiempo constante.
El menor parámetro posible siempre es \(t=1\). Por eso, una condición necesaria para que un \(k\) impar contribuya es
$$X_{k,1}=(2k-3)^2\le N,\qquad Y_{k,1}=\frac{(k-4)^2(k-1)}{2}\le N.$$
Si una de esas desigualdades ya falla cuando \(t=1\), ningún valor mayor de \(t\) puede funcionar, porque tanto \(X_{k,t}\) como \(Y_{k,t}\) crecen con \(t\).
Además, \(X_{k,1}\) y \(Y_{k,1}\) también crecen cuando aumenta \(k\) dentro de los impares. Por ello, una vez que un \(k\) impar falla en \(t=1\), todos los impares posteriores fallan también. Esa es la razón matemática por la que el recorrido exterior puede detenerse de inmediato.
Este caso pequeño contiene todos los ingredientes del método y todavía permite comprobar las cuentas manualmente.
Para \(k=3\), tenemos \(\delta=1\) y \(\gamma=1\). Como \(\lfloor\sqrt{100}\rfloor=10\),
$$T_A(3,100)=\left\lfloor\frac{10-1}{2}\right\rfloor=4.$$
Además,
$$M=\left\lfloor\frac{2\cdot 100}{1}\right\rfloor=200,\qquad 1+4\delta M=801,\qquad \left\lfloor\sqrt{801}\right\rfloor=28,$$
de modo que
$$T_B(3,100)=\left\lfloor\frac{28-1}{2}\right\rfloor=13.$$
Por lo tanto, \(T_3(100)=4\). Con \(S_1(4)=10\) y \(S_2(4)=30\),
$$C_3(100)=4+4\cdot 10+4\cdot 30+\frac{1}{2}(30+10)=164+20=184.$$
Para \(k=5\), \(\delta=3\) y \(\gamma=1\). Entonces
$$T_A(5,100)=\left\lfloor\frac{10-1}{6}\right\rfloor=1,$$
y
$$1+4\delta M=1+4\cdot 3\cdot 200=2401,\qquad \left\lfloor\sqrt{2401}\right\rfloor=49,$$
así que
$$T_B(5,100)=\left\lfloor\frac{49-1}{6}\right\rfloor=8.$$
Luego \(T_5(100)=1\), y la contribución se reduce a
$$C_5(100)=(2\cdot 3\cdot 1+1)^2+\frac{1}{2}(3\cdot 1^2+1)=49+2=51.$$
Para \(k=7\), el primer término cuadrático ya supera el límite:
$$X_{7,1}=(2\cdot 7-3)^2=11^2=121>100.$$
Así, ningún impar mayor puede contribuir y el total final es
$$S(100)=184+51=235.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Recorren solo los valores impares \(k\ge 3\), calculan las dos cotas exactas \(T_A\) y \(T_B\) mediante raíces cuadradas enteras y toman su mínimo como último \(t\) admisible.
Si ese mínimo es \(0\), el \(k\) actual no aporta nada. En caso contrario, la implementación evalúa \(S_1(T)\) y \(S_2(T)\), sustituye en las fórmulas cerradas anteriores y suma el resultado al acumulado global.
No se recorre explícitamente el rango de \(t\). El único bucle real que queda es el externo sobre los \(k\) impares, y también ese termina en cuanto la prueba con \(t=1\) demuestra que el \(k\) actual y todos los posteriores ya son imposibles.
Cada \(k\) impar potencialmente válido se procesa en \(O(1)\) tiempo aritmético tras un número constante de raíces cuadradas enteras, y el consumo de memoria es \(O(1)\).
Sea \(K_{\max}\) el mayor \(k\) impar que todavía puede superar la prueba con \(t=1\). Como
$$Y_{k,1}=\frac{(k-4)^2(k-1)}{2}=\Theta(k^3),$$
se obtiene \(K_{\max}=O(N^{1/3})\). La otra condición, \(X_{k,1}=(2k-3)^2\), solo da una cota \(O(\sqrt{N})\), así que el término cúbico es el que determina el punto de parada asintótico. En consecuencia, el tiempo total es
$$O(N^{1/3}),$$
con memoria adicional constante.
这道题在实现中采用的核心化简，是把原始的多边形数线性变换问题改写成对奇数形状参数 \(k\ge 3\) 的求和。对每个奇数 \(k\)，先定义
$$\delta=k-2,\qquad \gamma=(k-4)^2.$$
然后，每一个可行配置都可以用一个整数参数 \(t\ge 1\) 来描述，并对应两个非负量
$$X_{k,t}=(2\delta t+1)^2,\qquad Y_{k,t}=\frac{\gamma}{2}\left(\delta t^2+t\right).$$
只有当这两个量同时满足
$$X_{k,t}\le N,\qquad Y_{k,t}\le N$$
时，\((k,t)\) 才是一个有效参数对。于是要求的总量可以写成
$$S(N)=\sum_{\substack{k\ge 3\\ k\equiv 1 \!\!\!\pmod 2}}\ \sum_{\substack{t\ge 1\\ X_{k,t}\le N,\ Y_{k,t}\le N}}\left(X_{k,t}+Y_{k,t}\right).$$
真正的难点不在于公式本身，而在于 \(N\) 非常大，不能对所有可能的 \(t\) 逐个枚举。高效做法必须回答两个问题：第一，固定 \(k\) 后如何直接算出所有可行 \(t\) 的总贡献；第二，什么时候可以断定更大的奇数 \(k\) 不会再有任何贡献，从而立即停止外层循环。
对固定的奇数 \(k\)，记它单独带来的总贡献为 \(C_k(N)\)。下面的推导与 C++、Python、Java 三份实现中使用的数学结构完全一致。
一旦 \(k\) 固定，剩余的自由参数只有 \(t\ge 1\)。由于 \(\delta=k-2>0\)，并且 \(\gamma=(k-4)^2>0\)，所以 \(X_{k,t}\) 与 \(Y_{k,t}\) 都会随着 \(t\) 增大而增大。这一点非常重要，因为它意味着可行的 \(t\) 不会是零散分布的，而一定是从 \(1\) 开始的一段连续区间。
还要注意一个整除性细节。因为 \(k\) 是奇数，所以 \(\delta\) 也是奇数，于是
$$\delta t^2+t=t(\delta t+1)$$
始终为偶数。原因是：如果 \(t\) 为奇数，那么 \(\delta t\) 也是奇数，因此 \(\delta t+1\) 为偶数；如果 \(t\) 为偶数，那么前面的因子 \(t\) 本身就是偶数。这样一来，虽然 \(Y_{k,t}\) 的定义里有一个 \(1/2\)，它实际上总是整数。
因此，对固定的 \(k\)，所有可行的 \(t\) 必然组成
$$1\le t\le T_k(N)$$
这样的初始区间，而对应贡献就是
$$C_k(N)=\sum_{t=1}^{T_k(N)}\left(X_{k,t}+Y_{k,t}\right).$$
先设
$$R=\left\lfloor\sqrt{N}\right\rfloor.$$
由可行性条件 \(X_{k,t}\le N\) 可知
$$\left(2\delta t+1\right)^2\le N.$$
因为左边和右边都非负，所以这与
$$2\delta t+1\le R$$
完全等价。于是 \(t\) 的第一个精确上界为
$$T_A(k,N)=\left\lfloor\frac{R-1}{2\delta}\right\rfloor.$$
这一步只需要一次整数平方根，就能把平方约束直接转成线性上界。
再看另一条约束：
$$\frac{\gamma}{2}\left(\delta t^2+t\right)\le N.$$
由于 \(\gamma>0\)，可以把它移到右边，并定义
$$M=\left\lfloor\frac{2N}{\gamma}\right\rfloor.$$
这样就得到等价的不等式
$$\delta t^2+t\le M.$$
这已经是标准的二次不等式。求方程
$$\delta t^2+t-M=0$$
的正根，可得
$$\frac{-1+\sqrt{1+4\delta M}}{2\delta}.$$
因为 \(t\) 必须是整数，所以真正的上界应该写成
$$T_B(k,N)=\left\lfloor\frac{\left\lfloor\sqrt{1+4\delta M}\right\rfloor-1}{2\delta}\right\rfloor.$$
于是，对固定 \(k\)，允许的最大 \(t\) 就是两条约束共同作用下的较小者：
$$T_k(N)=\min\!\bigl(T_A(k,N),T_B(k,N)\bigr).$$
令 \(T=T_k(N)\)。接下来不再逐项遍历 \(t\)，而是使用经典求和公式
$$S_1(T)=\sum_{t=1}^{T} t=\frac{T(T+1)}{2},\qquad S_2(T)=\sum_{t=1}^{T} t^2=\frac{T(T+1)(2T+1)}{6}.$$
先展开第一部分：
$$X_{k,t}=(2\delta t+1)^2=4\delta^2t^2+4\delta t+1.$$
因此
$$\sum_{t=1}^{T}X_{k,t}=4\delta^2S_2(T)+4\delta S_1(T)+T.$$
第二部分则是
$$\sum_{t=1}^{T}Y_{k,t}=\frac{\gamma}{2}\sum_{t=1}^{T}\left(\delta t^2+t\right)=\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).$$
把两部分合起来，就得到固定 \(k\) 的完整闭式：
$$\boxed{C_k(N)=T+4\delta S_1(T)+4\delta^2S_2(T)+\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).}$$
这一步是整个算法的关键。原本看起来需要对所有 \(t\) 累加，现在只要先求出 \(T_k(N)\)，再代入两个标准和式就可以在常数时间内完成。
对于任意固定的奇数 \(k\)，最小候选参数总是 \(t=1\)。因此，一个 \(k\) 想要产生非零贡献，至少必须满足
$$X_{k,1}=(2k-3)^2\le N,\qquad Y_{k,1}=\frac{(k-4)^2(k-1)}{2}\le N.$$
如果在 \(t=1\) 时其中任何一条已经不成立，那么更大的 \(t\) 只会让 \(X_{k,t}\) 和 \(Y_{k,t}\) 更大，因此不可能重新变得可行。
更进一步，随着奇数 \(k\) 增大，\(X_{k,1}\) 与 \(Y_{k,1}\) 本身也会同步增大。也就是说，一旦某个奇数 \(k\) 在 \(t=1\) 处失败，那么所有更大的奇数 \(k\) 都必然失败。这就给出了外层循环的严格终止条件，不需要继续试探后面的值。
这个例子足够小，可以手算验证；同时又足够完整，能够展示所有关键步骤。
先看 \(k=3\)。此时
$$\delta=1,\qquad \gamma=1.$$
因为 \(\lfloor\sqrt{100}\rfloor=10\)，所以
$$T_A(3,100)=\left\lfloor\frac{10-1}{2}\right\rfloor=4.$$
另一方面，
$$M=\left\lfloor\frac{2\cdot 100}{1}\right\rfloor=200,$$
因此判别式为
$$1+4\delta M=1+4\cdot 1\cdot 200=801,$$
其整数平方根是
$$\left\lfloor\sqrt{801}\right\rfloor=28.$$
于是
$$T_B(3,100)=\left\lfloor\frac{28-1}{2}\right\rfloor=13.$$
两者取最小，得到
$$T_3(100)=4.$$
再计算标准和式：
$$S_1(4)=10,\qquad S_2(4)=30.$$
代入闭式可得
$$C_3(100)=4+4\cdot 10+4\cdot 30+\frac{1}{2}(30+10)=164+20=184.$$
接着看 \(k=5\)。这时
$$\delta=3,\qquad \gamma=1.$$
第一个上界是
$$T_A(5,100)=\left\lfloor\frac{10-1}{6}\right\rfloor=1.$$
而第二个上界中，判别式变成
$$1+4\delta M=1+4\cdot 3\cdot 200=2401,$$
所以
$$\left\lfloor\sqrt{2401}\right\rfloor=49,\qquad T_B(5,100)=\left\lfloor\frac{49-1}{6}\right\rfloor=8.$$
因此
$$T_5(100)=1.$$
此时只剩一项，于是
$$C_5(100)=(2\cdot 3\cdot 1+1)^2+\frac{1}{2}(3\cdot 1^2+1)=49+2=51.$$
再看 \(k=7\)。最小候选 \(t=1\) 时就已经有
$$X_{7,1}=(2\cdot 7-3)^2=11^2=121>100.$$
这说明 \(k=7\) 不可行，所有更大的奇数 \(k\) 也同样不可行。于是总和立刻结束：
$$S(100)=184+51=235.$$
C++、Python 和 Java 三个实现遵循的是同一套步骤。它们只枚举奇数 \(k\ge 3\)，对每个 \(k\) 分别用整数平方根算出两个上界 \(T_A\) 与 \(T_B\)，再取二者最小值作为最后一个可行的 \(t\)。
如果这个最小值是 \(0\)，说明当前 \(k\) 没有贡献；否则就计算 \(S_1(T)\) 与 \(S_2(T)\)，代入上面的闭式公式，并把结果加到总答案中。
整个实现都不会显式遍历所有 \(t\)。真正保留下来的只有一层关于奇数 \(k\) 的外循环，而且这层循环也会在 \(t=1\) 的可行性测试失败时立刻终止，因为那意味着后面所有更大的奇数 \(k\) 都不可能再贡献任何值。
每个可能有贡献的奇数 \(k\) 都只需要常数次整数平方根和常数次整数运算，因此单个 \(k\) 的代价是 \(O(1)\)，额外空间是 \(O(1)\)。
设 \(K_{\max}\) 为还能通过 \(t=1\) 测试的最大奇数 \(k\)。由于
$$Y_{k,1}=\frac{(k-4)^2(k-1)}{2}=\Theta(k^3),$$
所以有 \(K_{\max}=O(N^{1/3})\)。相比之下，来自 \(X_{k,1}=(2k-3)^2\) 的约束只给出 \(O(\sqrt{N})\) 的上界，渐近上更弱。于是总时间复杂度为
$$O(N^{1/3}),$$
空间复杂度保持为常数。
Используемое в решении арифметическое преобразование переписывает исходную задачу о линейных преобразованиях полигональных чисел как сумму по нечетным параметрам формы \(k\ge 3\). Для каждого нечетного \(k\) вводятся обозначения
$$\delta=k-2,\qquad \gamma=(k-4)^2.$$
После этого каждая допустимая конфигурация задается целым параметром \(t\ge 1\) и вносит два неотрицательных вклада
$$X_{k,t}=(2\delta t+1)^2,\qquad Y_{k,t}=\frac{\gamma}{2}\left(\delta t^2+t\right).$$
Пара \((k,t)\) считается допустимой только тогда, когда одновременно выполняются условия \(X_{k,t}\le N\) и \(Y_{k,t}\le N\). Поэтому искомая величина имеет вид
$$S(N)=\sum_{\substack{k\ge 3\\ k\equiv 1 \!\!\!\pmod 2}}\ \sum_{\substack{t\ge 1\\ X_{k,t}\le N,\ Y_{k,t}\le N}}\left(X_{k,t}+Y_{k,t}\right).$$
Главная трудность состоит в том, что \(N\) очень велико, а значит нельзя перебрать все возможные \(t\) напрямую. Нужно заменить внутреннюю сумму замкнутой формулой и получить строгий критерий, когда дальнейшие нечетные \(k\) уже точно ничего не дадут.
Для фиксированного нечетного \(k\) обозначим его суммарный вклад через \(C_k(N)\). Следующие шаги в точности отражают ту математику, на которой построены реализации.
После фиксации \(k\) единственным свободным параметром остается \(t\ge 1\). Поскольку \(\delta=k-2>0\) и \(\gamma=(k-4)^2>0\), обе последовательности \(X_{k,t}\) и \(Y_{k,t}\) возрастают по \(t\).
Есть и важная проверка целочисленности. Так как \(k\) нечетно, \(\delta\) тоже нечетно, а значит
$$\delta t^2+t=t(\delta t+1)$$
всегда четно. Если \(t\) нечетно, то \(\delta t\) нечетно, а \(\delta t+1\) четно; если \(t\) четно, то четен уже множитель \(t\). Следовательно, несмотря на множитель \(1/2\), выражение \(Y_{k,t}\) всегда целое.
Из монотонности следует, что допустимые значения \(t\) образуют начальный отрезок
$$1\le t\le T_k(N),$$
и вклад этого \(k\) равен
$$C_k(N)=\sum_{t=1}^{T_k(N)}\left(X_{k,t}+Y_{k,t}\right).$$
Обозначим
$$R=\left\lfloor\sqrt{N}\right\rfloor.$$
Тогда условие \(X_{k,t}\le N\) записывается как
$$\left(2\delta t+1\right)^2\le N.$$
Поскольку все величины неотрицательны, это эквивалентно неравенству
$$2\delta t+1\le R,$$
откуда получаем точную целочисленную оценку
$$T_A(k,N)=\left\lfloor\frac{R-1}{2\delta}\right\rfloor.$$
Теперь используем второе условие допустимости:
$$\frac{\gamma}{2}\left(\delta t^2+t\right)\le N.$$
Так как \(\gamma>0\), удобно ввести
$$M=\left\lfloor\frac{2N}{\gamma}\right\rfloor$$
и переписать требование в виде
$$\delta t^2+t\le M.$$
Это квадратичное неравенство. Положительный корень уравнения \(\delta t^2+t-M=0\) равен
$$\frac{-1+\sqrt{1+4\delta M}}{2\delta}.$$
Следовательно, точная целочисленная граница имеет вид
$$T_B(k,N)=\left\lfloor\frac{\left\lfloor\sqrt{1+4\delta M}\right\rfloor-1}{2\delta}\right\rfloor.$$
Максимально допустимое \(t\) определяется пересечением обеих оценок:
$$T_k(N)=\min\!\bigl(T_A(k,N),T_B(k,N)\bigr).$$
Положим \(T=T_k(N)\). Введем стандартные суммы
$$S_1(T)=\sum_{t=1}^{T} t=\frac{T(T+1)}{2},\qquad S_2(T)=\sum_{t=1}^{T} t^2=\frac{T(T+1)(2T+1)}{6}.$$
Поскольку
$$X_{k,t}=4\delta^2 t^2+4\delta t+1,$$
получаем
$$\sum_{t=1}^{T}X_{k,t}=4\delta^2S_2(T)+4\delta S_1(T)+T.$$
Для второй части имеем
$$\sum_{t=1}^{T}Y_{k,t}=\frac{\gamma}{2}\sum_{t=1}^{T}\left(\delta t^2+t\right)=\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).$$
Итак, полный вклад фиксированного нечетного \(k\) равен
$$\boxed{C_k(N)=T+4\delta S_1(T)+4\delta^2S_2(T)+\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).}$$
В этом и состоит главная оптимизация: как только найдено \(T_k(N)\), весь вклад данного \(k\) вычисляется за постоянное время, без явного перебора всех \(t\).
Минимально возможный параметр всегда равен \(t=1\). Поэтому необходимым условием ненулевого вклада для данного нечетного \(k\) является
$$X_{k,1}=(2k-3)^2\le N,\qquad Y_{k,1}=\frac{(k-4)^2(k-1)}{2}\le N.$$
Если хотя бы одно из этих условий уже нарушается при \(t=1\), то никакое большее значение \(t\) не подойдет, потому что и \(X_{k,t}\), и \(Y_{k,t}\) растут по \(t\).
Более того, сами величины \(X_{k,1}\) и \(Y_{k,1}\) тоже растут при увеличении нечетного \(k\). Значит, как только некоторое нечетное \(k\) проваливает тест при \(t=1\), все большие нечетные \(k\) проваливают его автоматически. Именно это и оправдывает немедленный выход из внешнего цикла.
Этот пример достаточно мал для ручной проверки и при этом показывает все ключевые идеи метода.
Сначала возьмем \(k=3\). Тогда
$$\delta=1,\qquad \gamma=1.$$
Так как \(\lfloor\sqrt{100}\rfloor=10\), получаем
$$T_A(3,100)=\left\lfloor\frac{10-1}{2}\right\rfloor=4.$$
Далее
$$M=\left\lfloor\frac{2\cdot 100}{1}\right\rfloor=200,$$
поэтому дискриминант равен
$$1+4\delta M=1+4\cdot 1\cdot 200=801,$$
а его целочисленный квадратный корень равен
$$\left\lfloor\sqrt{801}\right\rfloor=28.$$
Следовательно,
$$T_B(3,100)=\left\lfloor\frac{28-1}{2}\right\rfloor=13,$$
и значит
$$T_3(100)=4.$$
Так как \(S_1(4)=10\) и \(S_2(4)=30\), имеем
$$C_3(100)=4+4\cdot 10+4\cdot 30+\frac{1}{2}(30+10)=164+20=184.$$
Теперь возьмем \(k=5\). Здесь
$$\delta=3,\qquad \gamma=1.$$
Первая оценка дает
$$T_A(5,100)=\left\lfloor\frac{10-1}{6}\right\rfloor=1.$$
Во второй оценке получаем
$$1+4\delta M=1+4\cdot 3\cdot 200=2401,$$
откуда
$$\left\lfloor\sqrt{2401}\right\rfloor=49,\qquad T_B(5,100)=\left\lfloor\frac{49-1}{6}\right\rfloor=8.$$
Итак,
$$T_5(100)=1,$$
а значит вклад равен всего одной сумме:
$$C_5(100)=(2\cdot 3\cdot 1+1)^2+\frac{1}{2}(3\cdot 1^2+1)=49+2=51.$$
Наконец, для \(k=7\) уже первое значение при \(t=1\) оказывается слишком большим:
$$X_{7,1}=(2\cdot 7-3)^2=11^2=121>100.$$
Следовательно, \(k=7\) и все большие нечетные значения исключаются, и общий результат равен
$$S(100)=184+51=235.$$
Реализации на C++, Python и Java выполняют одну и ту же последовательность действий. Они перебирают только нечетные \(k\ge 3\), для каждого \(k\) вычисляют две точные границы \(T_A\) и \(T_B\) через целочисленные квадратные корни и берут минимум этих двух величин.
Если этот минимум равен нулю, текущий \(k\) ничего не добавляет. Если он положителен, реализация считает \(S_1(T)\) и \(S_2(T)\), подставляет их в замкнутые формулы и прибавляет результат к накопленной сумме.
Ни одна версия не выполняет явный внутренний цикл по всем \(t\). Остается только внешний проход по нечетным \(k\), и он тоже завершается сразу, как только проверка при \(t=1\) доказывает невозможность текущего и всех последующих нечетных значений.
Каждое потенциально допустимое нечетное \(k\) обрабатывается за \(O(1)\) арифметических операций после постоянного числа вычислений целочисленного квадратного корня, а дополнительная память равна \(O(1)\).
Пусть \(K_{\max}\) обозначает наибольшее нечетное \(k\), способное пройти тест при \(t=1\). Поскольку
$$Y_{k,1}=\frac{(k-4)^2(k-1)}{2}=\Theta(k^3),$$
получаем \(K_{\max}=O(N^{1/3})\). Ограничение из \(X_{k,1}=(2k-3)^2\) дает только \(O(\sqrt{N})\), то есть асимптотически слабее. Поэтому полное время работы равно
$$O(N^{1/3}),$$
при постоянной дополнительной памяти.
الاختزال الحسابي الذي تعتمد عليه الحلول يعيد صياغة مسألة التحويلات الخطية للأعداد المضلعّة على هيئة مجموع فوق معاملات شكلية فردية \(k\ge 3\). ولكل قيمة فردية من \(k\) نعرّف
$$\delta=k-2,\qquad \gamma=(k-4)^2.$$
بعد ذلك تصبح كل حالة صالحة موصوفة بعدد صحيح \(t\ge 1\)، وتنتج عنها كميتان غير سالبتين هما
$$X_{k,t}=(2\delta t+1)^2,\qquad Y_{k,t}=\frac{\gamma}{2}\left(\delta t^2+t\right).$$
ولا يُعد الزوج \((k,t)\) صالحًا إلا إذا تحقق الشرطان
$$X_{k,t}\le N,\qquad Y_{k,t}\le N.$$
وبذلك يمكن كتابة المقدار المطلوب على الصورة
$$S(N)=\sum_{\substack{k\ge 3\\ k\equiv 1 \!\!\!\pmod 2}}\ \sum_{\substack{t\ge 1\\ X_{k,t}\le N,\ Y_{k,t}\le N}}\left(X_{k,t}+Y_{k,t}\right).$$
الصعوبة الحقيقية هي أن \(N\) كبير جدًا، ولذلك لا يمكن المرور على جميع قيم \(t\) الممكنة. المطلوب إذن هو تحويل المجموع الداخلي إلى صيغة مغلقة، ثم إيجاد قاعدة توقف دقيقة تخبرنا متى تصبح كل القيم الفردية الأكبر من \(k\) غير قادرة على الإسهام.
لنفترض أن \(k\) قيمة فردية ثابتة، ولنرمز إلى مساهمتها الكلية بالرمز \(C_k(N)\). الخطوات الآتية هي الترجمة الرياضية المباشرة لما تنفذه تطبيقات C++ وPython وJava.
بعد تثبيت \(k\)، لا يبقى متغير حر إلا \(t\ge 1\). وبما أن \(\delta=k-2>0\) و\(\gamma=(k-4)^2>0\)، فإن كلا المقدارين \(X_{k,t}\) و\(Y_{k,t}\) يزدادان بازدياد \(t\).
وهناك ملاحظة عددية مهمة: بما أن \(k\) فردي فإن \(\delta\) فردي أيضًا، وبالتالي
$$\delta t^2+t=t(\delta t+1)$$
يكون دائمًا زوجيًا. فإذا كانت \(t\) فردية كان \(\delta t\) فرديًا ومن ثم \(\delta t+1\) زوجيًا، وإذا كانت \(t\) زوجية كان العامل \(t\) نفسه زوجيًا. لذا فإن \(Y_{k,t}\) عدد صحيح دائمًا رغم وجود العامل \(1/2\).
وبسبب الرتابة، فإن جميع قيم \(t\) الصالحة تشكل مقطعًا ابتدائيًا من الشكل
$$1\le t\le T_k(N),$$
ومن ثم تصبح مساهمة هذه القيمة الفردية
$$C_k(N)=\sum_{t=1}^{T_k(N)}\left(X_{k,t}+Y_{k,t}\right).$$
لنضع
$$R=\left\lfloor\sqrt{N}\right\rfloor.$$
من الشرط \(X_{k,t}\le N\) نحصل على
$$\left(2\delta t+1\right)^2\le N.$$
ولأن جميع الأطراف غير سالبة، فهذا يكافئ تمامًا
$$2\delta t+1\le R.$$
إذن الحد الأعلى الصحيح الأول هو
$$T_A(k,N)=\left\lfloor\frac{R-1}{2\delta}\right\rfloor.$$
نستخدم الآن الشرط الثاني:
$$\frac{\gamma}{2}\left(\delta t^2+t\right)\le N.$$
وبما أن \(\gamma>0\)، نعرّف
$$M=\left\lfloor\frac{2N}{\gamma}\right\rfloor$$
فتصبح المتباينة
$$\delta t^2+t\le M.$$
وهذه متباينة تربيعية. الجذر الموجب للمعادلة \(\delta t^2+t-M=0\) هو
$$\frac{-1+\sqrt{1+4\delta M}}{2\delta}.$$
وبما أن \(t\) عدد صحيح، فإن الحد الأعلى الدقيق يكتب على الصورة
$$T_B(k,N)=\left\lfloor\frac{\left\lfloor\sqrt{1+4\delta M}\right\rfloor-1}{2\delta}\right\rfloor.$$
ومن ثم فإن المجال الفعلي المسموح به هو
$$T_k(N)=\min\!\bigl(T_A(k,N),T_B(k,N)\bigr).$$
لنكتب \(T=T_k(N)\). بدلًا من جمع الحدود واحدًا واحدًا، نستخدم الصيغ المعروفة
$$S_1(T)=\sum_{t=1}^{T} t=\frac{T(T+1)}{2},\qquad S_2(T)=\sum_{t=1}^{T} t^2=\frac{T(T+1)(2T+1)}{6}.$$
وبما أن
$$X_{k,t}=4\delta^2 t^2+4\delta t+1,$$
فإن
$$\sum_{t=1}^{T}X_{k,t}=4\delta^2S_2(T)+4\delta S_1(T)+T.$$
أما الجزء الثاني فيصبح
$$\sum_{t=1}^{T}Y_{k,t}=\frac{\gamma}{2}\sum_{t=1}^{T}\left(\delta t^2+t\right)=\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).$$
إذن مساهمة القيمة الفردية الواحدة \(k\) تعطى بالصيغة المغلقة
$$\boxed{C_k(N)=T+4\delta S_1(T)+4\delta^2S_2(T)+\frac{\gamma}{2}\left(\delta S_2(T)+S_1(T)\right).}$$
وهذا هو جوهر التسريع: بعد إيجاد \(T_k(N)\) لا تبقى حاجة إلى أي تعداد داخلي على \(t\)، إذ يمكن حساب المساهمة كاملة بزمن ثابت.
أصغر قيمة ممكنة دائمًا هي \(t=1\). لذلك فإن شرطًا لازمًا لكي تساهم قيمة فردية معينة من \(k\) هو
$$X_{k,1}=(2k-3)^2\le N,\qquad Y_{k,1}=\frac{(k-4)^2(k-1)}{2}\le N.$$
إذا فشل أحد هذين الشرطين عند \(t=1\)، فلن تنجح أي قيمة أكبر لـ \(t\)، لأن كلا المقدارين \(X_{k,t}\) و\(Y_{k,t}\) يزدادان مع \(t\).
وفوق ذلك، فإن القيمتين \(X_{k,1}\) و\(Y_{k,1}\) تزدادان أيضًا عندما ننتقل إلى قيم فردية أكبر من \(k\). ولذلك، ما إن تفشل قيمة فردية ما في اختبار \(t=1\)، حتى تفشل جميع القيم الفردية الأكبر منها تلقائيًا. وهذه هي الحجة التي تسمح بإنهاء الحلقة الخارجية فورًا.
هذا المثال صغير بما يكفي للتحقق اليدوي، لكنه في الوقت نفسه يعرض جميع عناصر الطريقة بوضوح.
أولًا، عند \(k=3\) يكون
$$\delta=1,\qquad \gamma=1.$$
ولأن \(\lfloor\sqrt{100}\rfloor=10\)، نحصل على
$$T_A(3,100)=\left\lfloor\frac{10-1}{2}\right\rfloor=4.$$
كما أن
$$M=\left\lfloor\frac{2\cdot 100}{1}\right\rfloor=200,$$
ومن ثم يكون المميز
$$1+4\delta M=1+4\cdot 1\cdot 200=801,$$
وجذره التربيعي الصحيح هو
$$\left\lfloor\sqrt{801}\right\rfloor=28.$$
إذن
$$T_B(3,100)=\left\lfloor\frac{28-1}{2}\right\rfloor=13,$$
وبالتالي
$$T_3(100)=4.$$
ومع
$$S_1(4)=10,\qquad S_2(4)=30$$
نجد أن
$$C_3(100)=4+4\cdot 10+4\cdot 30+\frac{1}{2}(30+10)=164+20=184.$$
ثانيًا، عند \(k=5\) نحصل على
$$\delta=3,\qquad \gamma=1.$$
ومن ثم
$$T_A(5,100)=\left\lfloor\frac{10-1}{6}\right\rfloor=1.$$
وفي القيد الثاني يكون
$$1+4\delta M=1+4\cdot 3\cdot 200=2401,$$
وبالتالي
$$\left\lfloor\sqrt{2401}\right\rfloor=49,\qquad T_B(5,100)=\left\lfloor\frac{49-1}{6}\right\rfloor=8.$$
إذًا
$$T_5(100)=1,$$
فتصبح المساهمة
$$C_5(100)=(2\cdot 3\cdot 1+1)^2+\frac{1}{2}(3\cdot 1^2+1)=49+2=51.$$
أخيرًا، عند \(k=7\) يفشل الحد الأول مباشرة:
$$X_{7,1}=(2\cdot 7-3)^2=11^2=121>100.$$
وهذا يعني أن \(k=7\) وكل قيمة فردية أكبر منه غير صالحة، ومن ثم يكون المجموع النهائي
$$S(100)=184+51=235.$$
تتبع تطبيقات C++ وPython وJava الخطة نفسها تمامًا. فهي تمر فقط على القيم الفردية \(k\ge 3\)، وتحسب الحدين \(T_A\) و\(T_B\) بدقة باستخدام الجذر التربيعي الصحيح، ثم تأخذ الأصغر بينهما بوصفه آخر قيمة صالحة لـ \(t\).
إذا كان هذا الحد الأدنى يساوي صفرًا، فلا توجد مساهمة من \(k\) الحالية. وإذا كان موجبًا، تحسب الشيفرة المقدارين \(S_1(T)\) و\(S_2(T)\)، ثم تعوضهما في الصيغة المغلقة السابقة وتضيف الناتج إلى المجموع الكلي.
لا توجد حلقة داخلية تمر على كل قيم \(t\) صراحةً. الحلقة الحقيقية الوحيدة هي الحلقة الخارجية على القيم الفردية لـ \(k\)، وهذه بدورها تتوقف فورًا عندما يثبت اختبار \(t=1\) أن القيمة الحالية وكل القيم الفردية الأكبر منها أصبحت مستحيلة.
كل قيمة فردية محتملة لـ \(k\) تعالج في زمن \(O(1)\) بعد عدد ثابت من عمليات الجذر التربيعي الصحيح والحسابات الصحيحة، كما أن الذاكرة الإضافية المطلوبة هي \(O(1)\).
إذا رمزنا بأكبر قيمة فردية يمكنها اجتياز اختبار \(t=1\) إلى \(K_{\max}\)، فإن
$$Y_{k,1}=\frac{(k-4)^2(k-1)}{2}=\Theta(k^3)$$
يعطي مباشرة
$$K_{\max}=O(N^{1/3}).$$
أما القيد القادم من
$$X_{k,1}=(2k-3)^2$$
فلا يعطي إلا حدًا من رتبة \(O(\sqrt{N})\)، وهو أضعف من الحد التكعيبي من الناحية الأسيمبتوطية. لذلك يكون الزمن الكلي
$$O(N^{1/3}),$$
مع ذاكرة إضافية ثابتة.