Let \(F(N)\) be the maximum number of lattice points inside an \(N \times N\) square that can lie on the graph of one strictly convex increasing function. If the graph passes through \(k+1\) lattice points, then those points determine \(k\) consecutive step vectors. The task is to evaluate \(F(10^{18})\), but the derivation below works for general \(N\).
Write the selected lattice points in increasing \(x\)-order as \(P_0,P_1,\dots,P_k\). For each consecutive pair define the step vector
$$P_i-P_{i-1}=(a_i,b_i).$$
Because the graph is increasing, every step satisfies \(a_i\gt 0\) and \(b_i\gt 0\). The entire problem becomes: how many such steps can we choose while preserving strict convexity and staying inside the square?
Strict convexity means the slopes of consecutive chords are strictly increasing:
$$\frac{b_1}{a_1} \lt \frac{b_2}{a_2} \lt \cdots \lt \frac{b_k}{a_k}.$$
The horizontal and vertical spans must both fit into the square, so
$$\sum_{i=1}^{k} a_i \le N,\qquad \sum_{i=1}^{k} b_i \le N.$$
Adding the two inequalities gives the global \(L_1\) budget
$$\sum_{i=1}^{k}(a_i+b_i)\le 2N.$$
Each extra segment increases the number of lattice points by exactly \(1\), so maximizing points is equivalent to maximizing the number of admissible step vectors.
If a step \((a,b)\) has \(d=\gcd(a,b)\gt 1\), then the reduced vector \((a/d,b/d)\) has the same slope but strictly smaller cost \((a+b)/d\). Since equal slopes cannot repeat on a strictly convex chain, a non-primitive step is never preferable to its primitive version. Therefore an optimal construction may be assumed to use only primitive vectors:
$$\gcd(a_i,b_i)=1.$$
Now fix
$$s=a+b.$$
Every primitive vector in that layer has the form \((a,s-a)\) with \(1\le a\le s-1\) and
$$\gcd(a,s)=1.$$
The number of such choices is exactly Euler's totient:
$$\#\{a:1\le a\le s-1,\ \gcd(a,s)=1\}=\varphi(s).$$
All primitive vectors with the same value of \(a+b=s\) form one layer. Every vector in that layer contributes one segment and costs \(s\) units of \(L_1\) budget.
The layer is symmetric because \((a,s-a)\) is primitive if and only if \((s-a,a)\) is primitive. Pairing those two vectors gives equal total contribution in the \(x\)- and \(y\)-directions, so
$$\sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} a = \sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} (s-a) = \frac{s\varphi(s)}{2}.$$
Therefore taking the whole layer uses total cost
$$s\varphi(s),$$
and that cost is split evenly between horizontal and vertical motion. This is the key reason the two-dimensional square constraint collapses to an \(L_1\)-budget problem for complete layers.
Each available segment is worth one more lattice point, but a segment from layer \(s\) costs \(s\). Hence the cheapest segments always come from the smallest remaining \(s\), so the optimal count is obtained by taking layers in increasing order.
Define the prefix segment count and prefix cost by
$$\Phi(m)=\sum_{s=2}^{m}\varphi(s),\qquad C(m)=\sum_{s=2}^{m}s\varphi(s).$$
Let \(m\) be the largest integer such that
$$C(m)\le 2N.$$
Then all layers \(2,3,\dots,m\) are taken completely, contributing \(\Phi(m)\) segments. The next candidate layer is
$$s=m+1.$$
With remaining budget
$$R=2N-C(m),$$
the raw number of extra segments available from that next layer is
$$t=\left\lfloor\frac{R}{s}\right\rfloor,\qquad r=R\bmod s.$$
So the default segment count is \(\Phi(m)+t\), and the default point count is \(\Phi(m)+t+1\).
When \(r\gt 0\), there is still slack after choosing \(t\) vectors from the final layer, and the implementations treat that situation as feasible. The only time a correction is needed is
$$r=0,\qquad t\equiv 1\pmod{2}.$$
In that case the lower complete layers are already perfectly balanced, and the last layer must balance itself exactly:
$$\sum a=\sum b=\frac{ts}{2}.$$
If \(t\) is even, we can use complementary pairs \((a,s-a)\) and \((s-a,a)\), so balancing is automatic.
If \(t=1\), balancing is impossible.
If \(s\equiv 0\pmod{4}\), balancing is also impossible. Every admissible \(a\) is odd, so the sum of an odd number of such terms is odd, while \(ts/2\) is even.
The remaining case is \(s\equiv 2\pmod{4}\), so \(s=2n\) with \(n\) odd. Any larger odd balanced subset can then be written as one balanced triple together with complementary pairs. So the question reduces to whether there exist three integers coprime to \(s\) whose sum is \(3s/2\). The implementation checks exactly that condition and subtracts one segment if it fails.
Here the total budget is
$$2N=200.$$
The prefix costs of the early layers are
$$\begin{aligned} C(2)&=2,\\ C(3)&=8,\\ C(4)&=16,\\ C(5)&=36,\\ C(6)&=48,\\ C(7)&=90,\\ C(8)&=122,\\ C(9)&=176. \end{aligned}$$
But \(C(10)=216\gt 200\), so the last complete layer is \(m=9\). The complete layers contribute
$$\Phi(9)=\varphi(2)+\varphi(3)+\cdots+\varphi(9)=1+2+2+4+2+6+4+6=27$$
segments. The remaining budget is
$$R=200-176=24.$$
The next layer is \(s=10\), hence
$$t=\left\lfloor\frac{24}{10}\right\rfloor=2,\qquad r=4.$$
No correction is needed because \(r\ne 0\). Therefore
$$F(100)=27+2+1=30,$$
matching the checkpoint used by the C++, Python, and Java implementations.
The implementation first sieves Euler's totient function up to a cutoff large enough that the prefix cost \(C(m)\) exceeds \(2\times 10^{18}\). From those totients it builds two prefix arrays: one for \(\Phi(m)\) and one for \(C(m)\).
For a given \(N\), it binary-searches the largest \(m\) with \(C(m)\le 2N\). That immediately gives the number of complete layers and the remaining budget \(R\).
Next it computes \(t=\lfloor R/(m+1)\rfloor\) and \(r=R\bmod (m+1)\). The default answer is the number of complete-layer segments plus \(t\), followed by one extra point for the starting lattice point.
Finally, if the remainder is zero and the last-layer count is odd, the implementation runs the balancing test from Step 5. In the impossible subcases it decreases the segment count by \(1\), then returns the number of lattice points.
If the sieve stops at \(L\), computing all totients up to \(L\) costs \(O(L\log\log L)\) time and \(O(L)\) memory. Building the prefix arrays is \(O(L)\). A query for \(F(N)\) then needs one binary search, a few arithmetic operations, and only a tiny extra check in the rare exact-saturation case.
Sei \(F(N)\) die maximale Anzahl von Gitterpunkten in einem \(N\times N\)-Quadrat, die auf dem Graphen einer einzigen streng konvexen, streng wachsenden Funktion liegen können. Enthält der Graph \(k+1\) Gitterpunkte, dann entstehen \(k\) aufeinanderfolgende Schrittvektoren. Gesucht ist \(F(10^{18})\), aber die Herleitung gilt für beliebiges \(N\).
Wir schreiben die gewählten Gitterpunkte in aufsteigender \(x\)-Reihenfolge als \(P_0,P_1,\dots,P_k\). Für jedes benachbarte Paar definieren wir den Schrittvektor
$$P_i-P_{i-1}=(a_i,b_i).$$
Weil der Graph wächst, gilt stets \(a_i\gt 0\) und \(b_i\gt 0\). Damit wird das geometrische Problem zu der Frage, wie viele solcher Schritte man unter den Konvexitäts- und Quadratbedingungen auswählen kann.
Strenge Konvexität bedeutet, dass die Steigungen aufeinanderfolgender Sehnen streng wachsen:
$$\frac{b_1}{a_1} \lt \frac{b_2}{a_2} \lt \cdots \lt \frac{b_k}{a_k}.$$
Die gesamte horizontale und vertikale Ausdehnung muss in das Quadrat passen, also
$$\sum_{i=1}^{k} a_i \le N,\qquad \sum_{i=1}^{k} b_i \le N.$$
Durch Addition erhält man das globale \(L_1\)-Budget
$$\sum_{i=1}^{k}(a_i+b_i)\le 2N.$$
Jeder zusätzliche Schritt erhöht die Zahl der Gitterpunkte um genau \(1\). Deshalb genügt es, die Anzahl zulässiger Schrittvektoren zu maximieren.
Hat ein Schritt \((a,b)\) den gemeinsamen Teiler \(d=\gcd(a,b)\gt 1\), dann besitzt der reduzierte Vektor \((a/d,b/d)\) dieselbe Steigung, aber die kleinere Kosten \((a+b)/d\). Da auf einer streng konvexen Kette dieselbe Steigung nicht mehrfach auftreten darf, ist ein nicht-primitiver Schritt niemals besser als seine primitive Version. Deshalb kann man optimal annehmen:
$$\gcd(a_i,b_i)=1.$$
Fixiere nun
$$s=a+b.$$
Jeder primitive Vektor in dieser Schicht hat die Form \((a,s-a)\) mit \(1\le a\le s-1\) und
$$\gcd(a,s)=1.$$
Die Anzahl solcher Möglichkeiten ist genau die Eulersche Phi-Funktion:
$$\#\{a:1\le a\le s-1,\ \gcd(a,s)=1\}=\varphi(s).$$
Alle primitiven Vektoren mit festem \(a+b=s\) bilden eine Schicht. Jeder dieser Vektoren liefert genau ein Segment und kostet \(s\) Einheiten des \(L_1\)-Budgets.
Die Schicht ist symmetrisch, denn \((a,s-a)\) ist genau dann primitiv, wenn auch \((s-a,a)\) primitiv ist. Durch Paarung dieser beiden Vektoren sind die Gesamtbeiträge in \(x\)- und \(y\)-Richtung gleich:
$$\sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} a = \sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} (s-a) = \frac{s\varphi(s)}{2}.$$
Eine volle Schicht verbraucht also insgesamt
$$s\varphi(s),$$
und genau die Hälfte davon entfällt auf die horizontale, die andere Hälfte auf die vertikale Bewegung. Dadurch reduziert sich die zweidimensionale Nebenbedingung für komplette Schichten auf ein eindimensionales Kostenbudget.
Jedes verfügbare Segment ist einen zusätzlichen Gitterpunkt wert, aber ein Segment aus der Schicht \(s\) kostet \(s\). Also stammen die billigsten Segmente immer aus der kleinsten noch verfügbaren Schicht, und man nimmt die Schichten der Reihe nach.
Definiere dazu die Präfixanzahl der Segmente und die Präfixkosten durch
$$\Phi(m)=\sum_{s=2}^{m}\varphi(s),\qquad C(m)=\sum_{s=2}^{m}s\varphi(s).$$
Sei \(m\) die größte ganze Zahl mit
$$C(m)\le 2N.$$
Dann kann man die Schichten \(2,3,\dots,m\) vollständig nehmen. Sie liefern \(\Phi(m)\) Segmente. Die nächste Kandidatenschicht ist
$$s=m+1.$$
Mit Restbudget
$$R=2N-C(m)$$
erhält man als rohe Zusatzanzahl
$$t=\left\lfloor\frac{R}{s}\right\rfloor,\qquad r=R\bmod s.$$
Damit ist die Standardzahl der Segmente \(\Phi(m)+t\), und die Standardzahl der Punkte ist \(\Phi(m)+t+1\).
Wenn \(r\gt 0\) gilt, bleibt nach der Wahl von \(t\) Vektoren aus der letzten Schicht noch Spielraum, und die Implementierungen behandeln diesen Fall als zulässig. Eine Korrektur ist nur nötig, wenn
$$r=0,\qquad t\equiv 1\pmod{2}.$$
Dann sind die unteren vollständigen Schichten bereits perfekt ausbalanciert, und die letzte Schicht muss sich selbst exakt ausgleichen:
$$\sum a=\sum b=\frac{ts}{2}.$$
Ist \(t\) gerade, lösen komplementäre Paare \((a,s-a)\) und \((s-a,a)\) das sofort.
Für \(t=1\) ist es unmöglich.
Für \(s\equiv 0\pmod{4}\) ist es ebenfalls unmöglich. Alle zulässigen \(a\) sind dann ungerade, also ist die Summe einer ungeraden Anzahl solcher Terme ungerade, während \(ts/2\) gerade ist.
Der verbleibende Fall ist \(s\equiv 2\pmod{4}\), also \(s=2n\) mit ungeradem \(n\). Jede größere ungerade balancierte Teilmenge lässt sich dann als ein balanciertes Tripel plus komplementäre Paare schreiben. Deshalb reduziert sich die Frage auf die Existenz von drei zu \(s\) teilerfremden Zahlen mit Summe \(3s/2\). Genau diese Bedingung prüft die Implementierung; falls sie scheitert, wird ein Segment abgezogen.
Hier ist das Gesamtbudget
$$2N=200.$$
Die Präfixkosten der ersten Schichten lauten
$$\begin{aligned} C(2)&=2,\\ C(3)&=8,\\ C(4)&=16,\\ C(5)&=36,\\ C(6)&=48,\\ C(7)&=90,\\ C(8)&=122,\\ C(9)&=176. \end{aligned}$$
Aber \(C(10)=216\gt 200\), also ist \(m=9\) die letzte vollständige Schicht. Diese vollständigen Schichten liefern
$$\Phi(9)=\varphi(2)+\varphi(3)+\cdots+\varphi(9)=1+2+2+4+2+6+4+6=27$$
Segmente. Das Restbudget ist
$$R=200-176=24.$$
Die nächste Schicht ist \(s=10\), also
$$t=\left\lfloor\frac{24}{10}\right\rfloor=2,\qquad r=4.$$
Weil \(r\ne 0\), ist keine Korrektur nötig. Daher
$$F(100)=27+2+1=30,$$
genau der Kontrollwert der C++-, Python- und Java-Implementierungen.
Die Implementierung siebt zunächst die Eulersche Phi-Funktion bis zu einer Grenze, die groß genug ist, damit die Präfixkosten \(C(m)\) über \(2\times 10^{18}\) hinausgehen. Aus diesen Werten entstehen zwei Präfixfelder: eines für \(\Phi(m)\) und eines für \(C(m)\).
Für ein gegebenes \(N\) wird per Binärsuche das größte \(m\) mit \(C(m)\le 2N\) bestimmt. Damit kennt man sofort die Zahl der vollständigen Schichten und das Restbudget \(R\).
Danach berechnet die Implementierung \(t=\lfloor R/(m+1)\rfloor\) und \(r=R\bmod (m+1)\). Die Standardantwort ist die Zahl der Segmente aus vollständigen Schichten plus \(t\), anschließend kommt noch \(1\) für den Startpunkt hinzu.
Falls der Rest null ist und die Zahl der Segmente in der letzten Schicht ungerade ist, führt der Code schließlich den Ausgleichstest aus Schritt 5 durch. In den unmöglichen Teilfällen reduziert er die Segmentzahl um \(1\) und gibt dann die Anzahl der Gitterpunkte zurück.
Stoppt das Sieb bei \(L\), dann kostet die Berechnung aller Totienten bis \(L\) insgesamt \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher. Der Aufbau der Präfixfelder ist \(O(L)\). Eine Abfrage für \(F(N)\) benötigt danach nur eine Binärsuche, einige arithmetische Operationen und höchstens einen sehr kleinen Zusatztest im seltenen Fall exakter Sättigung.
\(F(N)\), \(N\times N\) kare içinde tek bir sıkı konveks ve artan fonksiyonun grafiği üzerinde bulunabilecek en büyük kafes nokta sayısıdır. Grafik \(k+1\) kafes noktasından geçiyorsa arada \(k\) tane ardışık adım vektörü vardır. Amaç \(F(10^{18})\) değerini bulmaktır; aşağıdaki türetim ise genel \(N\) için geçerlidir.
Seçilen kafes noktalarını artan \(x\) sırasıyla \(P_0,P_1,\dots,P_k\) olarak yazalım. Ardışık iki nokta için adım vektörü
$$P_i-P_{i-1}=(a_i,b_i)$$
olsun. Grafik artan olduğu için her adımda \(a_i\gt 0\) ve \(b_i\gt 0\) olur. Böylece problem, kare içinde kalırken ve sıkı konveksliği korurken bu adımlardan kaç tane seçebileceğimiz sorusuna dönüşür.
Sıkı konvekslik, ardışık kirişlerin eğimlerinin kesin olarak artması demektir:
$$\frac{b_1}{a_1} \lt \frac{b_2}{a_2} \lt \cdots \lt \frac{b_k}{a_k}.$$
Toplam yatay ve dikey yayılım karenin içinde kalmalıdır; dolayısıyla
$$\sum_{i=1}^{k} a_i \le N,\qquad \sum_{i=1}^{k} b_i \le N.$$
Bu iki eşitsizliği toplarsak küresel \(L_1\) bütçesini elde ederiz:
$$\sum_{i=1}^{k}(a_i+b_i)\le 2N.$$
Her ek segment kafes nokta sayısını tam \(1\) artırdığı için amaç, uygun adım vektörü sayısını en büyük yapmaktır.
Eğer bir adım \((a,b)\) için \(d=\gcd(a,b)\gt 1\) ise, indirgenmiş \((a/d,b/d)\) vektörü aynı eğime sahiptir ama maliyeti \((a+b)/d\) kadar küçüktür. Sıkı konveks bir zincirde aynı eğim iki kez kullanılamayacağı için primitive olmayan bir adım, primitive sürümünden daha iyi olamaz. Bu yüzden optimal çözümde
$$\gcd(a_i,b_i)=1$$
varsayılabilir.
Şimdi
$$s=a+b$$
değerini sabitleyelim. Bu katmandaki her primitive vektör \((a,s-a)\) biçimindedir ve
$$1\le a\le s-1,\qquad \gcd(a,s)=1$$
şartlarını sağlar. Böyle seçimlerin sayısı tam olarak Euler totient fonksiyonudur:
$$\#\{a:1\le a\le s-1,\ \gcd(a,s)=1\}=\varphi(s).$$
Aynı \(a+b=s\) değerine sahip bütün primitive vektörler tek bir katman oluşturur. Bu katmandaki her vektör bir segment kazandırır ve \(L_1\) bütçesinden \(s\) birim harcar.
Katman simetriktir; çünkü \((a,s-a)\) primitive ise \((s-a,a)\) da primitive olur. Bu iki vektörü eşleyince yatay ve dikey toplam katkılar eşit çıkar:
$$\sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} a = \sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} (s-a) = \frac{s\varphi(s)}{2}.$$
Dolayısıyla tam bir katmanın toplam maliyeti
$$s\varphi(s)$$
olur ve bu maliyetin yarısı \(x\), yarısı \(y\) yönünde harcanır. Tam katmanlarda iki boyutlu kısıtın tek boyutlu maliyet hesabına dönüşmesinin nedeni budur.
Her segment yalnızca bir ek kafes noktası kazandırır, ama \(s\) katmanındaki bir segmentin maliyeti \(s\)'dir. Bu nedenle en ucuz segmentler her zaman en küçük kullanılabilir \(s\) değerlerinden gelir; optimal sayım katmanları küçükten büyüğe almakla elde edilir.
Önek segment sayısını ve önek maliyeti
$$\Phi(m)=\sum_{s=2}^{m}\varphi(s),\qquad C(m)=\sum_{s=2}^{m}s\varphi(s)$$
şeklinde tanımlayalım.
\(C(m)\le 2N\) koşulunu sağlayan en büyük \(m\) seçilir. Böylece \(2,3,\dots,m\) katmanları tamamen alınabilir ve toplam \(\Phi(m)\) segment verir. Sıradaki aday katman
$$s=m+1$$
olur. Kalan bütçe
$$R=2N-C(m)$$
ise bu son katmandan ham olarak alınabilecek ek segment sayısı
$$t=\left\lfloor\frac{R}{s}\right\rfloor,\qquad r=R\bmod s$$
olur. Dolayısıyla varsayılan segment sayısı \(\Phi(m)+t\), nokta sayısı ise \(\Phi(m)+t+1\)'dir.
\(r\gt 0\) olduğunda son katmandan \(t\) vektör seçildikten sonra hâlâ boşluk kalır ve uygulamalar bu durumu mümkün kabul eder. Düzeltme yalnızca
$$r=0,\qquad t\equiv 1\pmod{2}$$
iken gerekir.
Bu durumda alt tam katmanlar zaten kusursuz biçimde dengelidir; son katmanın kendi içinde tam denge kurması gerekir:
$$\sum a=\sum b=\frac{ts}{2}.$$
\(t\) çiftse, tamamlayıcı çiftler \((a,s-a)\) ve \((s-a,a)\) bunu doğrudan sağlar.
\(t=1\) ise denge kurmak imkansızdır.
\(s\equiv 0\pmod{4}\) ise yine imkansızdır. Bu durumda izin verilen tüm \(a\) değerleri tektir; bunların tek sayıda toplamı tek olur, oysa \(ts/2\) çifttir.
Geriye kalan durum \(s\equiv 2\pmod{4}\), yani \(s=2n\) ve \(n\) tek olmasıdır. Daha büyük her tek dengeli altküme, bir dengeli üçlüye tamamlayıcı çiftler eklenerek kurulabilir. Bu yüzden problem, toplamı \(3s/2\) olan ve \(s\) ile aralarında asal üç sayının var olup olmadığına indirgenir. Uygulama tam olarak bu koşulu kontrol eder; başarısızsa bir segment eksiltir.
Burada toplam bütçe
$$2N=200$$
olur. İlk katmanların önek maliyetleri şöyledir:
$$\begin{aligned} C(2)&=2,\\ C(3)&=8,\\ C(4)&=16,\\ C(5)&=36,\\ C(6)&=48,\\ C(7)&=90,\\ C(8)&=122,\\ C(9)&=176. \end{aligned}$$
Fakat \(C(10)=216\gt 200\) olduğu için son tam katman \(m=9\)'dur. Bu tam katmanlar
$$\Phi(9)=\varphi(2)+\varphi(3)+\cdots+\varphi(9)=1+2+2+4+2+6+4+6=27$$
segment verir. Kalan bütçe
$$R=200-176=24$$
ve sonraki katman \(s=10\) olduğundan
$$t=\left\lfloor\frac{24}{10}\right\rfloor=2,\qquad r=4$$
olur. \(r\ne 0\) olduğu için düzeltme yoktur. Sonuç olarak
$$F(100)=27+2+1=30,$$
ve bu değer C++, Python ve Java uygulamalarındaki doğrulama sonucu ile aynıdır.
Uygulama önce Euler totient fonksiyonunu, \(C(m)\) önek maliyeti \(2\times 10^{18}\)'i aşana kadar artan bir üst sınıra kadar eler. Ardından iki önek dizi kurar: biri \(\Phi(m)\), diğeri \(C(m)\) içindir.
Verilen bir \(N\) için \(C(m)\le 2N\) koşulunu sağlayan en büyük \(m\) ikili arama ile bulunur. Böylece tam katman sayısı ve kalan bütçe \(R\) hemen elde edilir.
Sonra \(t=\lfloor R/(m+1)\rfloor\) ve \(r=R\bmod (m+1)\) hesaplanır. Varsayılan cevap, tam katmanlardan gelen segment sayısına \(t\) eklenip başlangıç noktası için \(1\) daha eklenmesidir.
Son olarak, kalan sıfırsa ve son katmandan alınan segment sayısı tekse, uygulama Adım 5'teki denge testini yapar. İmkansız alt durumlarda segment sayısını \(1\) azaltır ve kafes nokta sayısını döndürür.
Elek \(L\) değerinde duruyorsa, \(L\)'ye kadar tüm totient değerlerini hesaplamak \(O(L\log\log L)\) zaman ve \(O(L)\) bellek gerektirir. Önek dizilerin kurulması \(O(L)\)'dir. Bundan sonra \(F(N)\) sorgusu bir ikili arama, birkaç aritmetik işlem ve nadir görülen tam doygunluk durumunda çok küçük bir ek test ister.
Sea \(F(N)\) el número máximo de puntos de la red dentro de un cuadrado \(N\times N\) que pueden estar sobre la gráfica de una sola función estrictamente convexa y creciente. Si la gráfica pasa por \(k+1\) puntos de la red, entonces aparecen \(k\) vectores de salto consecutivos. La meta es calcular \(F(10^{18})\), pero la derivación vale para cualquier \(N\).
Escribimos los puntos elegidos, en orden creciente de \(x\), como \(P_0,P_1,\dots,P_k\). Para cada pareja consecutiva definimos el vector de salto
$$P_i-P_{i-1}=(a_i,b_i).$$
Como la gráfica es creciente, cada paso cumple \(a_i\gt 0\) y \(b_i\gt 0\). Así, el problema geométrico se convierte en decidir cuántos de estos pasos pueden elegirse manteniendo la convexidad estricta y permaneciendo dentro del cuadrado.
La convexidad estricta implica que las pendientes de las cuerdas consecutivas crecen estrictamente:
$$\frac{b_1}{a_1} \lt \frac{b_2}{a_2} \lt \cdots \lt \frac{b_k}{a_k}.$$
El recorrido horizontal y vertical total debe caber dentro del cuadrado, por lo que
$$\sum_{i=1}^{k} a_i \le N,\qquad \sum_{i=1}^{k} b_i \le N.$$
Al sumar ambas restricciones obtenemos el presupuesto global en norma \(L_1\):
$$\sum_{i=1}^{k}(a_i+b_i)\le 2N.$$
Cada segmento adicional aporta exactamente un punto más de la red, de modo que basta con maximizar el número de vectores admisibles.
Si un paso \((a,b)\) tiene \(d=\gcd(a,b)\gt 1\), entonces el vector reducido \((a/d,b/d)\) tiene la misma pendiente pero menor coste \((a+b)/d\). Como una cadena estrictamente convexa no puede repetir una pendiente, un paso no primitivo nunca es mejor que su versión primitiva. Por tanto, en una construcción óptima podemos suponer
$$\gcd(a_i,b_i)=1.$$
Fijemos ahora
$$s=a+b.$$
Cada vector primitivo de esa capa tiene la forma \((a,s-a)\), con \(1\le a\le s-1\) y
$$\gcd(a,s)=1.$$
El número de posibilidades es exactamente la función totiente:
$$\#\{a:1\le a\le s-1,\ \gcd(a,s)=1\}=\varphi(s).$$
Todos los vectores primitivos con el mismo valor \(a+b=s\) forman una capa. Cada uno aporta un segmento y cuesta \(s\) unidades del presupuesto \(L_1\).
La capa es simétrica, porque \((a,s-a)\) es primitivo si y solo si \((s-a,a)\) también lo es. Al emparejar esos dos vectores, la contribución total en \(x\) y en \(y\) coincide:
$$\sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} a = \sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} (s-a) = \frac{s\varphi(s)}{2}.$$
Por ello, tomar la capa completa consume
$$s\varphi(s)$$
de coste total, repartido exactamente por mitad entre movimiento horizontal y vertical. Esa es la razón por la que, para capas completas, la restricción bidimensional del cuadrado se reduce a un único presupuesto.
Cada segmento disponible vale exactamente un punto adicional, pero un segmento de la capa \(s\) cuesta \(s\). Por eso, los segmentos más baratos siempre vienen de la menor capa aún no utilizada, y el conteo óptimo se obtiene tomando capas en orden creciente.
Definimos el número prefijo de segmentos y el coste prefijo por
$$\Phi(m)=\sum_{s=2}^{m}\varphi(s),\qquad C(m)=\sum_{s=2}^{m}s\varphi(s).$$
Sea \(m\) el mayor entero que cumple
$$C(m)\le 2N.$$
Entonces las capas \(2,3,\dots,m\) se toman completas y aportan \(\Phi(m)\) segmentos. La siguiente capa candidata es
$$s=m+1.$$
Con presupuesto restante
$$R=2N-C(m),$$
el número bruto de segmentos extra disponibles de esa última capa es
$$t=\left\lfloor\frac{R}{s}\right\rfloor,\qquad r=R\bmod s.$$
Así, el conteo por defecto de segmentos es \(\Phi(m)+t\), y el conteo por defecto de puntos es \(\Phi(m)+t+1\).
Cuando \(r\gt 0\), todavía sobra margen después de elegir \(t\) vectores de la capa final, y las implementaciones tratan ese caso como realizable. Solo hace falta una corrección cuando
$$r=0,\qquad t\equiv 1\pmod{2}.$$
En esa situación las capas completas inferiores ya están perfectamente equilibradas, así que la última capa debe equilibrarse por sí sola:
$$\sum a=\sum b=\frac{ts}{2}.$$
Si \(t\) es par, los pares complementarios \((a,s-a)\) y \((s-a,a)\) resuelven esto inmediatamente.
Si \(t=1\), es imposible.
Si \(s\equiv 0\pmod{4}\), también es imposible. Todos los valores admisibles de \(a\) son impares, por lo que la suma de un número impar de ellos es impar, mientras que \(ts/2\) es par.
El caso restante es \(s\equiv 2\pmod{4}\), es decir, \(s=2n\) con \(n\) impar. Toda subcolección equilibrada impar más grande puede escribirse como un triple equilibrado más pares complementarios. Por eso el problema se reduce a comprobar si existen tres enteros coprimos con \(s\) cuya suma sea \(3s/2\). La implementación comprueba exactamente esa condición y resta un segmento si falla.
Aquí el presupuesto total es
$$2N=200.$$
Los costes prefijo de las primeras capas son
$$\begin{aligned} C(2)&=2,\\ C(3)&=8,\\ C(4)&=16,\\ C(5)&=36,\\ C(6)&=48,\\ C(7)&=90,\\ C(8)&=122,\\ C(9)&=176. \end{aligned}$$
Pero \(C(10)=216\gt 200\), así que la última capa completa es \(m=9\). Esas capas completas aportan
$$\Phi(9)=\varphi(2)+\varphi(3)+\cdots+\varphi(9)=1+2+2+4+2+6+4+6=27$$
segmentos. El presupuesto restante es
$$R=200-176=24.$$
La siguiente capa es \(s=10\), luego
$$t=\left\lfloor\frac{24}{10}\right\rfloor=2,\qquad r=4.$$
No hace falta corrección porque \(r\ne 0\). Por tanto
$$F(100)=27+2+1=30,$$
en acuerdo con el punto de control usado por las implementaciones en C++, Python y Java.
La implementación primero calcula por criba la función totiente hasta un límite suficientemente grande para que el coste prefijo \(C(m)\) supere \(2\times 10^{18}\). A partir de esos valores construye dos arreglos prefijo: uno para \(\Phi(m)\) y otro para \(C(m)\).
Para un \(N\) dado, hace una búsqueda binaria del mayor \(m\) con \(C(m)\le 2N\). Eso da de inmediato cuántas capas completas caben y cuánto presupuesto queda.
Después calcula \(t=\lfloor R/(m+1)\rfloor\) y \(r=R\bmod (m+1)\). La respuesta por defecto es el número de segmentos de capas completas más \(t\), y luego se suma \(1\) por el punto inicial.
Por último, si el residuo es cero y el número de segmentos de la capa final es impar, la implementación ejecuta la comprobación de equilibrio del Paso 5. En los subcasos imposibles reduce en \(1\) el número de segmentos antes de devolver el número de puntos.
Si la criba termina en \(L\), calcular todos los valores de \(\varphi\) hasta \(L\) cuesta \(O(L\log\log L)\) tiempo y \(O(L)\) memoria. Construir los arreglos prefijo es \(O(L)\). Después, una consulta \(F(N)\) solo necesita una búsqueda binaria, unas pocas operaciones aritméticas y una comprobación muy pequeña en el raro caso de saturación exacta.
设 \(F(N)\) 表示在一个 \(N\times N\) 的正方形内，某一条严格凸且严格递增函数的图像最多能够经过多少个格点。如果图像经过 \(k+1\) 个格点，那么相邻格点之间就形成 \(k\) 个步进向量。题目要求计算 \(F(10^{18})\)，但下面的推导对任意 \(N\) 都成立。
把选中的格点按 \(x\) 坐标递增记为 \(P_0,P_1,\dots,P_k\)。对每一对相邻格点定义步进向量
$$P_i-P_{i-1}=(a_i,b_i).$$
由于函数单调递增，所以每一步都满足 \(a_i\gt 0\) 且 \(b_i\gt 0\)。这样一来，原来的几何问题就变成了：在保持严格凸性的同时，最多能选出多少个这样的正整数步进向量，并且整条折线仍然能放进正方形里。
严格凸意味着相邻弦段的斜率严格递增，也就是
$$\frac{b_1}{a_1} \lt \frac{b_2}{a_2} \lt \cdots \lt \frac{b_k}{a_k}.$$
整条路径的水平总跨度和竖直总跨度都不能超过正方形边长，因此有
$$\sum_{i=1}^{k} a_i \le N,\qquad \sum_{i=1}^{k} b_i \le N.$$
把这两个不等式相加，就得到全局的 \(L_1\) 预算：
$$\sum_{i=1}^{k}(a_i+b_i)\le 2N.$$
每增加一个线段，就会让格点数恰好多 \(1\)。所以最大化格点数，等价于最大化可选步进向量的数量。
如果某一步 \((a,b)\) 满足 \(d=\gcd(a,b)\gt 1\)，那么约化后的向量 \((a/d,b/d)\) 具有完全相同的斜率，但代价 \((a+b)/d\) 更小。由于严格凸链上同一个斜率不可能重复出现，所以非原始向量永远不会比它对应的原始向量更优。因此最优解可以假设所有步进都满足
$$\gcd(a_i,b_i)=1.$$
现在固定
$$s=a+b.$$
在这一层中，每个原始向量都写成 \((a,s-a)\) 的形式，并满足
$$1\le a\le s-1,\qquad \gcd(a,s)=1.$$
这样的选择个数恰好就是欧拉函数：
$$\#\{a:1\le a\le s-1,\ \gcd(a,s)=1\}=\varphi(s).$$
所有满足 \(a+b=s\) 的原始向量组成一层。该层中的每个向量都会贡献 \(1\) 条线段，同时消耗 \(s\) 单位的 \(L_1\) 预算。
这一层具有对称性，因为 \((a,s-a)\) 是原始向量，当且仅当 \((s-a,a)\) 也是原始向量。把它们配成一对后，\(x\) 方向和 \(y\) 方向的总贡献完全相同：
$$\sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} a = \sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} (s-a) = \frac{s\varphi(s)}{2}.$$
因此，整层全部取完时，总成本是
$$s\varphi(s),$$
而且其中一半用于水平位移，另一半用于竖直位移。正因为完整层会自动平衡，原本二维的正方形约束才能压缩成一维的总成本约束。
每条可用线段的收益都一样，都是额外增加 \(1\) 个格点；但来自第 \(s\) 层的线段代价是 \(s\)。因此最便宜的线段总来自尚未使用的最小 \(s\)，最优计数自然就是按层从小到大依次选取。
定义前缀线段数和前缀成本：
$$\Phi(m)=\sum_{s=2}^{m}\varphi(s),\qquad C(m)=\sum_{s=2}^{m}s\varphi(s).$$
令 \(m\) 为满足
$$C(m)\le 2N$$
的最大整数。那么第 \(2,3,\dots,m\) 层都可以完整取走，一共贡献 \(\Phi(m)\) 条线段。下一层候选就是
$$s=m+1.$$
剩余预算为
$$R=2N-C(m)$$
于是下一层最多还能提供的线段数为
$$t=\left\lfloor\frac{R}{s}\right\rfloor,\qquad r=R\bmod s.$$
因此默认的线段总数是 \(\Phi(m)+t\)，默认的格点总数就是 \(\Phi(m)+t+1\)。
当 \(r\gt 0\) 时，从最后一层拿走 \(t\) 个向量后仍然还有松弛空间，三个实现都把这种情况视为可行。真正需要修正的只有
$$r=0,\qquad t\equiv 1\pmod{2}$$
这一种情况。
此时较小的完整层已经完全平衡，最后这一层必须自己精确平衡：
$$\sum a=\sum b=\frac{ts}{2}.$$
如果 \(t\) 是偶数，那么直接选取若干对互补向量 \((a,s-a)\) 与 \((s-a,a)\) 就能做到完全平衡。
如果 \(t=1\)，显然不可能平衡。
如果 \(s\equiv 0\pmod{4}\)，同样不可能。因为所有允许的 \(a\) 都是奇数，奇数个这样的数相加仍是奇数，而 \(ts/2\) 却是偶数。
剩下的情况是 \(s\equiv 2\pmod{4}\)，也就是 \(s=2n\) 且 \(n\) 为奇数。此时任何更大的奇数平衡子集，都可以写成一个平衡三元组再加若干互补对。所以问题被化简为：是否存在三个与 \(s\) 互素的整数，它们的和正好等于 \(3s/2\)。实现代码正是检查这个条件；如果失败，就把线段数减 \(1\)。
这时总预算为
$$2N=200$$
前几层的前缀成本依次为
$$\begin{aligned} C(2)&=2,\\ C(3)&=8,\\ C(4)&=16,\\ C(5)&=36,\\ C(6)&=48,\\ C(7)&=90,\\ C(8)&=122,\\ C(9)&=176. \end{aligned}$$
而 \(C(10)=216\gt 200\)，所以最后一个能完整取走的层是 \(m=9\)。这些完整层一共贡献
$$\Phi(9)=\varphi(2)+\varphi(3)+\cdots+\varphi(9)=1+2+2+4+2+6+4+6=27$$
条线段。剩余预算为
$$R=200-176=24$$
下一层是 \(s=10\)，于是
$$t=\left\lfloor\frac{24}{10}\right\rfloor=2,\qquad r=4$$
因为 \(r\ne 0\)，不需要修正，所以
$$F(100)=27+2+1=30,$$
这与 C++、Python 和 Java 实现中使用的校验值完全一致。
实现首先对欧拉函数做筛法预处理，直到前缀成本 \(C(m)\) 超过 \(2\times 10^{18}\) 为止。随后构造两个前缀数组：一个保存 \(\Phi(m)\)，另一个保存 \(C(m)\)。
对给定的 \(N\)，实现会二分查找最大的 \(m\)，使得 \(C(m)\le 2N\)。这样就立刻知道完整层的数量，以及还剩下多少预算 \(R\)。
然后计算 \(t=\lfloor R/(m+1)\rfloor\) 和 \(r=R\bmod (m+1)\)。默认答案是完整层线段数加上 \(t\)，再额外加 \(1\) 表示起点格点。
最后，如果余数为零且最后一层取到的线段数为奇数，实现就会执行上面步骤 5 的平衡性检查。在不可能的子情形下，把线段数减去 \(1\)，再返回格点总数。
如果筛法最终停在 \(L\)，那么计算到 \(L\) 为止的所有欧拉函数值需要 \(O(L\log\log L)\) 时间和 \(O(L)\) 空间；构造两个前缀数组需要 \(O(L)\) 时间。之后计算一次 \(F(N)\) 只需要一次二分查找、若干常数次算术操作，以及在少见的恰好耗尽预算情况下做一个很小的额外检查。
Пусть \(F(N)\) обозначает максимальное число узлов решетки внутри квадрата \(N\times N\), которые могут лежать на графике одной строго выпуклой возрастающей функции. Если на графике лежат \(k+1\) узлов, то между соседними узлами возникают \(k\) последовательных векторов шага. Нужно найти \(F(10^{18})\), но вывод ниже справедлив для любого \(N\).
Обозначим выбранные точки в порядке возрастания \(x\) как \(P_0,P_1,\dots,P_k\). Для каждой соседней пары введем вектор шага
$$P_i-P_{i-1}=(a_i,b_i).$$
Так как функция возрастает, всегда выполняется \(a_i\gt 0\) и \(b_i\gt 0\). Значит, геометрическая задача сводится к вопросу: сколько таких шагов можно выбрать, сохраняя строгую выпуклость и не выходя за пределы квадрата.
Строгая выпуклость означает, что наклоны последовательных хорд строго возрастают:
$$\frac{b_1}{a_1} \lt \frac{b_2}{a_2} \lt \cdots \lt \frac{b_k}{a_k}.$$
Суммарный горизонтальный и вертикальный размах должны поместиться в квадрат, поэтому
$$\sum_{i=1}^{k} a_i \le N,\qquad \sum_{i=1}^{k} b_i \le N.$$
Складывая эти ограничения, получаем глобальный бюджет по \(L_1\):
$$\sum_{i=1}^{k}(a_i+b_i)\le 2N.$$
Каждый дополнительный отрезок добавляет ровно \(1\) новый узел решетки, так что достаточно максимизировать число допустимых шагов.
Если для шага \((a,b)\) выполнено \(d=\gcd(a,b)\gt 1\), то сокращенный вектор \((a/d,b/d)\) имеет тот же наклон, но меньшую цену \((a+b)/d\). Поскольку на строго выпуклой цепочке один и тот же наклон не может повторяться, непримитивный шаг никогда не выгоднее своего примитивного варианта. Значит, в оптимуме можно считать, что
$$\gcd(a_i,b_i)=1.$$
Зафиксируем теперь
$$s=a+b.$$
Каждый примитивный вектор в этом слое имеет вид \((a,s-a)\), где \(1\le a\le s-1\) и
$$\gcd(a,s)=1.$$
Число таких вариантов равно функции Эйлера:
$$\#\{a:1\le a\le s-1,\ \gcd(a,s)=1\}=\varphi(s).$$
Все примитивные векторы с фиксированным \(a+b=s\) образуют один слой. Каждый такой вектор дает один отрезок и стоит \(s\) единиц \(L_1\)-бюджета.
Слой симметричен: \((a,s-a)\) примитивен тогда и только тогда, когда примитивен и \((s-a,a)\). Если объединять такие пары, то суммарный вклад по \(x\) и по \(y\) совпадает:
$$\sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} a = \sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} (s-a) = \frac{s\varphi(s)}{2}.$$
Следовательно, полный слой использует общую стоимость
$$s\varphi(s),$$
и ровно половина этой стоимости уходит в горизонтальное смещение, а половина в вертикальное. Именно поэтому для полных слоев двумерное ограничение квадрата сводится к одномерному бюджетному условию.
Каждый доступный отрезок приносит одинаковую выгоду: один новый узел решетки. Но отрезок из слоя \(s\) стоит \(s\). Значит, самые дешевые отрезки всегда лежат в наименьшем еще не использованном слое, и оптимальный подсчет получается при проходе по слоям снизу вверх.
Введем префиксное число отрезков и префиксную стоимость:
$$\Phi(m)=\sum_{s=2}^{m}\varphi(s),\qquad C(m)=\sum_{s=2}^{m}s\varphi(s).$$
Пусть \(m\) - наибольшее целое, для которого
$$C(m)\le 2N.$$
Тогда слои \(2,3,\dots,m\) можно взять целиком, и они дают \(\Phi(m)\) отрезков. Следующий кандидатный слой равен
$$s=m+1.$$
При оставшемся бюджете
$$R=2N-C(m)$$
грубое количество дополнительных отрезков из следующего слоя равно
$$t=\left\lfloor\frac{R}{s}\right\rfloor,\qquad r=R\bmod s.$$
Итак, стандартное число отрезков равно \(\Phi(m)+t\), а стандартное число точек равно \(\Phi(m)+t+1\).
Когда \(r\gt 0\), после выбора \(t\) векторов из последнего слоя еще остается запас, и реализации считают такой случай допустимым. Исправление требуется только тогда, когда
$$r=0,\qquad t\equiv 1\pmod{2}.$$
В этот момент нижние полные слои уже идеально сбалансированы, поэтому последний слой должен сбалансироваться сам:
$$\sum a=\sum b=\frac{ts}{2}.$$
Если \(t\) четно, достаточно взять комплементарные пары \((a,s-a)\) и \((s-a,a)\).
Если \(t=1\), баланс невозможен.
Если \(s\equiv 0\pmod{4}\), баланс тоже невозможен. Все допустимые \(a\) тогда нечетны, сумма нечетного числа таких слагаемых нечетна, а \(ts/2\) четно.
Остается случай \(s\equiv 2\pmod{4}\), то есть \(s=2n\) при нечетном \(n\). Любое большее нечетное сбалансированное подмножество тогда раскладывается в один сбалансированный тройной набор плюс комплементарные пары. Поэтому задача сводится к проверке существования трех чисел, взаимно простых с \(s\), сумма которых равна \(3s/2\). Реализация проверяет именно это условие и, если оно нарушено, уменьшает число отрезков на \(1\).
Здесь общий бюджет равен
$$2N=200.$$
Префиксные стоимости первых слоев таковы:
$$\begin{aligned} C(2)&=2,\\ C(3)&=8,\\ C(4)&=16,\\ C(5)&=36,\\ C(6)&=48,\\ C(7)&=90,\\ C(8)&=122,\\ C(9)&=176. \end{aligned}$$
Но \(C(10)=216\gt 200\), поэтому последний полный слой - это \(m=9\). Полные слои дают
$$\Phi(9)=\varphi(2)+\varphi(3)+\cdots+\varphi(9)=1+2+2+4+2+6+4+6=27$$
отрезков. Оставшийся бюджет равен
$$R=200-176=24.$$
Следующий слой имеет номер \(s=10\), значит
$$t=\left\lfloor\frac{24}{10}\right\rfloor=2,\qquad r=4.$$
Поскольку \(r\ne 0\), корректировка не нужна. Следовательно,
$$F(100)=27+2+1=30,$$
что совпадает с контрольным значением, используемым в реализациях на C++, Python и Java.
Сначала реализация просеивает функцию Эйлера до такой границы, чтобы префиксная стоимость \(C(m)\) превысила \(2\times 10^{18}\). После этого строятся два префиксных массива: один для \(\Phi(m)\), другой для \(C(m)\).
Для заданного \(N\) выполняется бинарный поиск максимального \(m\), удовлетворяющего \(C(m)\le 2N\). Это сразу дает число полных слоев и оставшийся бюджет \(R\).
Далее вычисляются \(t=\lfloor R/(m+1)\rfloor\) и \(r=R\bmod (m+1)\). Ответ по умолчанию - это число отрезков из полных слоев плюс \(t\), а затем еще \(1\) за начальную точку.
Наконец, если остаток равен нулю и число отрезков в последнем слое нечетно, реализация выполняет проверку балансировки из Шага 5. В невозможных подслучаях она уменьшает число отрезков на \(1\), после чего возвращает число точек.
Если решето остановилось на \(L\), то вычисление всех значений функции Эйлера до \(L\) требует \(O(L\log\log L)\) времени и \(O(L)\) памяти. Построение префиксных массивов занимает \(O(L)\). Затем запрос \(F(N)\) использует только бинарный поиск, несколько арифметических операций и очень маленькую дополнительную проверку в редком случае точного насыщения бюджета.
ليكن \(F(N)\) هو أكبر عدد من نقاط الشبكة داخل مربع \(N\times N\) يمكن أن تقع على رسم دالة واحدة متزايدة ومحدبة بصرامة. إذا مر الرسم عبر \(k+1\) نقطة شبكية، فهذا يولد \(k\) متجهات خطوة متتالية. المطلوب هو حساب \(F(10^{18})\)، لكن الاشتقاق الآتي صالح لأي \(N\).
نكتب نقاط الشبكة المختارة بترتيب تصاعدي في \(x\) على الصورة \(P_0,P_1,\dots,P_k\). ولكل زوج متتال من النقاط نعرّف متجه الخطوة
$$P_i-P_{i-1}=(a_i,b_i).$$
بما أن الرسم متزايد، فإن كل خطوة تحقق \(a_i\gt 0\) و\(b_i\gt 0\). وهكذا تتحول المسألة الهندسية إلى سؤال: كم عدد هذه الخطوات التي يمكن اختيارها مع الحفاظ على التحدب الصارم والبقاء داخل المربع؟
التحدب الصارم يعني أن ميول الأوتار المتتالية تزداد بشكل صارم:
$$\frac{b_1}{a_1} \lt \frac{b_2}{a_2} \lt \cdots \lt \frac{b_k}{a_k}.$$
كما يجب أن يبقى الامتداد الأفقي والامتداد الرأسي الكليان داخل المربع، لذا
$$\sum_{i=1}^{k} a_i \le N,\qquad \sum_{i=1}^{k} b_i \le N.$$
بجمع الشرطين نحصل على ميزانية \(L_1\) الكلية:
$$\sum_{i=1}^{k}(a_i+b_i)\le 2N.$$
كل مقطع إضافي يزيد عدد نقاط الشبكة بمقدار \(1\) بالضبط، لذلك يكفي تعظيم عدد متجهات الخطوة المسموح بها.
إذا كانت خطوة ما \((a,b)\) تحقق \(d=\gcd(a,b)\gt 1\)، فإن المتجه المختزل \((a/d,b/d)\) يملك الميل نفسه لكن بكلفة أصغر مقدارها \((a+b)/d\). وبما أن السلسلة المحدبة بصرامة لا تسمح بتكرار الميل نفسه، فإن المتجه غير البدائي لا يكون أفضل من نسخته البدائية. لذلك يمكن افتراض أن الحل الأمثل يحقق
$$\gcd(a_i,b_i)=1.$$
لنثبت الآن القيمة
$$s=a+b.$$
كل متجه بدائي في هذه الطبقة يكتب على الصورة \((a,s-a)\) بحيث
$$1\le a\le s-1,\qquad \gcd(a,s)=1.$$
وعدد هذه الاختيارات يساوي تمامًا دالة أويلر:
$$\#\{a:1\le a\le s-1,\ \gcd(a,s)=1\}=\varphi(s).$$
كل المتجهات البدائية التي تحقق \(a+b=s\) تشكل طبقة واحدة. كل متجه في هذه الطبقة يضيف مقطعًا واحدًا ويستهلك \(s\) وحدة من ميزانية \(L_1\).
الطبقة متناظرة لأن \((a,s-a)\) يكون بدائيًا إذا وفقط إذا كان \((s-a,a)\) بدائيًا أيضًا. وعند جمع هذين المتجهين تكون المساهمة الكلية في اتجاه \(x\) مساوية للمساهمة الكلية في اتجاه \(y\):
$$\sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} a = \sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} (s-a) = \frac{s\varphi(s)}{2}.$$
إذن أخذ الطبقة كاملة يستهلك كلفة كلية مقدارها
$$s\varphi(s),$$
وينقسم هذا المقدار بالتساوي بين الحركة الأفقية والحركة الرأسية. وهذه هي الفكرة التي تجعل قيد المربع ثنائي البعد ينهار إلى قيد ميزانية واحد عندما نتعامل مع الطبقات الكاملة.
كل مقطع متاح يساوي نقطة شبكية إضافية واحدة، لكن مقطع الطبقة \(s\) يكلف \(s\). لذلك تأتي المقاطع الأرخص دائمًا من أصغر قيمة غير مستخدمة لـ \(s\)، ومن ثم يكون العد الأمثل بأخذ الطبقات تصاعديًا.
نعرّف مجموعي السوابق لعدد المقاطع والكلفة كما يلي:
$$\Phi(m)=\sum_{s=2}^{m}\varphi(s),\qquad C(m)=\sum_{s=2}^{m}s\varphi(s).$$
ولنأخذ \(m\) أكبر عدد صحيح يحقق
$$C(m)\le 2N.$$
عندئذ يمكن أخذ الطبقات \(2,3,\dots,m\) كاملة، وهي تعطي \(\Phi(m)\) مقطعًا. أما الطبقة التالية المرشحة فهي
$$s=m+1.$$
ومع الميزانية المتبقية
$$R=2N-C(m)$$
فإن العدد الخام للمقاطع الإضافية الممكنة من تلك الطبقة هو
$$t=\left\lfloor\frac{R}{s}\right\rfloor,\qquad r=R\bmod s.$$
إذًا العدد الافتراضي للمقاطع هو \(\Phi(m)+t\)، وعدد النقاط الافتراضي هو \(\Phi(m)+t+1\).
عندما يكون \(r\gt 0\)، يبقى هامش بعد اختيار \(t\) متجهات من الطبقة الأخيرة، ولذلك تتعامل التطبيقات مع هذه الحالة على أنها ممكنة. التصحيح لا يصبح لازمًا إلا عندما
$$r=0,\qquad t\equiv 1\pmod{2}.$$
في هذه الحالة تكون الطبقات الكاملة الأصغر متوازنة سلفًا، ولذلك يجب على الطبقة الأخيرة أن تحقق التوازن بنفسها:
$$\sum a=\sum b=\frac{ts}{2}.$$
إذا كان \(t\) زوجيًا، فإن الأزواج المكملة \((a,s-a)\) و\((s-a,a)\) تحقق التوازن مباشرة.
إذا كان \(t=1\)، فالتوازن مستحيل.
وإذا كان \(s\equiv 0\pmod{4}\)، فالتوازن مستحيل أيضًا. فجميع قيم \(a\) المسموح بها تكون فردية، ومجموع عدد فردي من الأعداد الفردية يبقى فرديًا، بينما \(ts/2\) زوجي.
تبقى الحالة \(s\equiv 2\pmod{4}\)، أي \(s=2n\) حيث \(n\) فردي. وعندها يمكن كتابة أي مجموعة متوازنة فردية أكبر على شكل ثلاثي متوازن مع أزواج مكملة. لذلك تنحصر المسألة في التحقق من وجود ثلاثة أعداد أولية نسبيًا مع \(s\) مجموعها \(3s/2\). التطبيق يفحص هذا الشرط بالضبط، وإذا فشل ينقص عدد المقاطع بمقدار \(1\).
هنا تكون الميزانية الكلية
$$2N=200.$$
وكلفات السوابق للطبقات الأولى هي
$$\begin{aligned} C(2)&=2,\\ C(3)&=8,\\ C(4)&=16,\\ C(5)&=36,\\ C(6)&=48,\\ C(7)&=90,\\ C(8)&=122,\\ C(9)&=176. \end{aligned}$$
لكن \(C(10)=216\gt 200\)، ولذلك تكون آخر طبقة كاملة هي \(m=9\). وتعطي هذه الطبقات الكاملة
$$\Phi(9)=\varphi(2)+\varphi(3)+\cdots+\varphi(9)=1+2+2+4+2+6+4+6=27$$
مقطعًا. والميزانية المتبقية هي
$$R=200-176=24.$$
والطبقة التالية هي \(s=10\)، ومن ثم
$$t=\left\lfloor\frac{24}{10}\right\rfloor=2,\qquad r=4.$$
لا نحتاج إلى أي تصحيح لأن \(r\ne 0\). وعليه
$$F(100)=27+2+1=30,$$
وهو تمامًا مقدار التحقق المستخدم في تطبيقات C++ وPython وJava.
تبدأ التطبيقات بغربلة دالة أويلر حتى حد يكفي لأن تتجاوز كلفة السوابق \(C(m)\) القيمة \(2\times 10^{18}\). وبعد ذلك تُبنى مصفوفتان تراكمـيتان: واحدة لـ \(\Phi(m)\) وأخرى لـ \(C(m)\).
ولقيمة \(N\) معطاة، تُجرى عملية بحث ثنائي لإيجاد أكبر \(m\) يحقق \(C(m)\le 2N\). وبذلك نحصل مباشرة على عدد الطبقات الكاملة والميزانية المتبقية \(R\).
ثم تحسب الشيفرة \(t=\lfloor R/(m+1)\rfloor\) و\(r=R\bmod (m+1)\). والجواب الافتراضي هو عدد مقاطع الطبقات الكاملة زائد \(t\)، ثم نضيف \(1\) لنقطة البداية.
أخيرًا، إذا كان الباقي صفرًا وكان عدد مقاطع الطبقة الأخيرة فرديًا، تجري الشيفرة اختبار التوازن المذكور في الخطوة 5. وفي الحالات المستحيلة تُنقص عدد المقاطع بمقدار \(1\) قبل إعادة عدد نقاط الشبكة.
إذا توقفت الغربلة عند \(L\)، فإن حساب جميع قيم دالة أويلر حتى \(L\) يحتاج إلى \(O(L\log\log L)\) زمنًا و\(O(L)\) ذاكرة. وبناء المصفوفتين التراكميتين يكلف \(O(L)\). بعد ذلك يحتاج حساب \(F(N)\) إلى بحث ثنائي واحد، وبعض العمليات الحسابية البسيطة، واختبار صغير جدًا فقط في الحالة النادرة الخاصة بالإشباع التام.