For each integer \(k \ge 4\), let \(M(k)\) be the maximum possible sum of a geometric progression of positive integers with at least three terms, common ratio greater than \(1\), and largest term at most \(k\). The final target is the alternating total
$$A(N)=\sum_{k=4}^{N}(-1)^k M(k).$$
The real input is extremely large, so the solution cannot scan all geometric progressions and certainly cannot evaluate \(M(k)\) one value of \(k\) at a time. The key is to compress both the family of relevant progressions and the places where the maximum can actually change.
The three implementations are based on the same reduction: first write every admissible integer geometric progression in a canonical form, then keep only the candidates that can ever be optimal, and finally evaluate the alternating sum block by block.
Take a geometric progression with \(p+1\) terms, where \(p \ge 2\), common ratio \(a/b\) in lowest terms, and \(a > b \ge 1\). Because all terms must be integers, the progression can be written as
$$q b^p,\ q a b^{p-1},\ q a^2 b^{p-2},\ \dots,\ q a^p,$$
with some integer scale factor \(q \ge 1\). Its largest term is \(q a^p\), and its sum is
$$q\sum_{i=0}^{p} a^i b^{p-i}=q\,\frac{a^{p+1}-b^{p+1}}{a-b}.$$
So for fixed \(a\), \(b\), and \(p\), the best scale factor allowed by the bound \(k\) is
$$q=\left\lfloor \frac{k}{a^p} \right\rfloor.$$
For fixed \(a\), \(p\), and \(q\), the sum
$$q\sum_{i=0}^{p} a^i b^{p-i}$$
is strictly increasing in \(b\), because every term with exponent \(p-i > 0\) grows when \(b\) grows. Since \(b\) must satisfy \(1 \le b < a\), the best admissible choice is always
$$b=a-1.$$
Therefore only progressions of the form
$$q(a-1)^p,\ q a (a-1)^{p-1},\ \dots,\ q a^p$$
need to be considered. Their largest term and one-step contribution are
$$P(a,p)=a^p,\qquad \Delta(a,p)=a^{p+1}-(a-1)^{p+1}.$$
For a fixed \(k\), this candidate contributes
$$V_{a,p}(k)=\left\lfloor \frac{k}{P(a,p)} \right\rfloor \Delta(a,p).$$
Hence
$$M(k)=\max_{a \ge 2,\ p \ge 2} V_{a,p}(k).$$
If two candidates satisfy
$$P_1 \le P_2,\qquad \Delta_1 \ge \Delta_2,$$
then for every \(k\),
$$\left\lfloor \frac{k}{P_1} \right\rfloor \Delta_1 \ge \left\lfloor \frac{k}{P_2} \right\rfloor \Delta_2,$$
so the second candidate can never be optimal. The implementations therefore build only the record frontier: whenever the jump amount \(\Delta\) increases, they keep the smallest possible period \(P\) that achieves this new record. Because \(a^p \le N\), the exponent \(p\) only ranges up to \(\lfloor \log_2 N \rfloor\), and for each exponent the next record can be found by binary search on \(a\).
Even among record candidates, many are useful only for a finite interval of \(k\). Suppose candidate \(j\) has a better asymptotic slope than candidate \(i\), meaning
$$\frac{\Delta_j}{P_j} > \frac{\Delta_i}{P_i} \iff \Delta_j P_i > \Delta_i P_j.$$
Then
$$V_j(k)\ge \left(\frac{k}{P_j}-1\right)\Delta_j,\qquad V_i(k)\le \frac{k}{P_i}\Delta_i.$$
So candidate \(j\) is guaranteed to beat candidate \(i\) whenever
$$\left(\frac{k}{P_j}-1\right)\Delta_j > \frac{k}{P_i}\Delta_i,$$
which simplifies to
$$k > \frac{\Delta_j P_j P_i}{\Delta_j P_i-\Delta_i P_j}.$$
For each record candidate, the implementations take the minimum such bound over all stronger competitors. This produces a proven upper activity limit \(R\): once \(k > R\), that candidate can never again attain the maximum.
For one fixed candidate, the quantity \(\left\lfloor k / P \right\rfloor\) changes only when \(k\) reaches a multiple of \(P\). Therefore \(V_{a,p}(k)\) is constant between consecutive multiples of \(P\). After activity pruning, \(M(k)\) can change only at the union of all multiples of retained periods \(P\) up to \(\min(N,R)\). These integers are the event points. Once they are collected and sorted, every interval between consecutive events has a constant value of \(M(k)\).
If \(M(k)=C\) for every \(k \in [L,R]\), then that whole block contributes
$$C\sum_{k=L}^{R}(-1)^k.$$
The inner sign sum is elementary:
$$\sum_{k=L}^{R}(-1)^k= \begin{cases} 0, & R-L+1 \text{ is even},\\ 1, & R-L+1 \text{ is odd and } L \text{ is even},\\ -1, & R-L+1 \text{ is odd and } L \text{ is odd}. \end{cases}$$
So the total is accumulated blockwise. Exact recomputation of the maximum is needed only at event points, not at every integer up to \(N\).
The first useful candidates are
$$a=2,\ p=2:\quad (1,2,4),\qquad V_{2,2}(k)=7\left\lfloor \frac{k}{4} \right\rfloor,$$
$$a=2,\ p=3:\quad (1,2,4,8),\qquad V_{2,3}(k)=15\left\lfloor \frac{k}{8} \right\rfloor,$$
$$a=3,\ p=2:\quad (4,6,9),\qquad V_{3,2}(k)=19\left\lfloor \frac{k}{9} \right\rfloor.$$
Up to \(12\), the event points are \(4,8,9,12\). Therefore
$$\begin{aligned} 4 \le k \le 7&:&&M(k)=7,\\ 8 \le k \le 8&:&&M(k)=14,\\ 9 \le k \le 11&:&&M(k)=19,\\ 12 \le k \le 12&:&&M(k)=21. \end{aligned}$$
In particular, \(M(4)=7\), \(M(10)=19\), and \(M(12)=21\). The alternating total up to \(12\) is
$$A(12)=0+14-19+21=16,$$
because the block \([4,7]\) has even length and contributes \(0\). This is exactly the kind of block compression the implementations exploit at the full scale.
The C++, Python, and Java implementations follow the same pipeline. First they determine all admissible exponents \(p\) with \(2^p \le N\), and for each such exponent they use integer roots to bound the search range for \(a\). Then they repeatedly raise the current record jump amount and use binary search to find the smallest base \(a\) that beats it for each exponent. Among those contenders, the implementation keeps the one with the smallest period \(a^p\), which yields the next record candidate on the frontier.
Next, the implementations compare every pair of retained candidates and assign each one an activity limit using the inequality from Step 4. After that, they generate all event points by listing the multiples of every retained period up to the smaller of the global limit and that candidate's activity bound. The list is sorted and duplicates are removed.
Finally, they sweep from \(4\) to \(N\). Between two successive event points the maximum sum is constant, so the code adds either \(0\), the block value, or its negation according to the parity rule above. At an event point it recomputes the exact maximum over the still-relevant candidates. The C++ version uses wide integer arithmetic and multiprecision only where overflow could occur; Python relies on arbitrary-precision integers naturally; Java uses big integers where the crossover calculation needs them.
Let \(C\) be the number of retained record candidates and \(E\) the number of distinct event points. Let \(P_{\max}=\lfloor \log_2 N \rfloor\). Building the record frontier requires scanning those exponents and performing binary searches on the admissible base range, so the preprocessing cost is driven by about \(C\) record extractions across \(P_{\max}\) exponent families. The pairwise activity-bound computation costs \(O(C^2)\). Event generation costs \(O(E)\) insertions plus \(O(E \log E)\) for sorting and deduplication. The final sweep is \(O(E \cdot C)\) in the worst case because an event-point recomputation may inspect every retained candidate, although the activity limits keep the practical active set much smaller. The memory usage is \(O(C+E)\).
Für jedes \(k \ge 4\) sei \(M(k)\) die größtmögliche Summe einer geometrischen Folge aus positiven ganzen Zahlen mit mindestens drei Gliedern, Quotienten größer als \(1\) und größtem Glied höchstens \(k\). Gesucht ist dann die alternierende Summe
$$A(N)=\sum_{k=4}^{N}(-1)^k M(k).$$
Für die echte Eingabe ist weder eine Aufzählung aller geometrischen Folgen noch ein punktweises Auswerten von \(M(k)\) bis \(N\) machbar. Die Lösung komprimiert deshalb sowohl die relevanten Folgen als auch die Stellen, an denen sich das Maximum überhaupt ändern kann.
Alle drei Implementierungen beruhen auf derselben Reduktion: Zuerst wird jede zulässige ganzzahlige geometrische Folge in eine kanonische Form gebracht, dann werden nur die Kandidaten behalten, die jemals optimal sein können, und schließlich wird die alternierende Summe blockweise ausgewertet.
Betrachte eine geometrische Folge mit \(p+1\) Gliedern, \(p \ge 2\), Quotienten \(a/b\) in vollständig gekürzter Form und \(a > b \ge 1\). Weil alle Glieder ganzzahlig sein müssen, lässt sie sich schreiben als
$$q b^p,\ q a b^{p-1},\ q a^2 b^{p-2},\ \dots,\ q a^p,$$
wobei \(q \ge 1\) ganzzahlig ist. Das größte Glied ist \(q a^p\), und die Summe lautet
$$q\sum_{i=0}^{p} a^i b^{p-i}=q\,\frac{a^{p+1}-b^{p+1}}{a-b}.$$
Für festes \(a\), \(b\) und \(p\) ist der beste mit der Schranke \(k\) verträgliche Skalierungsfaktor also
$$q=\left\lfloor \frac{k}{a^p} \right\rfloor.$$
Für feste Werte von \(a\), \(p\) und \(q\) wächst die Summe
$$q\sum_{i=0}^{p} a^i b^{p-i}$$
streng mit \(b\), denn jeder Summand mit Exponent \(p-i > 0\) wird größer, wenn \(b\) größer wird. Da \(b\) nur \(1 \le b < a\) erfüllen darf, ist die beste Wahl stets
$$b=a-1.$$
Damit genügen Folgen der Form
$$q(a-1)^p,\ q a (a-1)^{p-1},\ \dots,\ q a^p.$$
Ihr größtes Glied und ihr Sprungwert sind
$$P(a,p)=a^p,\qquad \Delta(a,p)=a^{p+1}-(a-1)^{p+1}.$$
Für ein festes \(k\) trägt dieser Kandidat also
$$V_{a,p}(k)=\left\lfloor \frac{k}{P(a,p)} \right\rfloor \Delta(a,p)$$
bei, und damit gilt
$$M(k)=\max_{a \ge 2,\ p \ge 2} V_{a,p}(k).$$
Erfüllen zwei Kandidaten
$$P_1 \le P_2,\qquad \Delta_1 \ge \Delta_2,$$
dann folgt für alle \(k\)
$$\left\lfloor \frac{k}{P_1} \right\rfloor \Delta_1 \ge \left\lfloor \frac{k}{P_2} \right\rfloor \Delta_2,$$
also kann der zweite Kandidat niemals optimal sein. Deshalb konstruieren die Implementierungen nur die Rekord-Front: Immer wenn der Sprungwert \(\Delta\) steigt, wird der kleinste mögliche Zeitraum \(P\) behalten, der diesen neuen Rekord erreicht. Wegen \(a^p \le N\) muss man nur Exponenten bis \(\lfloor \log_2 N \rfloor\) betrachten, und für jeden Exponenten lässt sich der nächste Rekord per Binärsuche über \(a\) finden.
Auch unter den Rekorden sind viele Kandidaten nur auf einem endlichen Bereich von \(k\) nützlich. Habe Kandidat \(j\) die bessere asymptotische Steigung als Kandidat \(i\), also
$$\frac{\Delta_j}{P_j} > \frac{\Delta_i}{P_i} \iff \Delta_j P_i > \Delta_i P_j,$$
dann gilt
$$V_j(k)\ge \left(\frac{k}{P_j}-1\right)\Delta_j,\qquad V_i(k)\le \frac{k}{P_i}\Delta_i.$$
Somit schlägt \(j\) den Kandidaten \(i\) garantiert, sobald
$$\left(\frac{k}{P_j}-1\right)\Delta_j > \frac{k}{P_i}\Delta_i,$$
also
$$k > \frac{\Delta_j P_j P_i}{\Delta_j P_i-\Delta_i P_j}.$$
Für jeden Rekordkandidaten nimmt die Implementierung das Minimum solcher Schranken über alle stärkeren Konkurrenten. Das ergibt eine bewiesene obere Relevanzgrenze \(R\): Für \(k > R\) kann dieser Kandidat nie wieder das Maximum liefern.
Für einen festen Kandidaten ändert sich \(\left\lfloor k/P \right\rfloor\) nur dann, wenn \(k\) ein Vielfaches von \(P\) erreicht. Daher ist \(V_{a,p}(k)\) zwischen zwei aufeinanderfolgenden Vielfachen von \(P\) konstant. Nach dem Relevanzschnitt kann sich \(M(k)\) also nur an der Vereinigung aller Vielfachen der behaltenen Perioden \(P\) bis \(\min(N,R)\) ändern. Diese Zahlen sind die Ereignispunkte. Nach Sortieren dieser Menge ist \(M(k)\) auf jedem Intervall zwischen zwei aufeinanderfolgenden Ereignissen konstant.
Gilt auf einem Block \(k \in [L,R]\) konstant \(M(k)=C\), dann ist der gesamte Beitrag
$$C\sum_{k=L}^{R}(-1)^k.$$
Die innere Vorzeichensumme ist elementar:
$$\sum_{k=L}^{R}(-1)^k= \begin{cases} 0, & R-L+1 \text{ gerade ist},\\ 1, & R-L+1 \text{ ungerade ist und } L \text{ gerade ist},\\ -1, & R-L+1 \text{ ungerade ist und } L \text{ ungerade ist}. \end{cases}$$
Darum wird die Gesamtsumme blockweise akkumuliert. Eine exakte Neuberechnung des Maximums ist nur an Ereignispunkten nötig, nicht bei jedem einzelnen \(k\).
Die ersten nützlichen Kandidaten sind
$$a=2,\ p=2:\quad (1,2,4),\qquad V_{2,2}(k)=7\left\lfloor \frac{k}{4} \right\rfloor,$$
$$a=2,\ p=3:\quad (1,2,4,8),\qquad V_{2,3}(k)=15\left\lfloor \frac{k}{8} \right\rfloor,$$
$$a=3,\ p=2:\quad (4,6,9),\qquad V_{3,2}(k)=19\left\lfloor \frac{k}{9} \right\rfloor.$$
Bis \(12\) liegen die Ereignispunkte bei \(4,8,9,12\). Daher gilt
$$\begin{aligned} 4 \le k \le 7&:&&M(k)=7,\\ 8 \le k \le 8&:&&M(k)=14,\\ 9 \le k \le 11&:&&M(k)=19,\\ 12 \le k \le 12&:&&M(k)=21. \end{aligned}$$
Insbesondere sind \(M(4)=7\), \(M(10)=19\) und \(M(12)=21\). Die alternierende Summe bis \(12\) ist
$$A(12)=0+14-19+21=16,$$
weil der Block \([4,7]\) wegen seiner geraden Länge den Beitrag \(0\) liefert. Genau diese Blockkompression nutzen die Implementierungen auch im großen Fall.
Die C++, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst bestimmen sie alle zulässigen Exponenten \(p\) mit \(2^p \le N\) und begrenzen für jeden Exponenten den Suchraum für \(a\) über ganzzahlige Wurzeln. Danach erhöhen sie den aktuellen Rekord-Sprungwert schrittweise und finden per Binärsuche für jeden Exponenten die kleinste Basis \(a\), die diesen Wert übertrifft. Unter diesen Kandidaten wird derjenige mit der kleinsten Periode \(a^p\) als nächster Rekord der Front gespeichert.
Anschließend vergleichen die Implementierungen jedes Paar behaltene Kandidaten und weisen jedem Kandidaten mit Hilfe der Ungleichung aus Schritt 4 eine Relevanzgrenze zu. Danach erzeugen sie alle Ereignispunkte, indem sie die Vielfachen jeder behaltenen Periode bis zur kleineren der beiden Schranken, globale Grenze und Relevanzgrenze, auflisten. Die Liste wird sortiert und von Duplikaten bereinigt.
Zuletzt wird von \(4\) bis \(N\) gesweept. Zwischen zwei aufeinanderfolgenden Ereignispunkten bleibt die maximale Summe konstant, also addiert der Code je nach Parität entweder \(0\), den Blockwert oder dessen Negation. Genau an einem Ereignispunkt wird das Maximum über alle noch relevanten Kandidaten neu berechnet. Die C++-Version verwendet breite Ganzzahltypen und Multiprecision nur dort, wo Überlauf droht; Python nutzt eingebaute Ganzzahlarithmetik mit beliebiger Präzision; Java setzt für die kritischen Kreuzungsrechnungen große Ganzzahlen ein.
Sei \(C\) die Anzahl der behaltenen Rekordkandidaten und \(E\) die Anzahl verschiedener Ereignispunkte. Mit \(P_{\max}=\lfloor \log_2 N \rfloor\) benötigt der Aufbau der Rekord-Front etwa \(C\) Extraktionen über diese Exponentenfamilien, jeweils mit Binärsuchen im zulässigen Basisbereich. Die paarweise Relevanzberechnung kostet \(O(C^2)\). Die Ereigniserzeugung kostet \(O(E)\) Einfügungen plus \(O(E \log E)\) für Sortierung und Duplikatentfernung. Der abschließende Sweep kostet im Worst Case \(O(E \cdot C)\), weil eine Neuberechnung am Ereignispunkt alle behaltenen Kandidaten prüfen kann; in der Praxis wird die aktive Menge durch die Relevanzgrenzen deutlich kleiner. Der Speicherbedarf beträgt \(O(C+E)\).
Her \(k \ge 4\) için \(M(k)\), ortak oranı \(1\)'den büyük olan, en az üç terimli, tüm terimleri pozitif tamsayı olan ve en büyük terimi \(k\)'yı aşmayan geometrik dizilerin en büyük toplamı olsun. İstenen nihai değer
$$A(N)=\sum_{k=4}^{N}(-1)^k M(k)$$
alternatif toplamıdır. Gerçek girdi çok büyük olduğu için ne tüm geometrik dizileri tek tek üretmek ne de \(M(k)\)'yi \(4\)'ten \(N\)'ye kadar birer birer hesaplamak mümkündür. Çözüm, hem aday dizi ailesini hem de maksimumun değişebileceği konumları sıkıştırır.
Üç implementasyonun da dayandığı temel fikir aynıdır: Önce her uygun tamsayı geometrik diziyi standart bir biçimde yaz, sonra asla en iyi olamayacak adayları at, son olarak alternatif toplamı sabit bloklar üzerinden hesapla.
\(p+1\) terimli bir geometrik dizi düşünelim; burada \(p \ge 2\) olsun. Ortak oran sadeleştirilmiş biçimde \(a/b\) ve \(a > b \ge 1\) olsun. Tüm terimlerin tamsayı olması gerektiğinden dizi şu şekilde yazılabilir:
$$q b^p,\ q a b^{p-1},\ q a^2 b^{p-2},\ \dots,\ q a^p,$$
burada \(q \ge 1\) bir ölçek katsayısıdır. En büyük terim \(q a^p\), toplam ise
$$q\sum_{i=0}^{p} a^i b^{p-i}=q\,\frac{a^{p+1}-b^{p+1}}{a-b}$$
olur. Dolayısıyla \(k\) sınırı altında kullanılabilecek en büyük ölçek
$$q=\left\lfloor \frac{k}{a^p} \right\rfloor$$
şeklindedir.
\(a\), \(p\) ve \(q\) sabitken
$$q\sum_{i=0}^{p} a^i b^{p-i}$$
ifadesi \(b\) arttıkça büyür; çünkü \(p-i > 0\) olan her terim \(b\)'ye göre artandır. \(b\) için izinli aralık \(1 \le b < a\) olduğundan en iyi seçim her zaman
$$b=a-1$$
olur. Böylece yalnızca
$$q(a-1)^p,\ q a (a-1)^{p-1},\ \dots,\ q a^p$$
biçimindeki dizilere bakmak yeterlidir. Bu adayın en büyük terimi ve tek sıçramadaki katkısı
$$P(a,p)=a^p,\qquad \Delta(a,p)=a^{p+1}-(a-1)^{p+1}$$
olur. Sabit bir \(k\) için bu adayın katkısı
$$V_{a,p}(k)=\left\lfloor \frac{k}{P(a,p)} \right\rfloor \Delta(a,p)$$
şeklindedir; dolayısıyla
$$M(k)=\max_{a \ge 2,\ p \ge 2} V_{a,p}(k).$$
İki aday için
$$P_1 \le P_2,\qquad \Delta_1 \ge \Delta_2$$
ise her \(k\) için
$$\left\lfloor \frac{k}{P_1} \right\rfloor \Delta_1 \ge \left\lfloor \frac{k}{P_2} \right\rfloor \Delta_2$$
olur. Bu durumda ikinci aday hiçbir zaman optimum olamaz. Bu yüzden implementasyonlar sadece rekor sınırını üretir: \(\Delta\) değeri her yükseldiğinde, bunu sağlayan en küçük \(P\) değeri saklanır. Ayrıca \(a^p \le N\) olduğundan yalnızca \(p \le \lfloor \log_2 N \rfloor\) üsleri gerekir; her üste bir sonraki rekoru bulmak için \(a\) üzerinde ikili arama yapılır.
Rekor adaylar arasında bile bazıları yalnızca sonlu bir \(k\) aralığında faydalıdır. Eğer aday \(j\), aday \(i\)'ye göre daha iyi asimptotik eğime sahipse, yani
$$\frac{\Delta_j}{P_j} > \frac{\Delta_i}{P_i} \iff \Delta_j P_i > \Delta_i P_j,$$
o zaman
$$V_j(k)\ge \left(\frac{k}{P_j}-1\right)\Delta_j,\qquad V_i(k)\le \frac{k}{P_i}\Delta_i$$
eşitsizlikleri geçerlidir. Dolayısıyla \(j\), \(i\)'yi şu koşuldan sonra kesin olarak geçer:
$$\left(\frac{k}{P_j}-1\right)\Delta_j > \frac{k}{P_i}\Delta_i,$$
yani
$$k > \frac{\Delta_j P_j P_i}{\Delta_j P_i-\Delta_i P_j}.$$
İmplementasyon her aday için bu tür bütün daha güçlü rakipler arasındaki en küçük sınırı alır. Böylece ispatlı bir üst etkinlik değeri \(R\) elde edilir: \(k > R\) olduktan sonra o aday artık maksimumu veremez.
Sabit bir aday için \(\left\lfloor k/P \right\rfloor\) ancak \(k\), \(P\)'nin bir katına ulaştığında değişir. Bu nedenle \(V_{a,p}(k)\), \(P\)'nin ardışık katları arasında sabittir. Relevance budamasından sonra \(M(k)\) yalnızca saklanan periyotların \(P\) katlarında ve en fazla \(\min(N,R)\) noktasına kadar değişebilir. Bu tamsayılar olay noktalarıdır. Bunlar sıralandığında, ardışık iki olay noktası arasındaki her aralıkta \(M(k)\) sabit kalır.
Eğer \(k \in [L,R]\) boyunca \(M(k)=C\) sabitse, bu bloğun katkısı
$$C\sum_{k=L}^{R}(-1)^k$$
olur. İçteki işaret toplamı kapalı biçimde şöyledir:
$$\sum_{k=L}^{R}(-1)^k= \begin{cases} 0, & R-L+1 \text{ çift ise},\\ 1, & R-L+1 \text{ tek ve } L \text{ çift ise},\\ -1, & R-L+1 \text{ tek ve } L \text{ tek ise}. \end{cases}$$
Böylece toplam blok bazında biriktirilir. Maksimumu tam olarak yeniden hesaplamak yalnızca olay noktalarında gerekir.
İlk faydalı adaylar şunlardır:
$$a=2,\ p=2:\quad (1,2,4),\qquad V_{2,2}(k)=7\left\lfloor \frac{k}{4} \right\rfloor,$$
$$a=2,\ p=3:\quad (1,2,4,8),\qquad V_{2,3}(k)=15\left\lfloor \frac{k}{8} \right\rfloor,$$
$$a=3,\ p=2:\quad (4,6,9),\qquad V_{3,2}(k)=19\left\lfloor \frac{k}{9} \right\rfloor.$$
\(12\)'ye kadar olay noktaları \(4,8,9,12\) olur. Dolayısıyla
$$\begin{aligned} 4 \le k \le 7&:&&M(k)=7,\\ 8 \le k \le 8&:&&M(k)=14,\\ 9 \le k \le 11&:&&M(k)=19,\\ 12 \le k \le 12&:&&M(k)=21. \end{aligned}$$
Özellikle \(M(4)=7\), \(M(10)=19\), \(M(12)=21\) olur. \(12\)'ye kadarki alternatif toplam ise
$$A(12)=0+14-19+21=16$$
çıkar; çünkü \([4,7]\) bloğu çift uzunluklu olduğundan katkısı \(0\)'dır. Büyük ölçekte kullanılan blok sıkıştırma mantığı tam olarak budur.
C++, Python ve Java implementasyonları aynı akışı izler. Önce \(2^p \le N\) koşulunu sağlayan tüm üsler belirlenir ve her üs için \(a\) arama aralığı tam sayı kökleriyle sınırlandırılır. Ardından mevcut rekor sıçrama değeri adım adım yükseltilir; her üs için bu eşiği geçen en küçük taban \(a\) ikili aramayla bulunur. Bu adaylar arasından periyodu \(a^p\) en küçük olan, rekor sınırındaki bir sonraki aday olarak saklanır.
Daha sonra implementasyonlar saklanan tüm aday çiftlerini karşılaştırır ve Adım 4'teki eşitsizlikten yararlanarak her adaya bir etkinlik üst sınırı atar. Sonraki aşamada, her saklanan periyodun katları ilgili etkinlik sınırına ve küresel limite kadar üretilir; bunlar olay listesine eklenir, sıralanır ve tekrarlar silinir.
Son adımda \(4\)'ten \(N\)'ye doğru süpürme yapılır. İki olay noktası arasında maksimum toplam değişmediği için kod, parite kuralına göre ya \(0\), ya blok değerini, ya da onun negatifini ekler. Olay noktasına gelindiğinde, hâlâ geçerli olan adaylar arasından kesin maksimum yeniden hesaplanır. C++ sürümü taşma riski olan yerlerde geniş tamsayı aritmetiği ve çok hassas tamsayı türleri kullanır; Python doğal olarak sınırsız hassasiyetli tamsayılarla çalışır; Java ise kritik kesişim hesabında büyük tamsayı kullanır.
\(C\) saklanan rekor aday sayısı, \(E\) ise farklı olay noktası sayısı olsun. \(P_{\max}=\lfloor \log_2 N \rfloor\) ile, rekor sınırını kurma maliyeti yaklaşık olarak bu üs aileleri üzerinde yapılan \(C\) kadar rekor çıkarımı ve bunların içindeki ikili aramalardan oluşur. Çiftler arası etkinlik sınırı hesabı \(O(C^2)\) maliyetlidir. Olay üretimi \(O(E)\) ekleme ve \(O(E \log E)\) sıralama gerektirir. Son süpürme en kötü durumda \(O(E \cdot C)\) sürer; çünkü bir olay noktasında tüm saklanan adaylar incelenebilir. Pratikte etkinlik sınırları aktif aday kümesini çok daha küçük tutar. Bellek kullanımı \(O(C+E)\)'dir.
Para cada \(k \ge 4\), definimos \(M(k)\) como la suma máxima de una progresión geométrica de enteros positivos, con al menos tres términos, razón mayor que \(1\) y término máximo no superior a \(k\). El objetivo final es la suma alternante
$$A(N)=\sum_{k=4}^{N}(-1)^k M(k).$$
La entrada real es gigantesca, así que no se pueden enumerar todas las progresiones geométricas posibles ni evaluar \(M(k)\) uno por uno. La solución comprime tanto la familia de progresiones relevantes como los puntos en los que el máximo puede cambiar.
Las tres implementaciones siguen la misma reducción: escribir toda progresión geométrica entera admisible en forma canónica, conservar solo los candidatos que alguna vez pueden ser óptimos y, por último, acumular la suma alternante por bloques constantes.
Tomemos una progresión geométrica con \(p+1\) términos, donde \(p \ge 2\), razón \(a/b\) en forma reducida y \(a > b \ge 1\). Como todos los términos deben ser enteros, la progresión puede escribirse como
$$q b^p,\ q a b^{p-1},\ q a^2 b^{p-2},\ \dots,\ q a^p,$$
con un factor de escala entero \(q \ge 1\). El término mayor es \(q a^p\), y la suma vale
$$q\sum_{i=0}^{p} a^i b^{p-i}=q\,\frac{a^{p+1}-b^{p+1}}{a-b}.$$
Por tanto, para \(a\), \(b\) y \(p\) fijos, el mejor factor permitido por la cota \(k\) es
$$q=\left\lfloor \frac{k}{a^p} \right\rfloor.$$
Con \(a\), \(p\) y \(q\) fijos, la cantidad
$$q\sum_{i=0}^{p} a^i b^{p-i}$$
aumenta estrictamente con \(b\), porque cada término con exponente \(p-i > 0\) aumenta cuando aumenta \(b\). Como \(b\) debe cumplir \(1 \le b < a\), la mejor elección es siempre
$$b=a-1.$$
Así, solo hace falta considerar progresiones de la forma
$$q(a-1)^p,\ q a (a-1)^{p-1},\ \dots,\ q a^p.$$
Su término máximo y su ganancia elemental son
$$P(a,p)=a^p,\qquad \Delta(a,p)=a^{p+1}-(a-1)^{p+1}.$$
Para un \(k\) fijo, este candidato aporta
$$V_{a,p}(k)=\left\lfloor \frac{k}{P(a,p)} \right\rfloor \Delta(a,p),$$
y por ello
$$M(k)=\max_{a \ge 2,\ p \ge 2} V_{a,p}(k).$$
Si dos candidatos cumplen
$$P_1 \le P_2,\qquad \Delta_1 \ge \Delta_2,$$
entonces para todo \(k\)
$$\left\lfloor \frac{k}{P_1} \right\rfloor \Delta_1 \ge \left\lfloor \frac{k}{P_2} \right\rfloor \Delta_2,$$
de modo que el segundo nunca puede ser óptimo. Por eso las implementaciones construyen solo la frontera de récords: cada vez que el valor \(\Delta\) mejora, se conserva el menor período \(P\) que produce esa mejora. Como \(a^p \le N\), el exponente solo llega hasta \(\lfloor \log_2 N \rfloor\), y para cada exponente el siguiente récord se encuentra con búsqueda binaria sobre \(a\).
Incluso entre los récords, muchos candidatos solo importan en un intervalo finito. Si el candidato \(j\) tiene mejor pendiente asintótica que el candidato \(i\), es decir,
$$\frac{\Delta_j}{P_j} > \frac{\Delta_i}{P_i} \iff \Delta_j P_i > \Delta_i P_j,$$
entonces
$$V_j(k)\ge \left(\frac{k}{P_j}-1\right)\Delta_j,\qquad V_i(k)\le \frac{k}{P_i}\Delta_i.$$
Por lo tanto, \(j\) supera con seguridad a \(i\) cuando
$$\left(\frac{k}{P_j}-1\right)\Delta_j > \frac{k}{P_i}\Delta_i,$$
lo que se simplifica a
$$k > \frac{\Delta_j P_j P_i}{\Delta_j P_i-\Delta_i P_j}.$$
La implementación toma, para cada candidato, el mínimo de esas cotas entre todos los competidores más fuertes. Así obtiene un límite superior probado \(R\): una vez que \(k > R\), ese candidato ya no puede volver a alcanzar el máximo.
Para un candidato fijo, \(\left\lfloor k/P \right\rfloor\) solo cambia cuando \(k\) llega a un múltiplo de \(P\). Por tanto, \(V_{a,p}(k)\) es constante entre múltiplos consecutivos de \(P\). Tras la poda por relevancia, \(M(k)\) solo puede cambiar en la unión de los múltiplos de los períodos retenidos hasta \(\min(N,R)\). Esos enteros son los puntos de evento. Una vez ordenados, cada intervalo entre eventos consecutivos tiene valor constante de \(M(k)\).
Si \(M(k)=C\) para todo \(k \in [L,R]\), entonces la contribución completa de ese bloque es
$$C\sum_{k=L}^{R}(-1)^k.$$
La suma de signos tiene forma cerrada:
$$\sum_{k=L}^{R}(-1)^k= \begin{cases} 0, & R-L+1 \text{ es par},\\ 1, & R-L+1 \text{ es impar y } L \text{ es par},\\ -1, & R-L+1 \text{ es impar y } L \text{ es impar}. \end{cases}$$
Así, la suma total se acumula bloque a bloque. Solo en los puntos de evento hace falta recalcular exactamente el máximo.
Los primeros candidatos útiles son
$$a=2,\ p=2:\quad (1,2,4),\qquad V_{2,2}(k)=7\left\lfloor \frac{k}{4} \right\rfloor,$$
$$a=2,\ p=3:\quad (1,2,4,8),\qquad V_{2,3}(k)=15\left\lfloor \frac{k}{8} \right\rfloor,$$
$$a=3,\ p=2:\quad (4,6,9),\qquad V_{3,2}(k)=19\left\lfloor \frac{k}{9} \right\rfloor.$$
Hasta \(12\), los puntos de evento son \(4,8,9,12\). Por tanto,
$$\begin{aligned} 4 \le k \le 7&:&&M(k)=7,\\ 8 \le k \le 8&:&&M(k)=14,\\ 9 \le k \le 11&:&&M(k)=19,\\ 12 \le k \le 12&:&&M(k)=21. \end{aligned}$$
En particular, \(M(4)=7\), \(M(10)=19\) y \(M(12)=21\). La suma alternante hasta \(12\) es
$$A(12)=0+14-19+21=16,$$
porque el bloque \([4,7]\) tiene longitud par y aporta \(0\). Ese es exactamente el tipo de compresión por bloques que aprovecha la implementación a gran escala.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero determinan todos los exponentes posibles \(p\) con \(2^p \le N\) y, para cada uno, limitan el rango de búsqueda de \(a\) mediante raíces enteras. Después van elevando el valor récord actual de \(\Delta\) y usan búsqueda binaria para hallar, en cada familia de exponente fijo, la base más pequeña \(a\) que lo supera. Entre esos aspirantes, se conserva el que tiene el menor período \(a^p\), que pasa a ser el siguiente punto de la frontera de récords.
Luego las implementaciones comparan cada par de candidatos retenidos y asignan a cada uno un límite de relevancia usando la desigualdad del Paso 4. A continuación generan todos los puntos de evento enumerando los múltiplos de cada período retenido hasta el menor valor entre el límite global y la relevancia de ese candidato. La lista se ordena y se eliminan duplicados.
Finalmente, hacen un barrido desde \(4\) hasta \(N\). Entre dos puntos de evento sucesivos el valor máximo permanece constante, así que el código añade \(0\), el valor del bloque o su negación según la regla de paridad. En un punto de evento se recalcula el máximo exacto entre los candidatos que siguen siendo relevantes. La versión en C++ usa aritmética entera amplia y multiprecisión solo donde hace falta evitar desbordamientos; Python se apoya de forma natural en enteros de precisión arbitraria; Java usa enteros grandes cuando el cálculo del cruce lo requiere.
Sea \(C\) el número de candidatos récord retenidos y \(E\) el número de puntos de evento distintos. Con \(P_{\max}=\lfloor \log_2 N \rfloor\), la construcción de la frontera de récords está dominada por unas \(C\) extracciones repartidas entre esas familias de exponentes, con búsquedas binarias sobre el rango admisible de la base. El cálculo por parejas de las relevancias cuesta \(O(C^2)\). La generación de eventos cuesta \(O(E)\) inserciones y \(O(E \log E)\) para ordenar y eliminar repeticiones. El barrido final es \(O(E \cdot C)\) en el peor caso, porque un recálculo en un punto de evento puede inspeccionar todos los candidatos retenidos, aunque en la práctica las cotas de relevancia reducen mucho el conjunto activo. La memoria usada es \(O(C+E)\).
对每个 \(k \ge 4\)，记 \(M(k)\) 为满足下列条件的整数几何级数的最大可能和：项数至少为三项，公比大于 \(1\)，所有项都是正整数，且最大项不超过 \(k\)。最终要求的是交错和
$$A(N)=\sum_{k=4}^{N}(-1)^k M(k).$$
真正的输入规模极大，所以既不能把所有候选几何级数暴力枚举出来，也不能把 \(M(k)\) 从 \(4\) 到 \(N\) 逐点计算。可行的方法必须同时压缩两个维度：一是“哪些几何级数值得保留”，二是“最大值到底只会在哪些位置发生变化”。
这三份实现都建立在同一个数学化简上：先把任意合法的整数几何级数写成统一参数形式，再去掉永远不可能成为最优的候选，最后利用“长区间上最大值保持不变”的性质按块计算交错和。
设一个几何级数共有 \(p+1\) 项，其中 \(p \ge 2\)。公比写成最简分数 \(a/b\)，满足 \(a > b \ge 1\) 且 \(\gcd(a,b)=1\)。因为所有项都必须是整数，这个级数一定可以写成
$$q b^p,\ q a b^{p-1},\ q a^2 b^{p-2},\ \dots,\ q a^p,$$
其中 \(q \ge 1\) 是整数缩放因子。最大的那一项是 \(q a^p\)，而总和是
$$q\sum_{i=0}^{p} a^i b^{p-i}=q\,\frac{a^{p+1}-b^{p+1}}{a-b}.$$
因此，在给定上界 \(k\) 的情况下，同一组 \((a,b,p)\) 所允许的最佳缩放因子就是
$$q=\left\lfloor \frac{k}{a^p} \right\rfloor.$$
在 \(a\)、\(p\)、\(q\) 固定时，
$$q\sum_{i=0}^{p} a^i b^{p-i}$$
会随着 \(b\) 的增大而严格增大，因为其中所有含有 \(b\) 的项都会变大。又由于 \(b\) 只能满足 \(1 \le b < a\)，所以最优选择总是
$$b=a-1.$$
于是只需要考虑如下形状的几何级数：
$$q(a-1)^p,\ q a (a-1)^{p-1},\ \dots,\ q a^p.$$
把它对应的“周期阈值”和“单次提升量”记为
$$P(a,p)=a^p,\qquad \Delta(a,p)=a^{p+1}-(a-1)^{p+1}.$$
那么对固定的 \(k\)，该候选给出的和就是
$$V_{a,p}(k)=\left\lfloor \frac{k}{P(a,p)} \right\rfloor \Delta(a,p).$$
因此最大值函数可以写成
$$M(k)=\max_{a \ge 2,\ p \ge 2} V_{a,p}(k).$$
如果两个候选满足
$$P_1 \le P_2,\qquad \Delta_1 \ge \Delta_2,$$
那么对任意 \(k\) 都有
$$\left\lfloor \frac{k}{P_1} \right\rfloor \Delta_1 \ge \left\lfloor \frac{k}{P_2} \right\rfloor \Delta_2,$$
也就是说，第二个候选永远不可能优于第一个。于是实现不会保留所有候选，而只保留“纪录前沿”：每当 \(\Delta\) 提高到一个新纪录时，只保留达到这个新纪录所需的最小 \(P\)。因为必须有 \(a^p \le N\)，所以指数 \(p\) 只需要枚举到 \(\lfloor \log_2 N \rfloor\)，而对每个固定的 \(p\)，下一个纪录候选都可以通过对 \(a\) 做二分查找得到。
即使在纪录前沿上，也有很多候选只会在有限的 \(k\) 范围内起作用。若候选 \(j\) 的渐近斜率比候选 \(i\) 更大，即
$$\frac{\Delta_j}{P_j} > \frac{\Delta_i}{P_i} \iff \Delta_j P_i > \Delta_i P_j,$$
那么有下界和上界
$$V_j(k)\ge \left(\frac{k}{P_j}-1\right)\Delta_j,\qquad V_i(k)\le \frac{k}{P_i}\Delta_i.$$
因此当
$$\left(\frac{k}{P_j}-1\right)\Delta_j > \frac{k}{P_i}\Delta_i$$
成立时，候选 \(j\) 就一定比候选 \(i\) 更优。化简可得充分条件
$$k > \frac{\Delta_j P_j P_i}{\Delta_j P_i-\Delta_i P_j}.$$
实现会对每个候选，在所有更强竞争者中取这个上界的最小值，得到一个严格证明过的有效上界 \(R\)。一旦 \(k > R\)，该候选就再也不可能取得最大值。
对于单个固定候选，\(\left\lfloor k/P \right\rfloor\) 只有在 \(k\) 到达 \(P\) 的倍数时才会改变。因此 \(V_{a,p}(k)\) 在相邻两个倍数之间是常数。做完有效上界剪枝后，\(M(k)\) 也只能在保留周期 \(P\) 的倍数处改变，而且只需保留到 \(\min(N,R)\) 为止。把所有这样的整数收集起来，就是事件点。排序之后，相邻两个事件点之间的整个区间上，\(M(k)\) 都保持不变。
如果在区间 \(k \in [L,R]\) 上都有 \(M(k)=C\)，那么这一整块的贡献就是
$$C\sum_{k=L}^{R}(-1)^k.$$
内部符号和有简单闭式：
$$\sum_{k=L}^{R}(-1)^k= \begin{cases} 0, & R-L+1 \text{ 为偶数},\\ 1, & R-L+1 \text{ 为奇数且 } L \text{ 为偶数},\\ -1, & R-L+1 \text{ 为奇数且 } L \text{ 为奇数}. \end{cases}$$
这意味着总和不需要逐项相加，而是可以对每个常值块一次性结算。只有在真正的事件点上，才需要重新计算一次当前的最大值。
最先出现的几个有用候选是
$$a=2,\ p=2:\quad (1,2,4),\qquad V_{2,2}(k)=7\left\lfloor \frac{k}{4} \right\rfloor,$$
$$a=2,\ p=3:\quad (1,2,4,8),\qquad V_{2,3}(k)=15\left\lfloor \frac{k}{8} \right\rfloor,$$
$$a=3,\ p=2:\quad (4,6,9),\qquad V_{3,2}(k)=19\left\lfloor \frac{k}{9} \right\rfloor.$$
在 \(12\) 以内，事件点是 \(4,8,9,12\)。所以
$$\begin{aligned} 4 \le k \le 7&:&&M(k)=7,\\ 8 \le k \le 8&:&&M(k)=14,\\ 9 \le k \le 11&:&&M(k)=19,\\ 12 \le k \le 12&:&&M(k)=21. \end{aligned}$$
特别地，\(M(4)=7\)，\(M(10)=19\)，\(M(12)=21\)。于是
$$A(12)=0+14-19+21=16,$$
因为区间 \([4,7]\) 长度为偶数，对交错和的净贡献正好是 \(0\)。这正是完整程序在大输入上使用的分块思路。
C++、Python 和 Java 三份实现采用同一条流水线。首先，它们枚举所有满足 \(2^p \le N\) 的指数 \(p\)，并用整数根来给每个指数对应的底数 \(a\) 建立有效搜索上界。然后它们逐步提高当前纪录的 \(\Delta\) 值，对每个固定指数族使用二分查找找到第一个能超过该纪录的底数 \(a\)。在这些候选里，保留周期 \(a^p\) 最小的那个，作为纪录前沿上的下一个候选。
接下来，三份实现会两两比较这些保留下来的候选，并利用步骤 4 的不等式给每个候选分配一个有效上界。然后它们生成事件点集合：对每个候选，把其周期的所有倍数列出来，直到达到全局上限与该候选有效上界中的较小者。最后对这些事件点排序并去重。
最终的扫描从 \(4\) 开始一直到 \(N\)。在相邻两个事件点之间，最大和保持不变，所以程序根据奇偶规则一次加入 \(0\)、当前块值或其相反数。遇到事件点时，程序才在仍然有效的候选中重新求一次精确最大值。C++ 版本只在可能溢出的地方使用更宽的整数和高精度整数；Python 天然依赖任意精度整数；Java 在需要处理交叉边界时使用大整数。
记保留下来的纪录候选数为 \(C\)，不同事件点数为 \(E\)，并记 \(P_{\max}=\lfloor \log_2 N \rfloor\)。建立纪录前沿的预处理，主要由这 \(P_{\max}\) 个指数族上的若干次纪录提取和相应的二分查找组成。两两计算有效上界的复杂度是 \(O(C^2)\)。生成事件点需要 \(O(E)\) 次插入，以及 \(O(E \log E)\) 的排序与去重。最后的扫描在最坏情况下是 \(O(E \cdot C)\)，因为每次事件点重算都可能检查全部保留候选；不过有效上界会显著缩小实际活跃候选集。空间复杂度为 \(O(C+E)\)。
Для каждого \(k \ge 4\) обозначим через \(M(k)\) максимально возможную сумму геометрической прогрессии из положительных целых чисел, содержащей не менее трёх членов, имеющей знаменатель больше \(1\), и с наибольшим членом не больше \(k\). Требуется вычислить знакопеременную сумму
$$A(N)=\sum_{k=4}^{N}(-1)^k M(k).$$
Реальное значение \(N\) настолько велико, что нельзя ни перебрать все целочисленные геометрические прогрессии, ни считать \(M(k)\) по одному значению \(k\). Поэтому решение сжимает и семейство существенных кандидатов, и множество точек, где максимум вообще может измениться.
Все три реализации опираются на одну и ту же схему: сначала каждая допустимая целочисленная геометрическая прогрессия приводится к канонической параметризации, затем удаляются кандидаты, которые никогда не смогут стать оптимальными, и наконец сумма вычисляется по блокам, на которых максимум постоянен.
Рассмотрим геометрическую прогрессию из \(p+1\) членов, где \(p \ge 2\), с отношением \(a/b\) в несократимом виде и \(a > b \ge 1\). Поскольку все члены должны быть целыми, такая прогрессия имеет вид
$$q b^p,\ q a b^{p-1},\ q a^2 b^{p-2},\ \dots,\ q a^p,$$
где \(q \ge 1\) является целым масштабом. Наибольший член равен \(q a^p\), а сумма равна
$$q\sum_{i=0}^{p} a^i b^{p-i}=q\,\frac{a^{p+1}-b^{p+1}}{a-b}.$$
Значит, при фиксированных \(a\), \(b\) и \(p\) лучший допустимый масштаб при ограничении \(k\) равен
$$q=\left\lfloor \frac{k}{a^p} \right\rfloor.$$
При фиксированных \(a\), \(p\) и \(q\) величина
$$q\sum_{i=0}^{p} a^i b^{p-i}$$
строго возрастает по \(b\), потому что каждый член с показателем \(p-i > 0\) увеличивается при увеличении \(b\). Поскольку \(b\) должно удовлетворять \(1 \le b < a\), оптимальный выбор всегда
$$b=a-1.$$
Следовательно, достаточно рассматривать только прогрессии вида
$$q(a-1)^p,\ q a (a-1)^{p-1},\ \dots,\ q a^p.$$
Их верхний порог и приращение обозначим так:
$$P(a,p)=a^p,\qquad \Delta(a,p)=a^{p+1}-(a-1)^{p+1}.$$
Тогда вклад такого кандидата при фиксированном \(k\) равен
$$V_{a,p}(k)=\left\lfloor \frac{k}{P(a,p)} \right\rfloor \Delta(a,p),$$
и потому
$$M(k)=\max_{a \ge 2,\ p \ge 2} V_{a,p}(k).$$
Если для двух кандидатов выполняется
$$P_1 \le P_2,\qquad \Delta_1 \ge \Delta_2,$$
то для любого \(k\)
$$\left\lfloor \frac{k}{P_1} \right\rfloor \Delta_1 \ge \left\lfloor \frac{k}{P_2} \right\rfloor \Delta_2,$$
то есть второй кандидат никогда не сможет стать оптимальным. Поэтому реализации строят только фронт рекордов: как только величина \(\Delta\) возрастает, сохраняется минимальный возможный период \(P\), дающий новый рекорд. Так как \(a^p \le N\), показатель \(p\) достаточно рассматривать лишь до \(\lfloor \log_2 N \rfloor\), а следующий рекорд при фиксированном \(p\) находится бинарным поиском по \(a\).
Даже среди рекордных кандидатов многие важны только на конечном диапазоне \(k\). Если кандидат \(j\) имеет лучшую асимптотическую плотность, чем кандидат \(i\), то есть
$$\frac{\Delta_j}{P_j} > \frac{\Delta_i}{P_i} \iff \Delta_j P_i > \Delta_i P_j,$$
то выполняются оценки
$$V_j(k)\ge \left(\frac{k}{P_j}-1\right)\Delta_j,\qquad V_i(k)\le \frac{k}{P_i}\Delta_i.$$
Отсюда кандидат \(j\) гарантированно превосходит \(i\), когда
$$\left(\frac{k}{P_j}-1\right)\Delta_j > \frac{k}{P_i}\Delta_i,$$
то есть
$$k > \frac{\Delta_j P_j P_i}{\Delta_j P_i-\Delta_i P_j}.$$
Для каждого рекордного кандидата реализации берут минимум таких границ по всем более сильным соперникам. Получается доказанная верхняя релевантность \(R\): при \(k > R\) данный кандидат уже никогда не сможет дать максимум.
Для фиксированного кандидата значение \(\left\lfloor k/P \right\rfloor\) изменяется только тогда, когда \(k\) достигает очередного кратного \(P\). Значит, \(V_{a,p}(k)\) постоянно между соседними кратными \(P\). После отсечения по релевантности функция \(M(k)\) может изменяться только на объединении кратных сохранённых периодов \(P\) вплоть до \(\min(N,R)\). Эти числа и образуют точки событий. После сортировки этой совокупности на каждом промежутке между соседними событиями значение \(M(k)\) постоянно.
Если на всём отрезке \(k \in [L,R]\) выполняется \(M(k)=C\), то вклад блока равен
$$C\sum_{k=L}^{R}(-1)^k.$$
Внутренняя сумма знаков имеет простой вид:
$$\sum_{k=L}^{R}(-1)^k= \begin{cases} 0, & R-L+1 \text{ чётно},\\ 1, & R-L+1 \text{ нечётно и } L \text{ чётно},\\ -1, & R-L+1 \text{ нечётно и } L \text{ нечётно}. \end{cases}$$
Следовательно, всю сумму можно накапливать по блокам. Точное пересчитывание максимума нужно только в самих точках событий.
Первые полезные кандидаты таковы:
$$a=2,\ p=2:\quad (1,2,4),\qquad V_{2,2}(k)=7\left\lfloor \frac{k}{4} \right\rfloor,$$
$$a=2,\ p=3:\quad (1,2,4,8),\qquad V_{2,3}(k)=15\left\lfloor \frac{k}{8} \right\rfloor,$$
$$a=3,\ p=2:\quad (4,6,9),\qquad V_{3,2}(k)=19\left\lfloor \frac{k}{9} \right\rfloor.$$
До \(12\) точки событий равны \(4,8,9,12\). Поэтому
$$\begin{aligned} 4 \le k \le 7&:&&M(k)=7,\\ 8 \le k \le 8&:&&M(k)=14,\\ 9 \le k \le 11&:&&M(k)=19,\\ 12 \le k \le 12&:&&M(k)=21. \end{aligned}$$
В частности, \(M(4)=7\), \(M(10)=19\), \(M(12)=21\). Тогда
$$A(12)=0+14-19+21=16,$$
поскольку блок \([4,7]\) имеет чётную длину и даёт нулевой вклад. Именно такую блочную компрессию используют реализации и для полного входа.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала они перечисляют все возможные показатели \(p\), для которых \(2^p \le N\), и с помощью целочисленных корней ограничивают диапазон поиска по основанию \(a\) для каждого такого показателя. Затем текущий рекорд по величине \(\Delta\) постепенно повышается, и для каждой фиксированной семьи по \(p\) бинарным поиском находится минимальное основание \(a\), которое этот рекорд превосходит. Среди таких претендентов сохраняется тот, у которого период \(a^p\) минимален; он и становится следующим кандидатом на фронте рекордов.
После этого реализации попарно сравнивают сохранённые кандидаты и присваивают каждому верхнюю границу релевантности, используя неравенство из шага 4. Далее они строят список точек событий: перечисляют кратные каждого сохранённого периода до минимума из глобального ограничения и границы релевантности данного кандидата, затем сортируют список и удаляют повторы.
На последнем этапе выполняется проход от \(4\) до \(N\). Между соседними точками событий максимальная сумма постоянна, поэтому код добавляет либо \(0\), либо значение блока, либо его отрицание в зависимости от чётности. В самой точке события максимум заново вычисляется по всем ещё релевантным кандидатам. В версии C++ широкие целые и multiprecision используются только там, где возможен переполняющий промежуточный результат; Python естественно использует целые произвольной длины; Java применяет большие целые в расчёте границ пересечения.
Пусть \(C\) обозначает число сохранённых рекордных кандидатов, а \(E\) число различных точек событий. Обозначим также \(P_{\max}=\lfloor \log_2 N \rfloor\). Построение фронта рекордов определяется примерно \(C\) извлечениями рекордов по этим семействам показателей и бинарными поисками по допустимому диапазону основания. Попарный расчёт релевантности стоит \(O(C^2)\). Построение списка событий требует \(O(E)\) вставок и \(O(E \log E)\) на сортировку с удалением повторов. Финальный проход имеет оценку \(O(E \cdot C)\) в худшем случае, поскольку в точке события может потребоваться просмотр всех сохранённых кандидатов, хотя на практике границы релевантности существенно уменьшают активный набор. Память равна \(O(C+E)\).
لكل \(k \ge 4\)، لنرمز بـ \(M(k)\) إلى أكبر مجموع ممكن لمتتالية هندسية من أعداد صحيحة موجبة، فيها ثلاثة حدود على الأقل، ونسبتها المشتركة أكبر من \(1\)، وأكبر حد فيها لا يتجاوز \(k\). والمطلوب في النهاية هو المجموع المتناوب
$$A(N)=\sum_{k=4}^{N}(-1)^k M(k).$$
القيمة الحقيقية لـ \(N\) ضخمة جدا، لذلك لا يمكن تعداد جميع المتتاليات الهندسية الصحيحة الممكنة، ولا يمكن حساب \(M(k)\) لكل قيمة من \(4\) إلى \(N\) مباشرة. الفكرة الأساسية هي ضغط عائلة المرشحات نفسها، ثم ضغط المواضع التي يمكن أن يتغير عندها هذا العظمى.
البرامج الثلاثة تعتمد الاختزال نفسه: نكتب كل متتالية هندسية صحيحة صالحة في صورة معيارية، ثم نحذف كل مرشح لا يمكن أن يكون الأفضل أبدا، وبعد ذلك نحسب المجموع المتناوب على كتل تكون فيها القيمة العظمى ثابتة.
لنأخذ متتالية هندسية طولها \(p+1\) حيث \(p \ge 2\)، ونسبتها \(a/b\) في أبسط صورة مع \(a > b \ge 1\). بما أن كل الحدود يجب أن تكون أعدادا صحيحة، فإن المتتالية تأخذ الصورة
$$q b^p,\ q a b^{p-1},\ q a^2 b^{p-2},\ \dots,\ q a^p,$$
حيث \(q \ge 1\) عامل تكبير صحيح. أكبر حد هو \(q a^p\)، أما المجموع فهو
$$q\sum_{i=0}^{p} a^i b^{p-i}=q\,\frac{a^{p+1}-b^{p+1}}{a-b}.$$
إذن عند تثبيت \(a\) و\(b\) و\(p\)، فإن أفضل قيمة مسموحة لـ \(q\) تحت القيد \(k\) هي
$$q=\left\lfloor \frac{k}{a^p} \right\rfloor.$$
إذا ثبتنا \(a\) و\(p\) و\(q\)، فإن الكمية
$$q\sum_{i=0}^{p} a^i b^{p-i}$$
تزداد بازدياد \(b\)، لأن كل حد يحتوي على قوة موجبة من \(b\) يكبر عندما تكبر \(b\). وبما أن \(b\) يجب أن يحقق \(1 \le b < a\)، فإن أفضل اختيار ممكن هو دائما
$$b=a-1.$$
لذلك يكفي النظر فقط إلى المتتاليات من الشكل
$$q(a-1)^p,\ q a (a-1)^{p-1},\ \dots,\ q a^p.$$
ونعرّف حدها الأعلى ومقدار القفزة المقابلة لها بـ
$$P(a,p)=a^p,\qquad \Delta(a,p)=a^{p+1}-(a-1)^{p+1}.$$
وعند قيمة ثابتة لـ \(k\)، فإن مساهمة هذا المرشح تساوي
$$V_{a,p}(k)=\left\lfloor \frac{k}{P(a,p)} \right\rfloor \Delta(a,p).$$
ومن ثم
$$M(k)=\max_{a \ge 2,\ p \ge 2} V_{a,p}(k).$$
إذا كان لدينا مرشحان يحققان
$$P_1 \le P_2,\qquad \Delta_1 \ge \Delta_2,$$
فإنه لكل \(k\) نحصل على
$$\left\lfloor \frac{k}{P_1} \right\rfloor \Delta_1 \ge \left\lfloor \frac{k}{P_2} \right\rfloor \Delta_2,$$
وبالتالي لا يمكن للمرشح الثاني أن يكون الأفضل أبدا. لهذا السبب تبني البرامج فقط جبهة الأرقام القياسية: كلما ارتفعت قيمة \(\Delta\) إلى مستوى جديد، نحتفظ بأصغر فترة \(P\) تحقق هذا المستوى الجديد. وبما أن \(a^p \le N\)، فلا حاجة إلى أسس أكبر من \(\lfloor \log_2 N \rfloor\)، ولكل أس ثابت يمكن إيجاد المرشح القياسي التالي ببحث ثنائي على \(a\).
حتى بين المرشحات القياسية نفسها، كثير من المرشحات يكون مفيدا فقط على مجال منته من قيم \(k\). إذا كان المرشح \(j\) أفضل من المرشح \(i\) من حيث الميل التقاربي، أي
$$\frac{\Delta_j}{P_j} > \frac{\Delta_i}{P_i} \iff \Delta_j P_i > \Delta_i P_j,$$
فإن لدينا التقديرين
$$V_j(k)\ge \left(\frac{k}{P_j}-1\right)\Delta_j,\qquad V_i(k)\le \frac{k}{P_i}\Delta_i.$$
إذن يضمن المرشح \(j\) التفوق على \(i\) عندما
$$\left(\frac{k}{P_j}-1\right)\Delta_j > \frac{k}{P_i}\Delta_i,$$
وهذا يكافئ
$$k > \frac{\Delta_j P_j P_i}{\Delta_j P_i-\Delta_i P_j}.$$
تأخذ البرامج أصغر حد من هذا النوع على جميع المنافسين الأقوى، وبذلك تحصل لكل مرشح على حد علوي مثبت نسميه \(R\). بعد أن يصبح \(k > R\)، لا يمكن لذلك المرشح أن يحقق القيمة العظمى مرة أخرى.
بالنسبة إلى مرشح ثابت، فإن \(\left\lfloor k/P \right\rfloor\) لا تتغير إلا عندما يصل \(k\) إلى مضاعف جديد لـ \(P\). لذلك تكون \(V_{a,p}(k)\) ثابتة بين مضاعفين متتاليين لـ \(P\). وبعد تقليم حد الفعالية، لا يمكن أن تتغير \(M(k)\) إلا عند اتحاد مضاعفات الفترات المحتفظ بها حتى \(\min(N,R)\). هذه الأعداد هي نقاط الأحداث. وبعد جمعها وترتيبها، تصبح \(M(k)\) ثابتة على كل فترة بين نقطتي حدث متتاليتين.
إذا كانت \(M(k)=C\) لكل \(k \in [L,R]\)، فإن مساهمة هذه الكتلة كلها هي
$$C\sum_{k=L}^{R}(-1)^k.$$
ومجموع الإشارات له صيغة مغلقة بسيطة:
$$\sum_{k=L}^{R}(-1)^k= \begin{cases} 0, & R-L+1 \equiv 0 \pmod 2,\\ (-1)^L, & R-L+1 \equiv 1 \pmod 2. \end{cases}$$
أي أن الكتلة الزوجية الطول تعطي صفرا، أما الكتلة الفردية الطول فتعطي \(1\) إذا كان \(L\) زوجيا وتعطي \(-1\) إذا كان \(L\) فرديا. وهكذا يمكن تجميع النتيجة كتلة بعد كتلة، ولا نعيد حساب العظمى بدقة إلا عند نقاط الأحداث نفسها.
أول المرشحات المفيدة هي
$$a=2,\ p=2:\quad (1,2,4),\qquad V_{2,2}(k)=7\left\lfloor \frac{k}{4} \right\rfloor,$$
$$a=2,\ p=3:\quad (1,2,4,8),\qquad V_{2,3}(k)=15\left\lfloor \frac{k}{8} \right\rfloor,$$
$$a=3,\ p=2:\quad (4,6,9),\qquad V_{3,2}(k)=19\left\lfloor \frac{k}{9} \right\rfloor.$$
حتى \(12\)، تكون نقاط الأحداث هي \(4,8,9,12\). لذلك نحصل على
$$\begin{aligned} 4 \le k \le 7&:&&M(k)=7,\\ 8 \le k \le 8&:&&M(k)=14,\\ 9 \le k \le 11&:&&M(k)=19,\\ 12 \le k \le 12&:&&M(k)=21. \end{aligned}$$
وبصورة خاصة، \(M(4)=7\)، و\(M(10)=19\)، و\(M(12)=21\). ومن ثم
$$A(12)=0+14-19+21=16,$$
لأن الكتلة \([4,7]\) طولها زوجي، فيكون صافي مساهمتها صفرا. هذه هي بالضبط فكرة الضغط على الكتل التي تعتمدها البرامج في الحالة الكاملة.
تتبع تطبيقات C++ وPython وJava السلسلة نفسها من الخطوات. أولا تحدد جميع الأسس الممكنة \(p\) التي تحقق \(2^p \le N\)، ثم تستخدم الجذور الصحيحة لوضع حد أعلى لنطاق البحث عن \(a\) لكل أس. بعد ذلك ترفع قيمة الرقم القياسي الحالي لـ \(\Delta\) تدريجيا، وتستعمل بحثا ثنائيا لإيجاد أصغر أساس \(a\) يتجاوزه في كل عائلة ذات أس ثابت. ومن بين هذه المرشحات يتم الاحتفاظ بالمرشح ذي الفترة الأصغر \(a^p\)، لأنه يمثل المرشح القياسي التالي على الجبهة.
بعد ذلك تقارن البرامج كل زوج من المرشحات المحتفظ بها، وتخصص لكل واحد منها حدا علويا للفعالية باستخدام المتباينة الواردة في الخطوة 4. ثم تبني قائمة نقاط الأحداث عبر تعداد مضاعفات كل فترة محتفظ بها حتى أصغر القيمتين: الحد العام وحد الفعالية لذلك المرشح. بعدها تُرتب القائمة وتُحذف التكرارات.
في النهاية يجري المسح من \(4\) حتى \(N\). وبين نقطتي حدث متتاليتين تبقى القيمة العظمى ثابتة، لذلك يضيف الكود \(0\) أو قيمة الكتلة أو سالبها وفقا لقاعدة الزوجية. وعند نقطة الحدث يعيد حساب العظمى بدقة بين المرشحات التي ما زالت ضمن مجال الفعالية. تستخدم نسخة C++ حسابا صحيحا عريضا ودقة عالية فقط في المواضع التي قد يحدث فيها فيض؛ وتعتمد Python طبيعيا على الأعداد الصحيحة ذات الدقة غير المحدودة؛ وتستخدم Java الأعداد الصحيحة الكبيرة عندما يتطلب حساب حدود التقاطع ذلك.
لنرمز بعدد المرشحات القياسية المحتفظ بها بـ \(C\)، وبعدد نقاط الأحداث المختلفة بـ \(E\)، ولتكن \(P_{\max}=\lfloor \log_2 N \rfloor\). بناء جبهة الأرقام القياسية تحكمه نحو \(C\) عمليات استخراج موزعة على عائلات الأسس هذه، مع بحوث ثنائية داخل مجال الأساس المسموح. أما حساب حدود الفعالية على جميع الأزواج فيكلف \(O(C^2)\). وتوليد نقاط الأحداث يحتاج إلى \(O(E)\) إدراجات و\(O(E \log E)\) للترتيب وإزالة التكرار. أما المسح النهائي فتكلفته في أسوأ الأحوال \(O(E \cdot C)\)، لأن إعادة الحساب عند نقطة حدث قد تفحص جميع المرشحات المحتفظ بها، وإن كانت حدود الفعالية تجعل المجموعة الفعالة أصغر بكثير عمليا. واستهلاك الذاكرة هو \(O(C+E)\).