Let \(G_N=\{(x,y)\in\mathbb{Z}^2:0\le x,y\le N\}\). A finite set \(S\subseteq G_N\) is called titanic if some line passes through exactly two points of \(S\). We must compute \(T(N)\), the number of titanic subsets of \(G_N\), modulo \(10^8\).
The implementation never enumerates subsets directly. Instead, it counts the complement: empty sets, singletons, and larger subsets whose selected points are all collinear.
The key theorem is Sylvester-Gallai: every finite non-collinear set of real points has an ordinary line, meaning a line containing exactly two of the points. Therefore a lattice subset is not titanic if and only if it is empty, a singleton, or all of its points lie on one common line.
If \(\operatorname{NT}(N)\) denotes the number of non-titanic subsets, then
$$T(N)=2^{(N+1)^2}-\operatorname{NT}(N)\pmod{10^8}.$$
Suppose a grid line contains exactly \(k\) lattice points. The non-titanic subsets supported on that line are exactly the subsets of size at least \(3\), so that line contributes
$$\sum_{r=3}^{k}\binom{k}{r}=2^k-1-k-\binom{k}{2}.$$
Now define \(F_\ell(N)\) as the number of grid lines containing at least \(\ell+1\) lattice points. For a fixed line with \(k\) points, one has the identity
$$\sum_{\ell=2}^{k-1}\bigl(2^\ell-(\ell+1)\bigr)=2^k-1-k-\binom{k}{2}.$$
Therefore
$$\operatorname{NT}(N)=1+(N+1)^2+\sum_{\ell=2}^{N}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
The whole task is now reduced to computing \(F_\ell(N)\) efficiently for all \(\ell\ge2\).
Write \(a=N+1\). Every non-axis grid line has a primitive step vector \((u,v)\) with \(1\le v\le u\) and \(\gcd(u,v)=1\). The pair \((u,v)\) represents the slope classes \(\pm v/u\), and when \(u\ne v\), also the swapped classes \(\pm u/v\). Horizontal and vertical lines are handled separately.
For such a primitive direction, the number of placements of an \(\ell\)-step segment inside the square is
$$C_\ell(u,v)=\max(a-\ell u,0)\max(a-\ell v,0).$$
If a line contains \(k\) lattice points, then it contributes exactly \(k-\ell\) segments of length \(\ell\) and \(k-\ell-1\) segments of length \(\ell+1\). Their difference is \(1\) exactly when \(k\ge\ell+1\). Hence the number of distinct lines in this direction class that contain at least \(\ell+1\) points is
$$C_\ell(u,v)-C_{\ell+1}(u,v).$$
After doubling for the two signs and adding the \(a\) horizontal plus \(a\) vertical lines, we recover \(F_\ell(N)\).
Let
$$\Phi(M)=\sum_{d\le M}\varphi(d),\qquad \Psi_1(M)=\sum_{d\le M} d\,\varphi(d),\qquad \Psi_2(M)=\sum_{d\le M} d^2\varphi(d).$$
The implementation stores the primitive-direction information in three cumulative quantities:
$$c(M)=2\Phi(M)-1,\qquad s_{xy}(M)=3\Psi_1(M)-1,\qquad s_{\prod}(M)=\Psi_2(M).$$
Why do these formulas appear? Group primitive directions by their larger coordinate \(d\). For fixed \(d>1\), there are \(\varphi(d)\) reduced numerators, their sum is \(d\varphi(d)/2\), and the swapped directions contribute the same amount. The exceptional diagonal case \(d=1\) explains the subtractive constants.
The code does not recompute these sums from scratch for every query. Using \(\sum_{d\mid n}\varphi(d)=n\), one gets the divisor-summatory identities
$$\sum_{q=1}^{n}\Phi\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m=\frac{n(n+1)}{2},$$
$$\sum_{q=1}^{n}q\,\Psi_1\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^2=\frac{n(n+1)(2n+1)}{6},$$
$$\sum_{q=1}^{n}q^2\,\Psi_2\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^3=\left(\frac{n(n+1)}{2}\right)^2.$$
Those identities lead to memoized recurrences over quotient blocks \(\left\lfloor n/q\right\rfloor\), which is why the summatory functions can be queried many times without a linear scan up to \(n\).
Set
$$M=\left\lfloor\frac{N}{\ell}\right\rfloor,\qquad M'=\left\lfloor\frac{N}{\ell+1}\right\rfloor,\qquad a=N+1.$$
On any interval of \(\ell\) where \(M\) and \(M'\) stay constant, the line count becomes a quadratic polynomial in \(\ell\):
$$F_\ell(N)=2a+2\left(q_2\ell^2+q_1\ell+q_0\right),$$
where
$$q_2=s_{\prod}(M)-s_{\prod}(M'),$$
$$q_1=a\bigl(s_{xy}(M')-s_{xy}(M)\bigr)-2s_{\prod}(M'),$$
$$q_0=a^2\bigl(c(M)-c(M')\bigr)+a\,s_{xy}(M')-s_{\prod}(M').$$
This is exactly the quadratic block formula that appears in the implementation.
The values of \(\left\lfloor N/\ell\right\rfloor\) change only \(O(\sqrt N)\) times, so the final summation is performed block by block. For \(\ell\in[L_1,L_2]\), the contribution is
$$\sum_{\ell=L_1}^{L_2}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
After substituting the quadratic form, the implementation only needs closed forms for
$$\sum 2^\ell,\qquad \sum \ell 2^\ell,\qquad \sum \ell^2 2^\ell,\qquad \sum \ell,\qquad \sum \ell^2,\qquad \sum \ell^3.$$
The exponential identities used are
$$\sum_{j=0}^{n}2^j=2^{n+1}-1,\qquad \sum_{j=0}^{n}j2^j=(n-1)2^{n+1}+2,$$
$$\sum_{j=0}^{n}j^2 2^j=(n^2-2n+3)2^{n+1}-6.$$
For the \(5\times5\) grid, the formula gives
$$F_2(4)=32,\qquad F_3(4)=16,\qquad F_4(4)=12.$$
Hence
$$\operatorname{NT}(4)=1+25+32(1)+16(4)+12(11)=254,$$
and therefore
$$T(4)=2^{25}-254=33554178,$$
which matches the checkpoint verified by the implementation.
The C++, Python, and Java implementations follow the same mathematical pipeline. They precompute Euler totients up to a fixed cutoff with a linear sieve, build prefix tables for \(\Phi\), \(\Psi_1\), and \(\Psi_2\), and memoize larger arguments so that each summatory query is solved only once.
After that, the implementation enumerates the distinct quotient blocks of \(\lfloor N/\ell\rfloor\). Inside each block it evaluates the quadratic line-count formula, applies the closed forms for the exponential and polynomial sums, accumulates the complement count, and finally subtracts that value from \(2^{(N+1)^2}\) modulo \(10^8\).
Let \(B\) be the totient precomputation cutoff and let \(Q\) be the number of distinct values taken by \(\lfloor N/\ell\rfloor\); one has \(Q=O(\sqrt N)\). The sieve and prefix tables cost near-linear time and \(O(B)\) memory. The outer summation uses only \(O(Q)\) quotient blocks, and the cached summatory totient queries are shared across those blocks instead of being recomputed. In practice, the heavy work is the prefix-table construction plus the \(O(\sqrt N)\)-scale block arithmetic.
Sei \(G_N=\{(x,y)\in\mathbb{Z}^2:0\le x,y\le N\}\). Eine endliche Menge \(S\subseteq G_N\) heißt titanic, wenn es eine Gerade gibt, die genau zwei Punkte aus \(S\) enthält. Gesucht ist also \(T(N)\), die Anzahl titanicer Teilmengen von \(G_N\), modulo \(10^8\).
Die Implementierung durchsucht keine Teilmengen direkt. Stattdessen wird das Komplement gezählt: die leere Menge, alle Einelementmengen und alle größeren Teilmengen, deren Punkte vollständig auf einer gemeinsamen Geraden liegen.
Der entscheidende Satz ist Sylvester-Gallai: Jede endliche nichtkollineare Punktmenge in der Ebene besitzt eine ordinäre Gerade, also eine Gerade mit genau zwei Punkten der Menge. Daher ist eine Gitterteilmenge genau dann nicht titanic, wenn sie leer ist, genau einen Punkt enthält oder vollständig kollinear ist.
Bezeichnet \(\operatorname{NT}(N)\) die Anzahl der nicht-titanicen Mengen, dann gilt
$$T(N)=2^{(N+1)^2}-\operatorname{NT}(N)\pmod{10^8}.$$
Enthält eine Gittergerade genau \(k\) Gitterpunkte, dann sind genau die Teilmengen dieser Geraden mit mindestens \(3\) Punkten nicht titanic. Ihr Beitrag ist also
$$\sum_{r=3}^{k}\binom{k}{r}=2^k-1-k-\binom{k}{2}.$$
Sei nun \(F_\ell(N)\) die Anzahl der Gittergeraden mit mindestens \(\ell+1\) Gitterpunkten. Für eine feste Gerade mit \(k\) Punkten gilt die Identität
$$\sum_{\ell=2}^{k-1}\bigl(2^\ell-(\ell+1)\bigr)=2^k-1-k-\binom{k}{2}.$$
Also folgt
$$\operatorname{NT}(N)=1+(N+1)^2+\sum_{\ell=2}^{N}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
Damit reduziert sich das ganze Problem auf die schnelle Berechnung von \(F_\ell(N)\) für alle \(\ell\ge2\).
Schreibe \(a=N+1\). Jede nicht horizontale und nicht vertikale Gittergerade besitzt einen primitiven Schrittvektor \((u,v)\) mit \(1\le v\le u\) und \(\gcd(u,v)=1\). Das Paar \((u,v)\) repräsentiert die Steigungsfamilien \(\pm v/u\) und, falls \(u\ne v\), zusätzlich die vertauschten Familien \(\pm u/v\). Horizontale und vertikale Geraden werden separat behandelt.
Für eine solche primitive Richtung ist die Anzahl der Platzierungen eines \(\ell\)-Schritt-Segments im Quadrat
$$C_\ell(u,v)=\max(a-\ell u,0)\max(a-\ell v,0).$$
Hat eine Gerade \(k\) Gitterpunkte, dann liefert sie genau \(k-\ell\) Segmente der Länge \(\ell\) und \(k-\ell-1\) Segmente der Länge \(\ell+1\). Die Differenz ist genau dann \(1\), wenn \(k\ge\ell+1\). Also ist die Anzahl der Geraden dieser Richtungsklasse mit mindestens \(\ell+1\) Punkten gleich
$$C_\ell(u,v)-C_{\ell+1}(u,v).$$
Verdoppelt man für die beiden Vorzeichen und addiert die \(a\) horizontalen sowie \(a\) vertikalen Geraden, erhält man \(F_\ell(N)\).
Definiere
$$\Phi(M)=\sum_{d\le M}\varphi(d),\qquad \Psi_1(M)=\sum_{d\le M} d\,\varphi(d),\qquad \Psi_2(M)=\sum_{d\le M} d^2\varphi(d).$$
Die Implementierung fasst die primitiven Richtungen in drei kumulativen Größen zusammen:
$$c(M)=2\Phi(M)-1,\qquad s_{xy}(M)=3\Psi_1(M)-1,\qquad s_{\prod}(M)=\Psi_2(M).$$
Diese Formeln entstehen, wenn man nach der größeren Koordinate \(d\) gruppiert. Für festes \(d>1\) gibt es \(\varphi(d)\) teilerfremde Zähler, ihre Summe ist \(d\varphi(d)/2\), und die vertauschten Richtungen liefern denselben Beitrag. Der Sonderfall \(d=1\) erzeugt die konstanten Korrekturterme.
Diese Summen werden nicht für jede Anfrage neu berechnet. Aus \(\sum_{d\mid n}\varphi(d)=n\) folgen die Summenidentitäten
$$\sum_{q=1}^{n}\Phi\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m=\frac{n(n+1)}{2},$$
$$\sum_{q=1}^{n}q\,\Psi_1\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^2=\frac{n(n+1)(2n+1)}{6},$$
$$\sum_{q=1}^{n}q^2\,\Psi_2\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^3=\left(\frac{n(n+1)}{2}\right)^2.$$
Daraus entstehen memoiserte Rekursionen über Quotientenblöcke \(\left\lfloor n/q\right\rfloor\). Genau deshalb können diese Summen für große Argumente oft abgefragt werden, ohne bis \(n\) linear zu iterieren.
Setze
$$M=\left\lfloor\frac{N}{\ell}\right\rfloor,\qquad M'=\left\lfloor\frac{N}{\ell+1}\right\rfloor,\qquad a=N+1.$$
Auf jedem Intervall von \(\ell\), auf dem \(M\) und \(M'\) konstant bleiben, ist die Geradenzahl ein quadratisches Polynom in \(\ell\):
$$F_\ell(N)=2a+2\left(q_2\ell^2+q_1\ell+q_0\right),$$
wobei
$$q_2=s_{\prod}(M)-s_{\prod}(M'),$$
$$q_1=a\bigl(s_{xy}(M')-s_{xy}(M)\bigr)-2s_{\prod}(M'),$$
$$q_0=a^2\bigl(c(M)-c(M')\bigr)+a\,s_{xy}(M')-s_{\prod}(M').$$
Genau dieses quadratische Blockmodell wird im Programm ausgewertet.
Die Werte von \(\left\lfloor N/\ell\right\rfloor\) ändern sich nur \(O(\sqrt N)\)-mal, also wird die Endsumme blockweise berechnet. Für \(\ell\in[L_1,L_2]\) lautet der Beitrag
$$\sum_{\ell=L_1}^{L_2}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
Nach Einsetzen des quadratischen Polynoms werden nur noch geschlossene Formen für
$$\sum 2^\ell,\qquad \sum \ell 2^\ell,\qquad \sum \ell^2 2^\ell,\qquad \sum \ell,\qquad \sum \ell^2,\qquad \sum \ell^3$$
benötigt. Verwendet werden insbesondere
$$\sum_{j=0}^{n}2^j=2^{n+1}-1,\qquad \sum_{j=0}^{n}j2^j=(n-1)2^{n+1}+2,$$
$$\sum_{j=0}^{n}j^2 2^j=(n^2-2n+3)2^{n+1}-6.$$
Für das \(5\times5\)-Gitter liefert die Formel
$$F_2(4)=32,\qquad F_3(4)=16,\qquad F_4(4)=12.$$
Damit folgt
$$\operatorname{NT}(4)=1+25+32(1)+16(4)+12(11)=254,$$
und somit
$$T(4)=2^{25}-254=33554178,$$
genau der Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Pipeline. Zunächst werden Totientwerte bis zu einer festen Grenze mit einem linearen Sieb vorab berechnet, daraus entstehen Präfixtabellen für \(\Phi\), \(\Psi_1\) und \(\Psi_2\), und für größere Argumente werden die Ergebnisse zwischengespeichert.
Anschließend durchläuft die Implementierung die verschiedenen Quotientenblöcke von \(\lfloor N/\ell\rfloor\). Innerhalb eines Blocks wird die quadratische Formel für die Geradenzahl ausgewertet, dann werden die geschlossenen Summenformeln angewandt, das Komplement akkumuliert und am Ende von \(2^{(N+1)^2}\) modulo \(10^8\) subtrahiert.
Sei \(B\) die Vorberechnungsgrenze für die Totientwerte und \(Q\) die Anzahl der verschiedenen Werte von \(\lfloor N/\ell\rfloor\); es gilt \(Q=O(\sqrt N)\). Sieb und Präfixtabellen kosten nahezu lineare Zeit und \(O(B)\) Speicher. Die äußere Summation verwendet nur \(O(Q)\) Quotientenblöcke, und die großen Summenwerte werden per Cache über diese Blöcke hinweg wiederverwendet. Praktisch dominiert also der Aufbau der Tabellen zusammen mit der \(O(\sqrt N)\)-Blockarithmetik.
\(G_N=\{(x,y)\in\mathbb{Z}^2:0\le x,y\le N\}\) olsun. Sonlu bir \(S\subseteq G_N\) kümesi, \(S\) içinden tam olarak iki noktadan geçen bir doğru varsa titanic olarak adlandırılır. Amaç, \(G_N\)'nin titanic altkümelerinin sayısı olan \(T(N)\)'yi \(10^8\) modunda hesaplamaktır.
Uygulama altkümeleri tek tek denemez. Bunun yerine tamamlayıcıyı sayar: boş küme, tek noktalı kümeler ve tüm seçili noktaları aynı doğru üzerinde kalan daha büyük altkümeler.
Ana teorem Sylvester-Gallai teoremidir: Düzlemdeki her sonlu ve doğrusal olmayan nokta kümesinin, kümeden tam olarak iki nokta içeren bir ordinary line'ı vardır. Bu nedenle bir kafes altkümesi ancak ve ancak boşsa, tek elemanlıysa ya da tüm noktaları aynı doğru üzerindeyse titanic değildir.
\(\operatorname{NT}(N)\) titanic olmayan altkümelerin sayısı olsun. O zaman
$$T(N)=2^{(N+1)^2}-\operatorname{NT}(N)\pmod{10^8}.$$
Bir kafes doğrusu tam olarak \(k\) kafes noktası içeriyorsa, bu doğru üzerindeki titanic olmayan seçimler tam olarak en az \(3\) noktalı altkümelerdir. Dolayısıyla bu doğrunun katkısı
$$\sum_{r=3}^{k}\binom{k}{r}=2^k-1-k-\binom{k}{2}$$
olur. Şimdi \(F_\ell(N)\), en az \(\ell+1\) kafes noktası içeren doğru sayısı olsun. \(k\) noktalı tek bir doğru için
$$\sum_{\ell=2}^{k-1}\bigl(2^\ell-(\ell+1)\bigr)=2^k-1-k-\binom{k}{2}$$
eşitliği geçerlidir. Bu nedenle
$$\operatorname{NT}(N)=1+(N+1)^2+\sum_{\ell=2}^{N}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
Yani problem, tüm \(\ell\ge2\) için \(F_\ell(N)\)'yi hızlı hesaplamaya indirgenir.
\(a=N+1\) yazalım. Yatay ve dikey olmayan her kafes doğrusunun, \(1\le v\le u\) ve \(\gcd(u,v)=1\) koşullarını sağlayan bir primitif adım vektörü \((u,v)\) vardır. \((u,v)\) çifti, \(\pm v/u\) eğim sınıflarını ve \(u\ne v\) ise buna ek olarak \(\pm u/v\) sınıflarını temsil eder. Yatay ve dikey doğrular ayrı sayılır.
Bu primitif yön için, kare içindeki \(\ell\) adımlı parça yerleşim sayısı
$$C_\ell(u,v)=\max(a-\ell u,0)\max(a-\ell v,0)$$
şeklindedir. Bir doğru \(k\) kafes noktası içeriyorsa, \(\ell\) uzunluğunda tam \(k-\ell\) parça ve \(\ell+1\) uzunluğunda tam \(k-\ell-1\) parça verir. Aradaki fark ancak \(k\ge\ell+1\) ise \(1\) olur. Demek ki bu yön sınıfında en az \(\ell+1\) nokta içeren doğru sayısı
$$C_\ell(u,v)-C_{\ell+1}(u,v)$$
olur. Bunu iki işaret için ikiyle çarpıp \(a\) yatay ve \(a\) dikey doğruyu ekleyince \(F_\ell(N)\) elde edilir.
Aşağıdaki toplamları tanımlayalım:
$$\Phi(M)=\sum_{d\le M}\varphi(d),\qquad \Psi_1(M)=\sum_{d\le M} d\,\varphi(d),\qquad \Psi_2(M)=\sum_{d\le M} d^2\varphi(d).$$
Uygulama primitif yön bilgisini şu birikimli büyüklüklerde toplar:
$$c(M)=2\Phi(M)-1,\qquad s_{xy}(M)=3\Psi_1(M)-1,\qquad s_{\prod}(M)=\Psi_2(M).$$
Bu formüller, yönleri daha büyük koordinatları \(d\) ile gruplayınca ortaya çıkar. Sabit \(d>1\) için \(\varphi(d)\) tane sade pay vardır; bunların toplamı \(d\varphi(d)/2\)'dir ve koordinatları yer değiştirilmiş yönler aynı katkıyı tekrar verir. \(d=1\) olan köşegen durumu ise sabit düzeltme terimlerini açıklar.
Bu toplamlar her sorguda baştan hesaplanmaz. \(\sum_{d\mid n}\varphi(d)=n\) kimliğinden
$$\sum_{q=1}^{n}\Phi\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m=\frac{n(n+1)}{2},$$
$$\sum_{q=1}^{n}q\,\Psi_1\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^2=\frac{n(n+1)(2n+1)}{6},$$
$$\sum_{q=1}^{n}q^2\,\Psi_2\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^3=\left(\frac{n(n+1)}{2}\right)^2$$
elde edilir. Bunlar, \(\left\lfloor n/q\right\rfloor\) blokları üzerinden çalışan ve önbelleklenen özyinelemeleri doğurur; böylece büyük argümanlar tekrar tekrar doğrusal tarama olmadan hesaplanabilir.
Şu tanımları yapalım:
$$M=\left\lfloor\frac{N}{\ell}\right\rfloor,\qquad M'=\left\lfloor\frac{N}{\ell+1}\right\rfloor,\qquad a=N+1.$$
\(M\) ve \(M'\) sabit kaldığı her \(\ell\) aralığında doğru sayısı \(\ell\)'ye göre ikinci dereceden bir polinom olur:
$$F_\ell(N)=2a+2\left(q_2\ell^2+q_1\ell+q_0\right),$$
burada
$$q_2=s_{\prod}(M)-s_{\prod}(M'),$$
$$q_1=a\bigl(s_{xy}(M')-s_{xy}(M)\bigr)-2s_{\prod}(M'),$$
$$q_0=a^2\bigl(c(M)-c(M')\bigr)+a\,s_{xy}(M')-s_{\prod}(M').$$
Uygulamadaki blok formülü tam olarak budur.
\(\left\lfloor N/\ell\right\rfloor\) yalnızca \(O(\sqrt N)\) kez değiştiği için son toplam blok blok alınır. \(\ell\in[L_1,L_2]\) için katkı
$$\sum_{\ell=L_1}^{L_2}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr)$$
şeklindedir. İkinci derece polinom yerine yazılınca yalnızca
$$\sum 2^\ell,\qquad \sum \ell 2^\ell,\qquad \sum \ell^2 2^\ell,\qquad \sum \ell,\qquad \sum \ell^2,\qquad \sum \ell^3$$
kapalı formlarına ihtiyaç kalır. Kullanılan üstel toplam kimlikleri
$$\sum_{j=0}^{n}2^j=2^{n+1}-1,\qquad \sum_{j=0}^{n}j2^j=(n-1)2^{n+1}+2,$$
$$\sum_{j=0}^{n}j^2 2^j=(n^2-2n+3)2^{n+1}-6$$
biçimindedir.
\(5\times5\) kafes için formül
$$F_2(4)=32,\qquad F_3(4)=16,\qquad F_4(4)=12$$
değerlerini verir. Dolayısıyla
$$\operatorname{NT}(4)=1+25+32(1)+16(4)+12(11)=254,$$
ve bunun sonucunda
$$T(4)=2^{25}-254=33554178$$
elde edilir; bu da uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Önce Euler totient değerleri belirli bir sınıra kadar doğrusal elekle hesaplanır, ardından \(\Phi\), \(\Psi_1\) ve \(\Psi_2\) için prefix tabloları kurulur ve daha büyük argümanlar önbelleğe alınır.
Daha sonra uygulama \(\lfloor N/\ell\rfloor\) değerinin sabit kaldığı blokları dolaşır. Her blokta doğru sayısı için ikinci derece formül değerlendirilir, üstel ve polinomsal toplamların kapalı formları uygulanır, tamamlayıcı sayı toplanır ve en sonda bu değer \(2^{(N+1)^2}\)'den \(10^8\) modunda çıkarılır.
\(B\) totient ön hesaplama sınırı, \(Q\) ise \(\lfloor N/\ell\rfloor\)'nin farklı değer sayısı olsun; \(Q=O(\sqrt N)\) olur. Elek ve prefix tabloları yaklaşık doğrusal zamanda kurulup \(O(B)\) bellek kullanır. Dış toplam yalnızca \(O(Q)\) blok gezer ve büyük toplam sorguları bu bloklar arasında önbellekten tekrar kullanılır. Pratikte maliyetin ana kısmı tablo hazırlığı ile \(O(\sqrt N)\) ölçeğindeki blok aritmetiğidir.
Sea \(G_N=\{(x,y)\in\mathbb{Z}^2:0\le x,y\le N\}\). Un conjunto finito \(S\subseteq G_N\) se llama titanic si existe una recta que pasa exactamente por dos puntos de \(S\). Debemos calcular \(T(N)\), el número de subconjuntos titanic de \(G_N\), módulo \(10^8\).
La implementación no prueba subconjuntos uno por uno. En cambio cuenta el complemento: el conjunto vacío, los singletons y los subconjuntos más grandes cuyos puntos elegidos son todos colineales.
La herramienta conceptual es el teorema de Sylvester-Gallai: todo conjunto finito no colineal de puntos reales tiene una ordinary line, es decir, una recta que contiene exactamente dos de sus puntos. Por tanto, un subconjunto de la red no es titanic si y solo si es vacío, tiene un solo punto o todos sus puntos están en una misma recta.
Si \(\operatorname{NT}(N)\) denota el número de subconjuntos no titanic, entonces
$$T(N)=2^{(N+1)^2}-\operatorname{NT}(N)\pmod{10^8}.$$
Supongamos que una recta de la red contiene exactamente \(k\) puntos. Los subconjuntos no titanic apoyados en esa recta son precisamente los de tamaño al menos \(3\), así que su contribución es
$$\sum_{r=3}^{k}\binom{k}{r}=2^k-1-k-\binom{k}{2}.$$
Definamos ahora \(F_\ell(N)\) como el número de rectas de la red que contienen al menos \(\ell+1\) puntos. Para una recta fija con \(k\) puntos se cumple
$$\sum_{\ell=2}^{k-1}\bigl(2^\ell-(\ell+1)\bigr)=2^k-1-k-\binom{k}{2}.$$
Por consiguiente,
$$\operatorname{NT}(N)=1+(N+1)^2+\sum_{\ell=2}^{N}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
El problema completo queda reducido a calcular \(F_\ell(N)\) de forma rápida para todos los \(\ell\ge2\).
Escribamos \(a=N+1\). Toda recta no horizontal y no vertical de la red tiene un vector paso primitivo \((u,v)\) con \(1\le v\le u\) y \(\gcd(u,v)=1\). El par \((u,v)\) representa las familias de pendientes \(\pm v/u\) y, cuando \(u\ne v\), también las familias intercambiadas \(\pm u/v\). Las rectas horizontales y verticales se cuentan aparte.
Para una dirección primitiva así, el número de posiciones de un segmento de \(\ell\) pasos dentro del cuadrado es
$$C_\ell(u,v)=\max(a-\ell u,0)\max(a-\ell v,0).$$
Si una recta contiene \(k\) puntos de la red, aporta exactamente \(k-\ell\) segmentos de longitud \(\ell\) y \(k-\ell-1\) segmentos de longitud \(\ell+1\). La diferencia vale \(1\) exactamente cuando \(k\ge\ell+1\). Por ello, el número de rectas de esta clase direccional con al menos \(\ell+1\) puntos es
$$C_\ell(u,v)-C_{\ell+1}(u,v).$$
Al duplicar por los dos signos y sumar las \(a\) rectas horizontales y las \(a\) verticales, obtenemos \(F_\ell(N)\).
Definimos
$$\Phi(M)=\sum_{d\le M}\varphi(d),\qquad \Psi_1(M)=\sum_{d\le M} d\,\varphi(d),\qquad \Psi_2(M)=\sum_{d\le M} d^2\varphi(d).$$
La implementación condensa la información direccional en tres acumulados:
$$c(M)=2\Phi(M)-1,\qquad s_{xy}(M)=3\Psi_1(M)-1,\qquad s_{\prod}(M)=\Psi_2(M).$$
Estas fórmulas aparecen al agrupar las direcciones primitivas por su coordenada mayor \(d\). Para cada \(d>1\) hay \(\varphi(d)\) numeradores reducidos, su suma es \(d\varphi(d)/2\), y las direcciones intercambiadas aportan exactamente lo mismo. El caso diagonal \(d=1\) explica los términos constantes de corrección.
Estas sumas no se recalculan desde cero para cada consulta. A partir de \(\sum_{d\mid n}\varphi(d)=n\) se obtienen las identidades
$$\sum_{q=1}^{n}\Phi\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m=\frac{n(n+1)}{2},$$
$$\sum_{q=1}^{n}q\,\Psi_1\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^2=\frac{n(n+1)(2n+1)}{6},$$
$$\sum_{q=1}^{n}q^2\,\Psi_2\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^3=\left(\frac{n(n+1)}{2}\right)^2.$$
Eso genera recurrencias memoizadas sobre bloques de cocientes \(\left\lfloor n/q\right\rfloor\), que permiten consultar estas funciones muchas veces sin hacer un barrido lineal hasta \(n\).
Tomemos
$$M=\left\lfloor\frac{N}{\ell}\right\rfloor,\qquad M'=\left\lfloor\frac{N}{\ell+1}\right\rfloor,\qquad a=N+1.$$
En cualquier intervalo de \(\ell\) donde \(M\) y \(M'\) permanecen constantes, el recuento de rectas es un polinomio cuadrático en \(\ell\):
$$F_\ell(N)=2a+2\left(q_2\ell^2+q_1\ell+q_0\right),$$
con
$$q_2=s_{\prod}(M)-s_{\prod}(M'),$$
$$q_1=a\bigl(s_{xy}(M')-s_{xy}(M)\bigr)-2s_{\prod}(M'),$$
$$q_0=a^2\bigl(c(M)-c(M')\bigr)+a\,s_{xy}(M')-s_{\prod}(M').$$
Esta es exactamente la fórmula por bloques que usa la implementación.
Los valores de \(\left\lfloor N/\ell\right\rfloor\) solo cambian \(O(\sqrt N)\) veces, así que la suma final se hace bloque por bloque. Para \(\ell\in[L_1,L_2]\), la contribución es
$$\sum_{\ell=L_1}^{L_2}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
Al sustituir el polinomio cuadrático, la implementación solo necesita formas cerradas para
$$\sum 2^\ell,\qquad \sum \ell 2^\ell,\qquad \sum \ell^2 2^\ell,\qquad \sum \ell,\qquad \sum \ell^2,\qquad \sum \ell^3.$$
Las identidades exponenciales empleadas son
$$\sum_{j=0}^{n}2^j=2^{n+1}-1,\qquad \sum_{j=0}^{n}j2^j=(n-1)2^{n+1}+2,$$
$$\sum_{j=0}^{n}j^2 2^j=(n^2-2n+3)2^{n+1}-6.$$
Para la cuadrícula \(5\times5\), la fórmula da
$$F_2(4)=32,\qquad F_3(4)=16,\qquad F_4(4)=12.$$
Entonces
$$\operatorname{NT}(4)=1+25+32(1)+16(4)+12(11)=254,$$
y por tanto
$$T(4)=2^{25}-254=33554178,$$
que coincide con el valor de control usado por la implementación.
Las implementaciones en C++, Python y Java siguen la misma tubería matemática. Primero precalculan valores de la función totiente hasta un límite fijo mediante un cribado lineal, construyen tablas prefix para \(\Phi\), \(\Psi_1\) y \(\Psi_2\), y memorizan los argumentos grandes para no resolver la misma consulta dos veces.
Después, la implementación recorre los bloques distintos de \(\lfloor N/\ell\rfloor\). Dentro de cada bloque evalúa la fórmula cuadrática del número de rectas, aplica las formas cerradas de las sumas exponenciales y polinómicas, acumula el complemento y finalmente lo resta de \(2^{(N+1)^2}\) módulo \(10^8\).
Sea \(B\) el límite de precálculo del totiente y sea \(Q\) el número de valores distintos de \(\lfloor N/\ell\rfloor\); se tiene \(Q=O(\sqrt N)\). El cribado y las tablas prefix cuestan tiempo casi lineal y \(O(B)\) memoria. La suma exterior usa solo \(O(Q)\) bloques de cociente, y las consultas de sumas totiente se comparten entre bloques mediante caché. En la práctica, el coste dominante es la construcción de tablas junto con la aritmética por bloques de escala \(O(\sqrt N)\).
设 \(G_N=\{(x,y)\in\mathbb{Z}^2:0\le x,y\le N\}\)。如果某个有限集合 \(S\subseteq G_N\) 存在一条直线恰好经过 \(S\) 中的两个点，那么 \(S\) 就称为 titanic 集。题目要求计算 \(G_N\) 的 titanic 子集个数 \(T(N)\)，结果按 \(10^8\) 取模。
实现并不直接枚举子集，而是转而统计补集：空集、单点集，以及所有被选点完全共线的更大子集。
核心事实是 Sylvester-Gallai 定理：任意有限且不共线的实平面点集，都存在一条 ordinary line，也就是恰好只经过其中两个点的直线。因此，一个格点子集当且仅当它是空集、单点集，或者全部点共线时，才 不是 titanic 集。
记非 titanic 子集数为 \(\operatorname{NT}(N)\)，则
$$T(N)=2^{(N+1)^2}-\operatorname{NT}(N)\pmod{10^8}.$$
如果某条格点直线恰好包含 \(k\) 个格点，那么支撑在这条直线上的非 titanic 子集，正是大小至少为 \(3\) 的那些子集，因此它的贡献为
$$\sum_{r=3}^{k}\binom{k}{r}=2^k-1-k-\binom{k}{2}.$$
再定义 \(F_\ell(N)\) 为“至少包含 \(\ell+1\) 个格点的格点直线条数”。对一条固定的 \(k\) 点直线，有恒等式
$$\sum_{\ell=2}^{k-1}\bigl(2^\ell-(\ell+1)\bigr)=2^k-1-k-\binom{k}{2}.$$
因此
$$\operatorname{NT}(N)=1+(N+1)^2+\sum_{\ell=2}^{N}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
这样一来，问题就变成了如何快速求出所有 \(\ell\ge2\) 的 \(F_\ell(N)\)。
记 \(a=N+1\)。每一条既非水平也非竖直的格点直线，都对应一个原始步向量 \((u,v)\)，其中 \(1\le v\le u\) 且 \(\gcd(u,v)=1\)。\((u,v)\) 代表斜率族 \(\pm v/u\)；若 \(u\ne v\)，还同时代表交换坐标后的 \(\pm u/v\)。水平线和竖直线单独处理。
对于这样的原始方向，边长方形中的 \(\ell\) 步线段摆放数为
$$C_\ell(u,v)=\max(a-\ell u,0)\max(a-\ell v,0).$$
如果某条直线含有 \(k\) 个格点，那么它恰好提供 \(k-\ell\) 条长度为 \(\ell\) 的线段，以及 \(k-\ell-1\) 条长度为 \(\ell+1\) 的线段。两者之差在且仅在 \(k\ge\ell+1\) 时等于 \(1\)。所以该方向类中“至少含 \(\ell+1\) 个格点”的直线条数就是
$$C_\ell(u,v)-C_{\ell+1}(u,v).$$
再对正负号乘以 \(2\)，并加上 \(a\) 条水平线与 \(a\) 条竖直线，就得到 \(F_\ell(N)\)。
定义
$$\Phi(M)=\sum_{d\le M}\varphi(d),\qquad \Psi_1(M)=\sum_{d\le M} d\,\varphi(d),\qquad \Psi_2(M)=\sum_{d\le M} d^2\varphi(d).$$
实现把原始方向的信息打包成三个累计量：
$$c(M)=2\Phi(M)-1,\qquad s_{xy}(M)=3\Psi_1(M)-1,\qquad s_{\prod}(M)=\Psi_2(M).$$
这些公式来自按较大坐标 \(d\) 分组。对固定 \(d>1\)，既约分子有 \(\varphi(d)\) 个，它们的和是 \(d\varphi(d)/2\)，而交换坐标的方向会再贡献同样的一份。\(d=1\) 的对角线情形则给出常数修正项。
代码不会为每个查询重新累加这些和。由 \(\sum_{d\mid n}\varphi(d)=n\) 可以推出
$$\sum_{q=1}^{n}\Phi\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m=\frac{n(n+1)}{2},$$
$$\sum_{q=1}^{n}q\,\Psi_1\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^2=\frac{n(n+1)(2n+1)}{6},$$
$$\sum_{q=1}^{n}q^2\,\Psi_2\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^3=\left(\frac{n(n+1)}{2}\right)^2.$$
于是可以按 \(\left\lfloor n/q\right\rfloor\) 的商分块写出记忆化递推，这就是实现中大量重复查询仍然高效的原因。
设
$$M=\left\lfloor\frac{N}{\ell}\right\rfloor,\qquad M'=\left\lfloor\frac{N}{\ell+1}\right\rfloor,\qquad a=N+1.$$
在任何一个 \(M\) 与 \(M'\) 都保持不变的 \(\ell\) 区间里，直线条数是 \(\ell\) 的二次多项式：
$$F_\ell(N)=2a+2\left(q_2\ell^2+q_1\ell+q_0\right),$$
其中
$$q_2=s_{\prod}(M)-s_{\prod}(M'),$$
$$q_1=a\bigl(s_{xy}(M')-s_{xy}(M)\bigr)-2s_{\prod}(M'),$$
$$q_0=a^2\bigl(c(M)-c(M')\bigr)+a\,s_{xy}(M')-s_{\prod}(M').$$
这正是实现中实际使用的分块二次公式。
\(\left\lfloor N/\ell\right\rfloor\) 只会改变 \(O(\sqrt N)\) 次，因此最终求和按整段区间进行。对 \(\ell\in[L_1,L_2]\)，贡献为
$$\sum_{\ell=L_1}^{L_2}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
代入二次式以后，只需要
$$\sum 2^\ell,\qquad \sum \ell 2^\ell,\qquad \sum \ell^2 2^\ell,\qquad \sum \ell,\qquad \sum \ell^2,\qquad \sum \ell^3$$
这些闭式。实现使用的指数求和恒等式是
$$\sum_{j=0}^{n}2^j=2^{n+1}-1,\qquad \sum_{j=0}^{n}j2^j=(n-1)2^{n+1}+2,$$
$$\sum_{j=0}^{n}j^2 2^j=(n^2-2n+3)2^{n+1}-6.$$
对 \(5\times5\) 的格点方阵，上式给出
$$F_2(4)=32,\qquad F_3(4)=16,\qquad F_4(4)=12.$$
于是
$$\operatorname{NT}(4)=1+25+32(1)+16(4)+12(11)=254,$$
从而
$$T(4)=2^{25}-254=33554178,$$
与实现内置的校验值完全一致。
C++、Python 和 Java 三个实现遵循同一套数学流程。它们先用线性筛预处理固定范围内的欧拉函数值，建立 \(\Phi\)、\(\Psi_1\)、\(\Psi_2\) 的前缀表，再把更大的参数结果缓存起来，避免重复求值。
之后，实现枚举 \(\lfloor N/\ell\rfloor\) 的所有不同商区间。在每个区间内，它计算二次型的直线条数，套用指数和多项式求和的闭式，累加非 titanic 集合个数，最后再从 \(2^{(N+1)^2}\) 中减去这个补集并对 \(10^8\) 取模。
设 \(B\) 为欧拉函数预处理上界，\(Q\) 为 \(\lfloor N/\ell\rfloor\) 的不同取值个数，则 \(Q=O(\sqrt N)\)。筛法和前缀表构造需要近线性时间以及 \(O(B)\) 内存。外层求和只处理 \(O(Q)\) 个商分块，而大参数的 totient 求和通过缓存跨区间复用。实际运行中，主要开销来自前缀表构造和 \(O(\sqrt N)\) 量级的分块算术。
Пусть \(G_N=\{(x,y)\in\mathbb{Z}^2:0\le x,y\le N\}\). Конечное множество \(S\subseteq G_N\) называется titanic, если существует прямая, проходящая ровно через две точки из \(S\). Нужно вычислить \(T(N)\), то есть число titanic-подмножеств \(G_N\), по модулю \(10^8\).
Реализация не перебирает подмножества напрямую. Вместо этого она считает дополнение: пустое множество, одноточечные множества и более крупные наборы, все выбранные точки которых лежат на одной прямой.
Ключевой факт даёт теорема Сильвестра-Галлаи: любое конечное неколлинеарное множество точек на вещественной плоскости имеет ordinary line, то есть прямую, содержащую ровно две точки множества. Значит, решёточное подмножество не является titanic тогда и только тогда, когда оно пусто, состоит из одной точки или целиком коллинеарно.
Если \(\operatorname{NT}(N)\) обозначает число нетитанических множеств, то
$$T(N)=2^{(N+1)^2}-\operatorname{NT}(N)\pmod{10^8}.$$
Пусть некоторая решёточная прямая содержит ровно \(k\) решёточных точек. Нетитанические подмножества на этой прямой — это в точности подмножества размера не меньше \(3\), поэтому вклад такой прямой равен
$$\sum_{r=3}^{k}\binom{k}{r}=2^k-1-k-\binom{k}{2}.$$
Обозначим через \(F_\ell(N)\) число решёточных прямых, содержащих не менее \(\ell+1\) точек. Для одной фиксированной прямой с \(k\) точками выполняется тождество
$$\sum_{\ell=2}^{k-1}\bigl(2^\ell-(\ell+1)\bigr)=2^k-1-k-\binom{k}{2}.$$
Следовательно,
$$\operatorname{NT}(N)=1+(N+1)^2+\sum_{\ell=2}^{N}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
Тем самым задача сводится к быстрому вычислению \(F_\ell(N)\) для всех \(\ell\ge2\).
Положим \(a=N+1\). Каждая решёточная прямая, не являющаяся горизонтальной или вертикальной, имеет примитивный шаговый вектор \((u,v)\) с \(1\le v\le u\) и \(\gcd(u,v)=1\). Пара \((u,v)\) представляет семейства наклонов \(\pm v/u\), а при \(u\ne v\) ещё и переставленные семейства \(\pm u/v\). Горизонтальные и вертикальные прямые учитываются отдельно.
Для такого примитивного направления число размещений \(\ell\)-шагового отрезка внутри квадрата равно
$$C_\ell(u,v)=\max(a-\ell u,0)\max(a-\ell v,0).$$
Если прямая содержит \(k\) решёточных точек, то она даёт ровно \(k-\ell\) отрезков длины \(\ell\) и \(k-\ell-1\) отрезков длины \(\ell+1\). Разность равна \(1\) тогда и только тогда, когда \(k\ge\ell+1\). Значит, число прямых этого класса направлений, содержащих как минимум \(\ell+1\) точек, равно
$$C_\ell(u,v)-C_{\ell+1}(u,v).$$
После умножения на \(2\) для двух знаков и добавления \(a\) горизонтальных и \(a\) вертикальных прямых получается \(F_\ell(N)\).
Определим
$$\Phi(M)=\sum_{d\le M}\varphi(d),\qquad \Psi_1(M)=\sum_{d\le M} d\,\varphi(d),\qquad \Psi_2(M)=\sum_{d\le M} d^2\varphi(d).$$
В реализации информация о примитивных направлениях упакована в три накопительные функции:
$$c(M)=2\Phi(M)-1,\qquad s_{xy}(M)=3\Psi_1(M)-1,\qquad s_{\prod}(M)=\Psi_2(M).$$
Эти формулы получаются при группировке направлений по большей координате \(d\). Для фиксированного \(d>1\) существует \(\varphi(d)\) несократимых числителей, их сумма равна \(d\varphi(d)/2\), а переставленные направления дают симметричный вклад. Диагональный случай \(d=1\) и порождает постоянные поправки.
Эти суммы не пересчитываются с нуля для каждого аргумента. Из тождества \(\sum_{d\mid n}\varphi(d)=n\) выводятся соотношения
$$\sum_{q=1}^{n}\Phi\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m=\frac{n(n+1)}{2},$$
$$\sum_{q=1}^{n}q\,\Psi_1\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^2=\frac{n(n+1)(2n+1)}{6},$$
$$\sum_{q=1}^{n}q^2\,\Psi_2\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^3=\left(\frac{n(n+1)}{2}\right)^2.$$
Это даёт мемоизированные рекурсии по блокам одинаковых значений \(\left\lfloor n/q\right\rfloor\), поэтому большие аргументы можно многократно запрашивать без линейного прохода до \(n\).
Положим
$$M=\left\lfloor\frac{N}{\ell}\right\rfloor,\qquad M'=\left\lfloor\frac{N}{\ell+1}\right\rfloor,\qquad a=N+1.$$
На любом интервале \(\ell\), где \(M\) и \(M'\) постоянны, число прямых является квадратичным полиномом по \(\ell\):
$$F_\ell(N)=2a+2\left(q_2\ell^2+q_1\ell+q_0\right),$$
где
$$q_2=s_{\prod}(M)-s_{\prod}(M'),$$
$$q_1=a\bigl(s_{xy}(M')-s_{xy}(M)\bigr)-2s_{\prod}(M'),$$
$$q_0=a^2\bigl(c(M)-c(M')\bigr)+a\,s_{xy}(M')-s_{\prod}(M').$$
Именно этот квадратичный блочный вид использует программа.
Значения \(\left\lfloor N/\ell\right\rfloor\) меняются лишь \(O(\sqrt N)\) раз, поэтому конечная сумма считается блоками. Для \(\ell\in[L_1,L_2]\) вклад равен
$$\sum_{\ell=L_1}^{L_2}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
После подстановки квадратичной формы остаются только замкнутые формулы для
$$\sum 2^\ell,\qquad \sum \ell 2^\ell,\qquad \sum \ell^2 2^\ell,\qquad \sum \ell,\qquad \sum \ell^2,\qquad \sum \ell^3.$$
Используемые экспоненциальные тождества таковы:
$$\sum_{j=0}^{n}2^j=2^{n+1}-1,\qquad \sum_{j=0}^{n}j2^j=(n-1)2^{n+1}+2,$$
$$\sum_{j=0}^{n}j^2 2^j=(n^2-2n+3)2^{n+1}-6.$$
Для решётки \(5\times5\) формула даёт
$$F_2(4)=32,\qquad F_3(4)=16,\qquad F_4(4)=12.$$
Значит,
$$\operatorname{NT}(4)=1+25+32(1)+16(4)+12(11)=254,$$
и потому
$$T(4)=2^{25}-254=33554178,$$
что точно совпадает с контрольным значением реализации.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала они вычисляют значения функции Эйлера до фиксированной границы линейным решетом, строят префиксные таблицы для \(\Phi\), \(\Psi_1\) и \(\Psi_2\), а затем кешируют результаты для больших аргументов.
После этого реализация перебирает различные блоки значений \(\lfloor N/\ell\rfloor\). Внутри каждого блока вычисляется квадратичная формула для числа прямых, применяются замкнутые формулы для экспоненциальных и полиномиальных сумм, накапливается дополнение и в самом конце вычитается из \(2^{(N+1)^2}\) по модулю \(10^8\).
Пусть \(B\) — граница предварительного вычисления totient, а \(Q\) — число различных значений \(\lfloor N/\ell\rfloor\); тогда \(Q=O(\sqrt N)\). Решето и префиксные таблицы требуют почти линейного времени и \(O(B)\) памяти. Внешняя сумма использует лишь \(O(Q)\) блоков, а большие сумматорные запросы totient переиспользуются между блоками через кеш. На практике основную стоимость дают построение таблиц и блочная арифметика масштаба \(O(\sqrt N)\).
لتكن \(G_N=\{(x,y)\in\mathbb{Z}^2:0\le x,y\le N\}\). نسمّي المجموعة المنتهية \(S\subseteq G_N\) مجموعة titanic إذا وُجد مستقيم يمرّ عبر نقطتين فقط من نقاط \(S\). المطلوب هو حساب \(T(N)\)، أي عدد المجموعات الجزئية titanic من \(G_N\)، بترديد \(10^8\).
التنفيذ لا يجرّب جميع المجموعات الجزئية مباشرة. بدلاً من ذلك يحسب المتمم: المجموعة الخالية، والمجموعات ذات النقطة الواحدة، والمجموعات الأكبر التي تقع كل نقاطها المختارة على مستقيم واحد.
الحقيقة الأساسية هنا هي مبرهنة Sylvester-Gallai: كل مجموعة منتهية غير مستقيمية في المستوى الحقيقي لها ordinary line، أي مستقيم يحتوي نقطتين فقط من المجموعة. لذلك فإن مجموعة شبكية لا تكون titanic إلا إذا كانت خالية، أو تحوي نقطة واحدة فقط، أو كانت جميع نقاطها على استقامة واحدة.
إذا رمزنا بعدد المجموعات غير titanic بالرمز \(\operatorname{NT}(N)\)، فإن
$$T(N)=2^{(N+1)^2}-\operatorname{NT}(N)\pmod{10^8}.$$
إذا كان مستقيم شبكي ما يحتوي بالضبط على \(k\) نقاط شبكية، فإن المجموعات غير titanic المدعومة على هذا المستقيم هي بالضبط المجموعات التي حجمها لا يقل عن \(3\)، ولذلك يكون مساهمته
$$\sum_{r=3}^{k}\binom{k}{r}=2^k-1-k-\binom{k}{2}.$$
عرّف الآن \(F_\ell(N)\) بأنه عدد المستقيمات الشبكية التي تحتوي على \(\ell+1\) نقطة أو أكثر. ولأي مستقيم ثابت يحوي \(k\) نقاط لدينا الهوية
$$\sum_{\ell=2}^{k-1}\bigl(2^\ell-(\ell+1)\bigr)=2^k-1-k-\binom{k}{2}.$$
ومن ثم
$$\operatorname{NT}(N)=1+(N+1)^2+\sum_{\ell=2}^{N}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
وهكذا تصبح المسألة كلها هي حساب \(F_\ell(N)\) بسرعة لكل \(\ell\ge2\).
لنكتب \(a=N+1\). كل مستقيم شبكي غير أفقي وغير عمودي يملك متجه خطوة أولي \((u,v)\) حيث \(1\le v\le u\) و \(\gcd(u,v)=1\). الزوج \((u,v)\) يمثّل عائلتي الميل \(\pm v/u\)، وإذا كان \(u\ne v\) فإنه يمثّل أيضًا العائلتين المتبادلتين \(\pm u/v\). أما المستقيمات الأفقية والعمودية فتُحسب على حدة.
لذلك الاتجاه الأولي يكون عدد تموضعات قطعة طولها \(\ell\) داخل المربع هو
$$C_\ell(u,v)=\max(a-\ell u,0)\max(a-\ell v,0).$$
إذا احتوى مستقيم ما على \(k\) نقاط شبكية، فإنه يعطي بالضبط \(k-\ell\) قطعًا بطول \(\ell\)، ويعطي \(k-\ell-1\) قطعًا بطول \(\ell+1\). الفرق بينهما يساوي \(1\) بالضبط عندما يكون \(k\ge\ell+1\). لذلك فإن عدد المستقيمات في هذه الفئة الاتجاهية التي تحتوي على \(\ell+1\) نقطة أو أكثر هو
$$C_\ell(u,v)-C_{\ell+1}(u,v).$$
بعد الضرب في \(2\) من أجل الإشارتين وإضافة \(a\) مستقيمًا أفقيًا و\(a\) مستقيمًا عموديًا نحصل على \(F_\ell(N)\).
نعرّف
$$\Phi(M)=\sum_{d\le M}\varphi(d),\qquad \Psi_1(M)=\sum_{d\le M} d\,\varphi(d),\qquad \Psi_2(M)=\sum_{d\le M} d^2\varphi(d).$$
ويجمع التنفيذ معلومات الاتجاهات الأولية في ثلاث كميات تراكمية:
$$c(M)=2\Phi(M)-1,\qquad s_{xy}(M)=3\Psi_1(M)-1,\qquad s_{\prod}(M)=\Psi_2(M).$$
تظهر هذه الصيغ عند تجميع الاتجاهات بحسب الإحداثي الأكبر \(d\). لكل \(d>1\) يوجد \(\varphi(d)\) بسطًا مختزلاً، ومجموع هذه البسوط يساوي \(d\varphi(d)/2\)، كما أن الاتجاهات الناتجة عن تبديل الإحداثيين تعطي الإسهام نفسه. أما الحالة القطرية \(d=1\) فهي التي تولّد حدود التصحيح الثابتة.
هذه المجاميع لا تُعاد من الصفر لكل استعلام. من الهوية \(\sum_{d\mid n}\varphi(d)=n\) نحصل على
$$\sum_{q=1}^{n}\Phi\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m=\frac{n(n+1)}{2},$$
$$\sum_{q=1}^{n}q\,\Psi_1\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^2=\frac{n(n+1)(2n+1)}{6},$$
$$\sum_{q=1}^{n}q^2\,\Psi_2\!\left(\left\lfloor\frac{n}{q}\right\rfloor\right)=\sum_{m=1}^{n}m^3=\left(\frac{n(n+1)}{2}\right)^2.$$
وهذا يقود إلى علاقات تراجعية محفوظة في الذاكرة على كتل القيم المتساوية لـ \(\left\lfloor n/q\right\rfloor\)، ولذلك يمكن استدعاء هذه الدوال كثيرًا من دون مسح خطي حتى \(n\).
لنضع
$$M=\left\lfloor\frac{N}{\ell}\right\rfloor,\qquad M'=\left\lfloor\frac{N}{\ell+1}\right\rfloor,\qquad a=N+1.$$
على أي مجال تبقى فيه \(M\) و\(M'\) ثابتتين، يصبح عدد المستقيمات كثير حدود تربيعيًا في \(\ell\):
$$F_\ell(N)=2a+2\left(q_2\ell^2+q_1\ell+q_0\right),$$
حيث
$$q_2=s_{\prod}(M)-s_{\prod}(M'),$$
$$q_1=a\bigl(s_{xy}(M')-s_{xy}(M)\bigr)-2s_{\prod}(M'),$$
$$q_0=a^2\bigl(c(M)-c(M')\bigr)+a\,s_{xy}(M')-s_{\prod}(M').$$
وهذه هي بالضبط الصيغة التربيعية الكتلية التي يستخدمها التنفيذ.
القيم \(\left\lfloor N/\ell\right\rfloor\) لا تتغير إلا \(O(\sqrt N)\) مرة، لذلك يُنفَّذ الجمع النهائي على شكل كتل. إذا كان \(\ell\in[L_1,L_2]\)، فإن المساهمة تساوي
$$\sum_{\ell=L_1}^{L_2}F_\ell(N)\bigl(2^\ell-(\ell+1)\bigr).$$
بعد التعويض عن كثير الحدود التربيعي، لا يحتاج التنفيذ إلا إلى صيغ مغلقة لـ
$$\sum 2^\ell,\qquad \sum \ell 2^\ell,\qquad \sum \ell^2 2^\ell,\qquad \sum \ell,\qquad \sum \ell^2,\qquad \sum \ell^3.$$
ومن الهويات الأسية المستخدمة
$$\sum_{j=0}^{n}2^j=2^{n+1}-1,\qquad \sum_{j=0}^{n}j2^j=(n-1)2^{n+1}+2,$$
$$\sum_{j=0}^{n}j^2 2^j=(n^2-2n+3)2^{n+1}-6.$$
في الشبكة \(5\times5\) تعطي الصيغة
$$F_2(4)=32,\qquad F_3(4)=16,\qquad F_4(4)=12.$$
ومن ثم
$$\operatorname{NT}(4)=1+25+32(1)+16(4)+12(11)=254,$$
وبالتالي
$$T(4)=2^{25}-254=33554178,$$
وهو تمامًا مقدار التحقق الذي تستخدمه الخوارزمية.
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. فهي تحسب أولًا قيم دالة أويلر حتى حد ثابت باستعمال غربال خطي، ثم تبني جداول prefix لـ \(\Phi\) و\(\Psi_1\) و\(\Psi_2\)، وبعد ذلك تخزّن نتائج الوسائط الكبيرة كي لا يُعاد الحساب نفسه.
بعد ذلك يستعرض التنفيذ كتل القيم المختلفة لـ \(\lfloor N/\ell\rfloor\). داخل كل كتلة يقيّم الصيغة التربيعية لعدد المستقيمات، ويطبّق الصيغ المغلقة لمجاميع الحدود الأسية وكثيرات الحدود، ويجمع عدد المجموعات غير titanic، ثم يطرحه أخيرًا من \(2^{(N+1)^2}\) بترديد \(10^8\).
ليكن \(B\) حدّ التحضير المسبق لقيم totient، وليكن \(Q\) عدد القيم المختلفة لـ \(\lfloor N/\ell\rfloor\)، وعندئذٍ \(Q=O(\sqrt N)\). يحتاج الغربال وجداول prefix إلى زمن شبه خطي وذاكرة \(O(B)\). أما الجمع الخارجي فلا يمر إلا على \(O(Q)\) من الكتل، كما أن استعلامات المجاميع الكبيرة يعاد استخدامها بين هذه الكتل بفضل التخزين المؤقت. عمليًا تهيمن كلفة بناء الجداول مع الحساب الكتلي على مقياس \(O(\sqrt N)\).