Let
$$G_{m,n}=\{0,1,\dots,m\}\times\{0,1,\dots,n\},\qquad N=(m+1)(n+1).$$
We seek \(Q(m,n)\), the number of simple quadrilaterals whose four vertices are distinct lattice points of \(G_{m,n}\). The checkpoint values used by the implementations are
$$Q(2,2)=94,\quad Q(3,7)=39590,\quad Q(12,3)=309000,\quad Q(123,45)=70542215894646.$$
The actual target is \(Q(12345,6789)\bmod 135707531\).
The solution does not enumerate quadruples directly. Instead it decomposes the problem into four global quantities: collinear triples, collinear quadruples, the total boundary-point count over all lattice triangles, and the total doubled-area count over all lattice triangles.
There are \(\binom{N}{4}\) ways to choose four lattice points. A set is immediately invalid if at least three of its points are collinear, because then no simple quadrilateral can use all four chosen vertices.
For a segment with displacement \((i,j)\), the number of lattice points on the segment equals \(\gcd(i,j)+1\). Therefore the number of interior lattice points on that segment is \(\gcd(i,j)-1\). This gcd rule is the basic ingredient behind the whole counting argument.
Let \(\mathcal{D}\) be the set of all nonzero displacements \((i,j)\) with \(0\le i\le m\) and \(0\le j\le n\). For \((i,j)\in\mathcal{D}\), define
$$g_{i,j}=\gcd(i,j),$$
with the conventions \(\gcd(i,0)=i\) and \(\gcd(0,j)=j\). The number of segments having that displacement is
$$M_{i,j}=\begin{cases} (n+1)(m+1-i), & j=0,\\ (m+1)(n+1-j), & i=0,\\ 2(m+1-i)(n+1-j), & i,j\ge 1. \end{cases}$$
The factor \(2\) in the last case accounts for the two slopes \((i,j)\) and \((i,-j)\). Then
$$L_3=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\bigl(g_{i,j}-1\bigr),\qquad L_4=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\binom{g_{i,j}-1}{2}.$$
Each interior lattice point on a segment produces one collinear triple with the two endpoints, so \(L_3\) is exactly the number of collinear triples. Choosing two interior points on the same segment produces one collinear quadruple, so \(L_4\) is exactly the number of collinear quadruples.
If every collinear triple is extended by an arbitrary fourth point, we count \((N-3)L_3\) bad 4-point sets. A set of four collinear points contains four different triples, so it has been counted four times and must be corrected by subtracting \(3L_4\). Hence
$$C_{\mathrm{bad}}=(N-3)L_3-3L_4.$$
Now consider only 4-point sets with no three collinear. Such a set has exactly two possibilities:
1. The four points are in convex position, and there is exactly one simple quadrilateral.
2. One point lies strictly inside the triangle formed by the other three, and there are exactly three simple quadrilaterals.
So every nondegenerate 4-point set contributes \(1+2t\), where \(t\in\{0,1\}\) is the number of chosen points strictly inside the triangle formed by the other three. Summing over all 4-point sets gives
$$Q(m,n)=\binom{N}{4}-C_{\mathrm{bad}}+2\Theta,$$
where \(\Theta\) is the total number of pairs \((T,P)\) such that \(T\) is a nondegenerate lattice triangle and \(P\) is a lattice point strictly inside \(T\).
For any lattice triangle, Pick's theorem states
$$A=I+\frac{B}{2}-1,$$
where \(A\) is the area, \(I\) the number of interior lattice points, and \(B\) the number of boundary lattice points. In doubled-area form this becomes
$$2A=2I+B-2.$$
Summing over all nondegenerate lattice triangles yields
$$2\Theta=S_{\mathrm{A}}-S_{\mathrm{B}}+2T,$$
where \(T=\binom{N}{3}-L_3\) is the number of nondegenerate triangles, \(S_{\mathrm{A}}\) is the total doubled area over all nondegenerate triangles, and \(S_{\mathrm{B}}\) is the total boundary-point sum over all nondegenerate triangles.
For a fixed segment, its contribution to the boundary-point count of every triangle using that segment is exactly \(\gcd(i,j)\). Therefore define
$$S_{\mathrm{seg}}=\sum_{(i,j)\in\mathcal{D}} M_{i,j}g_{i,j}.$$
If we multiply by \(N\), we temporarily pretend that every lattice point can serve as the third vertex. That overcounts points lying on the same maximal lattice line as the segment. If one such line contains \(k\) lattice points, then
$$\sum_{\{A,B\}\subset \ell}\gcd\bigl(|x_B-x_A|,|y_B-y_A|\bigr)=\binom{k+1}{3},$$
because pairs separated by \(r\) primitive steps contribute \(r\), and there are \(k-r\) such pairs. Therefore the forbidden same-line contribution of that line is \(k\binom{k+1}{3}\). Using
$$k\binom{k+1}{3}=2\binom{k}{2}+6\binom{k}{3}+4\binom{k}{4},$$
and summing over all maximal lattice lines, we obtain
$$S_{\mathrm{B}}=N\,S_{\mathrm{seg}}-\left(2\binom{N}{2}+6L_3+4L_4\right).$$
Every nondegenerate triangle has positive horizontal span and positive vertical span. Group triangles by the size \(i\times j\) of their minimal axis-aligned bounding box, where \(1\le i\le m\) and \(1\le j\le n\). Such a box can be translated in
$$w(i,j)=(m+1-i)(n+1-j)$$
different positions.
For a fixed box size, a direct inclusion-exclusion over all boundary placements of the three vertices simplifies to the exact-box doubled-area sum
$$E(i,j)=\frac{i^2+j^2+11i^2j^2-\gcd(i,j)^2}{3}.$$
This is always an integer. For example, \(E(1,1)=4\) and \(E(2,1)=16\), exactly matching direct enumeration in those boxes. Therefore
$$S_{\mathrm{A}}=\sum_{i=1}^{m}\sum_{j=1}^{n} w(i,j)\,E(i,j).$$
Substituting the previous pieces gives the formula implemented in all three languages:
$$\boxed{Q(m,n)=\binom{N}{4}-\bigl((N-3)L_3-3L_4\bigr)+2\binom{N}{3}-2L_3+S_{\mathrm{A}}-S_{\mathrm{B}}.}$$
For \(m=n=2\), we have \(N=9\), \(L_3=8\), \(L_4=0\), \(S_{\mathrm{A}}=140\), and \(S_{\mathrm{B}}=276\). Hence
$$Q(2,2)=\binom{9}{4}-(6\cdot 8)+2\binom{9}{3}-2\cdot 8+140-276=94,$$
which matches the published checkpoint exactly.
The C++, Python, and Java implementations evaluate exactly these aggregated sums. They precompute the gcd-derived coefficients, handle horizontal and vertical segments separately, and run the main double loop over positive box widths and heights. The large target is evaluated modulo the prime \(135707531\), while the smaller checkpoints are also verified with exact integer arithmetic.
The dominant work is the double sum over \(1\le i\le m\) and \(1\le j\le n\), so the running time is \(O(mn)\). The auxiliary tables for squares, multiplicities, and gcd-derived coefficients require \(O(m+n)\) memory. Splitting the outer loop across workers improves wall-clock time but does not change the asymptotic complexity.
Sei
$$G_{m,n}=\{0,1,\dots,m\}\times\{0,1,\dots,n\},\qquad N=(m+1)(n+1).$$
Gesucht ist \(Q(m,n)\), also die Anzahl einfacher Vierecke, deren vier Ecken verschiedene Gitterpunkte aus \(G_{m,n}\) sind. Die in den Implementierungen verwendeten Kontrollwerte lauten
$$Q(2,2)=94,\quad Q(3,7)=39590,\quad Q(12,3)=309000,\quad Q(123,45)=70542215894646.$$
Berechnet werden soll \(Q(12345,6789)\bmod 135707531\).
Die Lösung zählt keine 4-Punkt-Mengen direkt. Stattdessen zerlegt sie das Problem in vier globale Größen: kollineare Tripel, kollineare Vierergruppen, die gesamte Randpunktzahl aller Gitterdreiecke und die gesamte verdoppelte Flächensumme aller Gitterdreiecke.
Es gibt \(\binom{N}{4}\) Möglichkeiten, vier Gitterpunkte zu wählen. Eine solche Menge ist sofort ungültig, wenn mindestens drei ihrer Punkte auf einer Geraden liegen, denn dann kann kein einfaches Viereck alle vier Ecken benutzen.
Für eine Strecke mit Verschiebung \((i,j)\) ist die Anzahl der Gitterpunkte auf der Strecke \(\gcd(i,j)+1\). Daher besitzt die Strecke \(\gcd(i,j)-1\) innere Gitterpunkte. Genau diese ggT-Regel treibt die gesamte Zählung an.
Sei \(\mathcal{D}\) die Menge aller von null verschiedenen Verschiebungen \((i,j)\) mit \(0\le i\le m\) und \(0\le j\le n\). Für \((i,j)\in\mathcal{D}\) definieren wir
$$g_{i,j}=\gcd(i,j),$$
wobei \(\gcd(i,0)=i\) und \(\gcd(0,j)=j\) gelten. Die Anzahl der Strecken mit dieser Verschiebung ist
$$M_{i,j}=\begin{cases} (n+1)(m+1-i), & j=0,\\ (m+1)(n+1-j), & i=0,\\ 2(m+1-i)(n+1-j), & i,j\ge 1. \end{cases}$$
Der Faktor \(2\) im letzten Fall steht für die beiden Steigungen \((i,j)\) und \((i,-j)\). Damit gilt
$$L_3=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\bigl(g_{i,j}-1\bigr),\qquad L_4=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\binom{g_{i,j}-1}{2}.$$
Jeder innere Gitterpunkt einer Strecke bildet zusammen mit den beiden Endpunkten genau ein kollineares Tripel. Daher ist \(L_3\) genau die Anzahl kollinearer Tripel. Entsprechend liefern zwei innere Punkte zusammen mit den Endpunkten genau eine kollineare Vierergruppe, also ist \(L_4\) die Anzahl kollinearer Vierergruppen.
Erweitert man jedes kollineare Tripel um einen beliebigen vierten Punkt, erhält man \((N-3)L_3\) schlechte 4-Punkt-Mengen. Liegen alle vier Punkte auf einer Geraden, dann enthält diese Menge vier verschiedene Tripel und wurde somit viermal gezählt; daher muss man \(3L_4\) abziehen. Also
$$C_{\mathrm{bad}}=(N-3)L_3-3L_4.$$
Betrachte nun nur noch 4-Punkt-Mengen ohne kollineares Tripel. Dann gibt es genau zwei Fälle:
1. Die vier Punkte liegen in konvexer Lage. Dann gibt es genau ein einfaches Viereck.
2. Ein Punkt liegt strikt im Inneren des von den anderen drei Punkten gebildeten Dreiecks. Dann gibt es genau drei einfache Vierecke.
Jede nichtdegenerierte 4-Punkt-Menge trägt also \(1+2t\) bei, wobei \(t\in\{0,1\}\) die Anzahl ausgewählter Punkte im Inneren des von den anderen drei Punkten gebildeten Dreiecks bezeichnet. Summiert über alle 4-Punkt-Mengen ergibt das
$$Q(m,n)=\binom{N}{4}-C_{\mathrm{bad}}+2\Theta,$$
wobei \(\Theta\) die Anzahl aller Paare \((T,P)\) ist, für die \(T\) ein nichtdegeneriertes Gitterdreieck und \(P\) ein strikt innerer Gitterpunkt von \(T\) ist.
Für jedes Gitterdreieck gilt nach Pick
$$A=I+\frac{B}{2}-1,$$
wobei \(A\) die Fläche, \(I\) die Anzahl innerer Gitterpunkte und \(B\) die Anzahl der Randgitterpunkte ist. In verdoppelter Flächenform lautet dies
$$2A=2I+B-2.$$
Über alle nichtdegenerierten Gitterdreiecke summiert erhält man
$$2\Theta=S_{\mathrm{A}}-S_{\mathrm{B}}+2T,$$
wobei \(T=\binom{N}{3}-L_3\) die Anzahl nichtdegenerierter Dreiecke ist, \(S_{\mathrm{A}}\) die gesamte verdoppelte Flächensumme und \(S_{\mathrm{B}}\) die gesamte Randpunktzahl dieser Dreiecke.
Für eine feste Strecke ist ihr Beitrag zur Randpunktzahl jedes Dreiecks, das diese Strecke enthält, genau \(\gcd(i,j)\). Daher definieren wir
$$S_{\mathrm{seg}}=\sum_{(i,j)\in\mathcal{D}} M_{i,j}g_{i,j}.$$
Multipliziert man mit \(N\), tut man zunächst so, als könne jeder Gitterpunkt als dritter Eckpunkt dienen. Dabei werden jedoch Punkte auf derselben maximalen Gittergeraden überzählt. Enthält eine solche Gerade \(k\) Gitterpunkte, dann gilt
$$\sum_{\{A,B\}\subset \ell}\gcd\bigl(|x_B-x_A|,|y_B-y_A|\bigr)=\binom{k+1}{3},$$
denn Paare im Abstand von \(r\) primitiven Schritten liefern den Beitrag \(r\), und davon gibt es \(k-r\) Stück. Somit ist der verbotene Beitrag dieser Geraden gleich \(k\binom{k+1}{3}\). Mit
$$k\binom{k+1}{3}=2\binom{k}{2}+6\binom{k}{3}+4\binom{k}{4}$$
und Summation über alle maximalen Gittergeraden folgt
$$S_{\mathrm{B}}=N\,S_{\mathrm{seg}}-\left(2\binom{N}{2}+6L_3+4L_4\right).$$
Jedes nichtdegenerierte Dreieck besitzt positive horizontale und vertikale Spannweite. Gruppiere daher alle Dreiecke nach der Größe \(i\times j\) ihrer minimalen achsenparallelen Bounding-Box mit \(1\le i\le m\) und \(1\le j\le n\). Eine solche Box kann auf
$$w(i,j)=(m+1-i)(n+1-j)$$
verschiedene Arten verschoben werden.
Für feste Boxgröße vereinfacht eine direkte Inklusions-Exklusions-Auswertung aller Randlagen der drei Ecken zur geschlossenen Formel
$$E(i,j)=\frac{i^2+j^2+11i^2j^2-\gcd(i,j)^2}{3}.$$
Dieser Wert ist stets ganzzahlig. Beispielsweise gilt \(E(1,1)=4\) und \(E(2,1)=16\), genau wie bei direkter Enumeration in diesen Boxen. Also
$$S_{\mathrm{A}}=\sum_{i=1}^{m}\sum_{j=1}^{n} w(i,j)\,E(i,j).$$
Setzt man alles zusammen, erhält man die in allen drei Sprachen implementierte Formel:
$$\boxed{Q(m,n)=\binom{N}{4}-\bigl((N-3)L_3-3L_4\bigr)+2\binom{N}{3}-2L_3+S_{\mathrm{A}}-S_{\mathrm{B}}.}$$
Für \(m=n=2\) gilt \(N=9\), \(L_3=8\), \(L_4=0\), \(S_{\mathrm{A}}=140\) und \(S_{\mathrm{B}}=276\). Daher
$$Q(2,2)=\binom{9}{4}-(6\cdot 8)+2\binom{9}{3}-2\cdot 8+140-276=94,$$
also exakt der Kontrollwert.
Die C++-, Python- und Java-Implementierungen werten genau diese aggregierten Summen aus. Sie berechnen die ggT-basierten Koeffizienten vorab, behandeln horizontale und vertikale Strecken getrennt und durchlaufen dann die doppelte Schleife über positive Boxbreiten und -höhen. Das große Ziel wird modulo der Primzahl \(135707531\) berechnet; die kleineren Kontrollwerte werden zusätzlich mit exakter Ganzzahlarithmetik geprüft.
Der dominierende Aufwand ist die doppelte Summe über \(1\le i\le m\) und \(1\le j\le n\), also \(O(mn)\) Zeit. Die Hilfstabellen für Quadrate, Multiplizitäten und ggT-abgeleitete Koeffizienten benötigen \(O(m+n)\) Speicher. Parallelisierung der äußeren Schleife verkürzt die Laufzeit in der Praxis, ändert aber nicht die asymptotische Komplexität.
Tanım:
$$G_{m,n}=\{0,1,\dots,m\}\times\{0,1,\dots,n\},\qquad N=(m+1)(n+1).$$
Aranan \(Q(m,n)\), yani köşeleri \(G_{m,n}\) içindeki farklı kafes noktaları olan basit dörtgenlerin sayısıdır. Uygulamalarda kullanılan kontrol değerleri şunlardır:
$$Q(2,2)=94,\quad Q(3,7)=39590,\quad Q(12,3)=309000,\quad Q(123,45)=70542215894646.$$
Asıl hedef \(Q(12345,6789)\bmod 135707531\) değeridir.
Çözüm doğrudan dörtlü nokta taraması yapmaz. Bunun yerine problemi dört küresel büyüklüğe ayırır: doğrusal üçlüler, doğrusal dörtlüler, tüm kafes üçgenlerinin toplam sınır-nokta sayısı ve tüm kafes üçgenlerinin toplam iki kat alanı.
Dört kafes noktası seçmenin \(\binom{N}{4}\) yolu vardır. Bu seçimin içinde en az üç nokta aynı doğru üzerinde ise seçim hemen geçersizdir; çünkü böyle bir durumda dört köşenin tamamını kullanan basit bir dörtgen oluşamaz.
\((i,j)\) yer değiştirmesine sahip bir doğru parçası üzerinde toplam \(\gcd(i,j)+1\) kafes noktası bulunur. Dolayısıyla iç kafes noktası sayısı \(\gcd(i,j)-1\) olur. Çözümün temelini bu EBOB kuralı oluşturur.
\(0\le i\le m\), \(0\le j\le n\) ve \((i,j)\ne(0,0)\) olan tüm yer değiştirmelerin kümesine \(\mathcal{D}\) diyelim. Her \((i,j)\in\mathcal{D}\) için
$$g_{i,j}=\gcd(i,j)$$
tanımını yapalım; burada \(\gcd(i,0)=i\) ve \(\gcd(0,j)=j\) kabul edilir. Bu yer değiştirmeye sahip doğru parçası sayısı
$$M_{i,j}=\begin{cases} (n+1)(m+1-i), & j=0,\\ (m+1)(n+1-j), & i=0,\\ 2(m+1-i)(n+1-j), & i,j\ge 1. \end{cases}$$
Son satırdaki \(2\) çarpanı \((i,j)\) ve \((i,-j)\) eğimlerini birlikte sayar. Böylece
$$L_3=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\bigl(g_{i,j}-1\bigr),\qquad L_4=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\binom{g_{i,j}-1}{2}.$$
Bir doğru parçası üzerindeki her iç nokta, iki uç nokta ile birlikte tek bir doğrusal üçlü oluşturur; dolayısıyla \(L_3\) tam olarak doğrusal üçlü sayısıdır. Aynı şekilde iki iç nokta seçmek, uç noktalarla birlikte tek bir doğrusal dörtlü verir; bu yüzden \(L_4\) doğrusal dörtlü sayısıdır.
Her doğrusal üçlüye keyfi bir dördüncü nokta eklersek \((N-3)L_3\) adet kötü 4-nokta kümesi sayarız. Dört nokta tek bir doğru üzerinde olduğunda bu küme dört farklı üçlü içerir ve dört kez sayılmış olur; bu nedenle \(3L_4\) çıkarılmalıdır. Sonuç:
$$C_{\mathrm{bad}}=(N-3)L_3-3L_4.$$
Şimdi doğrusal üçlü içermeyen 4-nokta kümelerine bakalım. Burada yalnızca iki durum vardır:
1. Dört nokta konveks konumdadır; tam bir basit dörtgen vardır.
2. Noktalardan biri, diğer üç noktanın oluşturduğu üçgenin içinde kalır; bu durumda tam üç basit dörtgen vardır.
Dolayısıyla her geçerli 4-nokta kümesi \(1+2t\) katkısı yapar; burada \(t\in\{0,1\}\), diğer üç noktanın oluşturduğu üçgenin içinde kalan seçili nokta sayısıdır. Toplamda
$$Q(m,n)=\binom{N}{4}-C_{\mathrm{bad}}+2\Theta$$
elde edilir. Burada \(\Theta\), \(T\) bir dejenere olmayan kafes üçgeni ve \(P\) de \(T\)'nin içinde kalan bir kafes noktası olmak üzere tüm \((T,P)\) çiftlerinin sayısıdır.
Her kafes üçgeni için Pick teoremi
$$A=I+\frac{B}{2}-1$$
der. Burada \(A\) alan, \(I\) iç kafes noktası sayısı, \(B\) ise sınır kafes noktası sayısıdır. İki kat alan biçiminde
$$2A=2I+B-2$$
olur. Tüm dejenere olmayan kafes üçgenleri üzerinde toplanırsa
$$2\Theta=S_{\mathrm{A}}-S_{\mathrm{B}}+2T$$
elde edilir. Burada \(T=\binom{N}{3}-L_3\) dejenere olmayan üçgen sayısı, \(S_{\mathrm{A}}\) toplam iki kat alan, \(S_{\mathrm{B}}\) ise toplam sınır-nokta sayısıdır.
Sabit bir doğru parçasının, onu kullanan her üçgenin sınır-nokta sayısına katkısı tam olarak \(\gcd(i,j)\)'dir. Bu yüzden
$$S_{\mathrm{seg}}=\sum_{(i,j)\in\mathcal{D}} M_{i,j}g_{i,j}$$
tanımını yaparız. Bunu \(N\) ile çarpmak, her kafes noktasını üçüncü köşe adayıymış gibi saymak demektir. Fakat aynı maksimum kafes doğrusu üzerindeki noktalar bu şekilde fazla sayılır. Bir böyle doğru \(k\) kafes noktası içeriyorsa
$$\sum_{\{A,B\}\subset \ell}\gcd\bigl(|x_B-x_A|,|y_B-y_A|\bigr)=\binom{k+1}{3}$$
olur; çünkü aralarında \(r\) ilkel adım bulunan her çift \(r\) katkısı yapar ve böyle çiftlerden \(k-r\) tane vardır. O halde bu doğrunun yasak katkısı \(k\binom{k+1}{3}\) olur. Şu özdeşlik ile
$$k\binom{k+1}{3}=2\binom{k}{2}+6\binom{k}{3}+4\binom{k}{4}$$
ve tüm maksimum kafes doğruları üzerinde toplam alarak
$$S_{\mathrm{B}}=N\,S_{\mathrm{seg}}-\left(2\binom{N}{2}+6L_3+4L_4\right)$$
sonucuna ulaşırız.
Dejenere olmayan her üçgenin yatay ve düşey açıklığı pozitiftir. Bu yüzden üçgenleri, en küçük eksenlere paralel çevreleyen kutularının \(i\times j\) boyutuna göre gruplarız; burada \(1\le i\le m\) ve \(1\le j\le n\). Böyle bir kutu
$$w(i,j)=(m+1-i)(n+1-j)$$
farklı konuma taşınabilir.
Sabit bir kutu boyutu için, üç köşenin tüm sınır yerleşimlerine uygulanan doğrudan bir dahil etme-hariç tutma hesabı şu kapalı ifadeye indirgenir:
$$E(i,j)=\frac{i^2+j^2+11i^2j^2-\gcd(i,j)^2}{3}.$$
Bu değer her zaman tam sayıdır. Örneğin \(E(1,1)=4\) ve \(E(2,1)=16\) olup, bu kutular içindeki doğrudan sayımla tam uyumludur. Dolayısıyla
$$S_{\mathrm{A}}=\sum_{i=1}^{m}\sum_{j=1}^{n} w(i,j)\,E(i,j)$$
olur.
Önceki parçaları birleştirince, üç dildeki uygulamaların kullandığı formül elde edilir:
$$\boxed{Q(m,n)=\binom{N}{4}-\bigl((N-3)L_3-3L_4\bigr)+2\binom{N}{3}-2L_3+S_{\mathrm{A}}-S_{\mathrm{B}}.}$$
\(m=n=2\) için \(N=9\), \(L_3=8\), \(L_4=0\), \(S_{\mathrm{A}}=140\) ve \(S_{\mathrm{B}}=276\) bulunur. Böylece
$$Q(2,2)=\binom{9}{4}-(6\cdot 8)+2\binom{9}{3}-2\cdot 8+140-276=94$$
elde edilir; bu da kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları bu toplamları doğrudan hesaplar. Önce EBOB tabanlı katsayılar önceden hazırlanır, yatay ve düşey doğru parçaları ayrı ele alınır, sonra pozitif kutu genişliği ve yüksekliği üzerinde ana çift döngü çalıştırılır. Büyük hedef değer asal modül \(135707531\) altında hesaplanır; küçük kontrol örnekleri ise ayrıca tam sayı aritmetiğiyle doğrulanır.
Baskın maliyet \(1\le i\le m\) ve \(1\le j\le n\) üzerindeki çift toplamdır; dolayısıyla süre karmaşıklığı \(O(mn)\)'dir. Kareler, çokluklar ve EBOB tabanlı katsayılar için tutulan yardımcı tablolar \(O(m+n)\) bellek kullanır. Dış döngünün paralelleştirilmesi pratikte süreyi düşürür, fakat asimptotik karmaşıklığı değiştirmez.
Sea
$$G_{m,n}=\{0,1,\dots,m\}\times\{0,1,\dots,n\},\qquad N=(m+1)(n+1).$$
Buscamos \(Q(m,n)\), el número de cuadriláteros simples cuyas cuatro esquinas son puntos de la red en \(G_{m,n}\). Los valores de control usados por las implementaciones son
$$Q(2,2)=94,\quad Q(3,7)=39590,\quad Q(12,3)=309000,\quad Q(123,45)=70542215894646.$$
El objetivo final es \(Q(12345,6789)\bmod 135707531\).
La solución no enumera directamente las 4-tuplas. Reorganiza el problema en cuatro cantidades globales: ternas colineales, cuaternas colineales, la suma total de puntos de frontera sobre todos los triángulos de la red y la suma total de áreas dobles sobre todos esos triángulos.
Hay \(\binom{N}{4}\) formas de elegir cuatro puntos de la red. Una elección es inválida en cuanto contiene tres puntos colineales, porque entonces no existe un cuadrilátero simple que use los cuatro vértices elegidos.
Para un segmento con desplazamiento \((i,j)\), el número de puntos de la red en el segmento es \(\gcd(i,j)+1\). Por tanto, el número de puntos interiores es \(\gcd(i,j)-1\). Esta regla basada en el mcd es la pieza local fundamental.
Sea \(\mathcal{D}\) el conjunto de todos los desplazamientos no nulos \((i,j)\) con \(0\le i\le m\) y \(0\le j\le n\). Para \((i,j)\in\mathcal{D}\), definimos
$$g_{i,j}=\gcd(i,j),$$
con las convenciones \(\gcd(i,0)=i\) y \(\gcd(0,j)=j\). La cantidad de segmentos con ese desplazamiento es
$$M_{i,j}=\begin{cases} (n+1)(m+1-i), & j=0,\\ (m+1)(n+1-j), & i=0,\\ 2(m+1-i)(n+1-j), & i,j\ge 1. \end{cases}$$
El factor \(2\) del último caso cuenta simultáneamente las pendientes \((i,j)\) y \((i,-j)\). Entonces
$$L_3=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\bigl(g_{i,j}-1\bigr),\qquad L_4=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\binom{g_{i,j}-1}{2}.$$
Cada punto interior de un segmento, junto con sus dos extremos, determina exactamente una terna colineal; por eso \(L_3\) es el número total de ternas colineales. De la misma manera, elegir dos puntos interiores del mismo segmento produce exactamente una cuaterna colineal, de modo que \(L_4\) es el número total de cuaternas colineales.
Si prolongamos cada terna colineal con un cuarto punto arbitrario, contamos \((N-3)L_3\) conjuntos malos de cuatro puntos. Un conjunto de cuatro puntos colineales contiene cuatro ternas diferentes y por tanto ha sido contado cuatro veces; hay que corregirlo restando \(3L_4\). Así,
$$C_{\mathrm{bad}}=(N-3)L_3-3L_4.$$
Ahora restringimos la atención a los conjuntos de cuatro puntos sin ternas colineales. Solo pueden ocurrir dos configuraciones:
1. Los cuatro puntos están en posición convexa, y entonces existe exactamente un cuadrilátero simple.
2. Un punto queda estrictamente dentro del triángulo formado por los otros tres, y entonces existen exactamente tres cuadriláteros simples.
Por ello, cada conjunto no degenerado aporta \(1+2t\), donde \(t\in\{0,1\}\) es el número de puntos elegidos que quedan estrictamente dentro del triángulo formado por los otros tres. Sumando sobre todos los conjuntos de cuatro puntos, obtenemos
$$Q(m,n)=\binom{N}{4}-C_{\mathrm{bad}}+2\Theta,$$
donde \(\Theta\) es el número total de pares \((T,P)\) tales que \(T\) es un triángulo no degenerado de la red y \(P\) es un punto de la red estrictamente interior a \(T\).
Para cualquier triángulo de la red, el teorema de Pick afirma
$$A=I+\frac{B}{2}-1,$$
donde \(A\) es el área, \(I\) el número de puntos interiores y \(B\) el número de puntos sobre la frontera. En forma de área doble,
$$2A=2I+B-2.$$
Al sumar sobre todos los triángulos no degenerados se obtiene
$$2\Theta=S_{\mathrm{A}}-S_{\mathrm{B}}+2T,$$
con \(T=\binom{N}{3}-L_3\) igual al número de triángulos no degenerados, \(S_{\mathrm{A}}\) la suma total de áreas dobles y \(S_{\mathrm{B}}\) la suma total de puntos de frontera.
Para un segmento fijo, su contribución al número de puntos de frontera de cualquier triángulo que lo use es exactamente \(\gcd(i,j)\). Por eso definimos
$$S_{\mathrm{seg}}=\sum_{(i,j)\in\mathcal{D}} M_{i,j}g_{i,j}.$$
Si multiplicamos por \(N\), estamos fingiendo que cualquier punto de la red puede ser el tercer vértice. Eso sobrecuenta los puntos que están en la misma recta máxima que el segmento. Si una recta máxima contiene \(k\) puntos de la red, entonces
$$\sum_{\{A,B\}\subset \ell}\gcd\bigl(|x_B-x_A|,|y_B-y_A|\bigr)=\binom{k+1}{3},$$
porque los pares separados por \(r\) pasos primitivos aportan \(r\), y hay \(k-r\) pares de ese tipo. Por tanto, la corrección prohibida de esa recta es \(k\binom{k+1}{3}\). Usando
$$k\binom{k+1}{3}=2\binom{k}{2}+6\binom{k}{3}+4\binom{k}{4},$$
y sumando sobre todas las rectas máximas de la red, llegamos a
$$S_{\mathrm{B}}=N\,S_{\mathrm{seg}}-\left(2\binom{N}{2}+6L_3+4L_4\right).$$
Cada triángulo no degenerado tiene anchura horizontal positiva y altura vertical positiva. Agrupamos por el tamaño \(i\times j\) de su caja envolvente mínima alineada con los ejes, con \(1\le i\le m\) y \(1\le j\le n\). Dicha caja puede trasladarse de
$$w(i,j)=(m+1-i)(n+1-j)$$
formas distintas.
Para un tamaño fijo, una inclusión-exclusión directa sobre todas las posiciones de los tres vértices en la frontera se simplifica en la suma exacta de áreas dobles
$$E(i,j)=\frac{i^2+j^2+11i^2j^2-\gcd(i,j)^2}{3}.$$
Este valor siempre es entero. Por ejemplo, \(E(1,1)=4\) y \(E(2,1)=16\), justo lo que se obtiene por enumeración directa dentro de esas cajas. Por consiguiente,
$$S_{\mathrm{A}}=\sum_{i=1}^{m}\sum_{j=1}^{n} w(i,j)\,E(i,j).$$
Sustituyendo todo lo anterior, obtenemos la fórmula que implementan C++, Python y Java:
$$\boxed{Q(m,n)=\binom{N}{4}-\bigl((N-3)L_3-3L_4\bigr)+2\binom{N}{3}-2L_3+S_{\mathrm{A}}-S_{\mathrm{B}}.}$$
Para \(m=n=2\), se tiene \(N=9\), \(L_3=8\), \(L_4=0\), \(S_{\mathrm{A}}=140\) y \(S_{\mathrm{B}}=276\). Por tanto,
$$Q(2,2)=\binom{9}{4}-(6\cdot 8)+2\binom{9}{3}-2\cdot 8+140-276=94,$$
en acuerdo exacto con el valor de control.
Las implementaciones en C++, Python y Java evalúan exactamente estas sumas agregadas. Precalculan los coeficientes derivados del mcd, tratan por separado los segmentos horizontales y verticales, y ejecutan el doble bucle principal sobre anchuras y alturas positivas de la caja. El objetivo grande se calcula módulo el primo \(135707531\), mientras que los controles pequeños también se comprueban con aritmética entera exacta.
El coste dominante es la doble suma sobre \(1\le i\le m\) y \(1\le j\le n\), así que el tiempo es \(O(mn)\). Las tablas auxiliares de cuadrados, multiplicidades y coeficientes derivados del mcd ocupan \(O(m+n)\) memoria. Paralelizar el bucle exterior mejora el tiempo real de ejecución, pero no cambia la complejidad asintótica.
设
$$G_{m,n}=\{0,1,\dots,m\}\times\{0,1,\dots,n\},\qquad N=(m+1)(n+1).$$
我们要求 \(Q(m,n)\)，即顶点取自 \(G_{m,n}\) 中不同格点的简单四边形个数。实现中使用的校验值为
$$Q(2,2)=94,\quad Q(3,7)=39590,\quad Q(12,3)=309000,\quad Q(123,45)=70542215894646.$$
最终目标是 \(Q(12345,6789)\bmod 135707531\)。
程序并不直接枚举四点组合，而是把问题拆成四个全局统计量：共线三点组、共线四点组、所有格点三角形的总边界点数，以及所有格点三角形的总二倍面积。
从 \(N\) 个格点中选 4 个点共有 \(\binom{N}{4}\) 种方法。如果这 4 个点中至少有 3 个共线，那么它立刻就是无效集合，因为不存在使用这 4 个顶点的简单四边形。
对位移为 \((i,j)\) 的线段，线段上的格点数为 \(\gcd(i,j)+1\)，因此线段内部的格点数为 \(\gcd(i,j)-1\)。整个计数都建立在这条 gcd 规则上。
记 \(\mathcal{D}\) 为所有满足 \(0\le i\le m\)、\(0\le j\le n\)、且 \((i,j)\ne(0,0)\) 的位移集合。 对 \((i,j)\in\mathcal{D}\)，定义
$$g_{i,j}=\gcd(i,j),$$
并约定 \(\gcd(i,0)=i\)、\(\gcd(0,j)=j\)。具有该位移的线段条数是
$$M_{i,j}=\begin{cases} (n+1)(m+1-i), & j=0,\\ (m+1)(n+1-j), & i=0,\\ 2(m+1-i)(n+1-j), & i,j\ge 1. \end{cases}$$
最后一行中的因子 \(2\) 同时计入斜率 \((i,j)\) 和 \((i,-j)\)。于是
$$L_3=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\bigl(g_{i,j}-1\bigr),\qquad L_4=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\binom{g_{i,j}-1}{2}.$$
一条线段上的每个内部格点，与两端点恰好构成一个共线三点组，所以 \(L_3\) 正是全部共线三点组的数目。同理，从同一线段内部选两个点，再配上线段两端点，就得到一个共线四点组，所以 \(L_4\) 正是全部共线四点组的数目。
若把每个共线三点组再配上任意第四点，就得到 \((N-3)L_3\) 个坏的四点集合。若四点本来就全部共线，那么它包含 4 个不同的三点组，因此被重复算了 4 次，必须减去 \(3L_4\)。所以
$$C_{\mathrm{bad}}=(N-3)L_3-3L_4.$$
现在只看不含共线三点组的四点集合。这时只有两种情形：
1. 四点处于凸位置，此时恰好对应一个简单四边形。
2. 其中一个点严格落在另外三个点构成的三角形内部，此时恰好对应三个简单四边形。
因此，每个非退化四点集合的贡献都可写成 \(1+2t\)，其中 \(t\in\{0,1\}\) 表示被选中的点里有多少个严格落在另外三个点构成的三角形内部。把所有四点集合加总，就得到
$$Q(m,n)=\binom{N}{4}-C_{\mathrm{bad}}+2\Theta,$$
其中 \(\Theta\) 表示所有二元组 \((T,P)\) 的总数：\(T\) 是一个非退化格点三角形，\(P\) 是严格位于 \(T\) 内部的格点。
对任意格点三角形，Pick 定理给出
$$A=I+\frac{B}{2}-1,$$
其中 \(A\) 是面积，\(I\) 是内部格点数，\(B\) 是边界格点数。写成二倍面积形式即
$$2A=2I+B-2.$$
对全部非退化格点三角形求和，得到
$$2\Theta=S_{\mathrm{A}}-S_{\mathrm{B}}+2T,$$
这里 \(T=\binom{N}{3}-L_3\) 是非退化三角形总数，\(S_{\mathrm{A}}\) 是全部二倍面积之和， \(S_{\mathrm{B}}\) 是全部边界格点数之和。
对固定线段而言，它对任何包含它的三角形的边界格点数贡献恰好是 \(\gcd(i,j)\)。因此定义
$$S_{\mathrm{seg}}=\sum_{(i,j)\in\mathcal{D}} M_{i,j}g_{i,j}.$$
若把它乘上 \(N\)，等于暂时把每个格点都当成第三个顶点候选。这样会把与线段位于同一条最大格点直线上的点多算进去。若某条这样的直线包含 \(k\) 个格点，则
$$\sum_{\{A,B\}\subset \ell}\gcd\bigl(|x_B-x_A|,|y_B-y_A|\bigr)=\binom{k+1}{3},$$
因为相距 \(r\) 个原始步长的点对贡献 \(r\)，而这样的点对共有 \(k-r\) 个。所以该直线的禁用贡献是 \(k\binom{k+1}{3}\)。再利用
$$k\binom{k+1}{3}=2\binom{k}{2}+6\binom{k}{3}+4\binom{k}{4},$$
对所有最大格点直线求和后得到
$$S_{\mathrm{B}}=N\,S_{\mathrm{seg}}-\left(2\binom{N}{2}+6L_3+4L_4\right).$$
每个非退化三角形都有正的水平跨度和垂直跨度。按其最小轴对齐包围盒的尺寸 \(i\times j\) 分类，其中 \(1\le i\le m\)、\(1\le j\le n\)。这样的包围盒可以平移到
$$w(i,j)=(m+1-i)(n+1-j)$$
个不同位置。
对固定包围盒尺寸，把三角形三个顶点在边界上的所有可能位置做一次直接容斥化简，可得该尺寸下的精确二倍面积总和
$$E(i,j)=\frac{i^2+j^2+11i^2j^2-\gcd(i,j)^2}{3}.$$
这个值总是整数。例如 \(E(1,1)=4\)、\(E(2,1)=16\)，与小包围盒内的直接枚举完全一致。因此
$$S_{\mathrm{A}}=\sum_{i=1}^{m}\sum_{j=1}^{n} w(i,j)\,E(i,j).$$
把前面各部分代回去，就得到三种实现共同使用的闭式：
$$\boxed{Q(m,n)=\binom{N}{4}-\bigl((N-3)L_3-3L_4\bigr)+2\binom{N}{3}-2L_3+S_{\mathrm{A}}-S_{\mathrm{B}}.}$$
当 \(m=n=2\) 时，\(N=9\)，\(L_3=8\)，\(L_4=0\)，\(S_{\mathrm{A}}=140\)，\(S_{\mathrm{B}}=276\)。于是
$$Q(2,2)=\binom{9}{4}-(6\cdot 8)+2\binom{9}{3}-2\cdot 8+140-276=94,$$
恰好与校验值一致。
C++、Python 和 Java 实现都直接计算上述聚合量。它们先预计算由 gcd 导出的系数，分别处理水平和竖直线段，再对所有正的包围盒宽度与高度执行主双重循环。大规模目标在素数模 \(135707531\) 下求值，而较小的校验矩形还会用精确整数运算再次确认。
主耗时来自 \(1\le i\le m\)、\(1\le j\le n\) 上的双重求和，因此时间复杂度是 \(O(mn)\)。保存平方值、出现次数和 gcd 派生系数所需的辅助表规模为 \(O(m+n)\)。把外层循环并行化可以缩短实际运行时间，但不会改变渐近复杂度。
Пусть
$$G_{m,n}=\{0,1,\dots,m\}\times\{0,1,\dots,n\},\qquad N=(m+1)(n+1).$$
Нужно найти \(Q(m,n)\), то есть число простых четырёхугольников, чьи вершины являются различными узлами решётки из \(G_{m,n}\). Контрольные значения, используемые в реализациях, таковы:
$$Q(2,2)=94,\quad Q(3,7)=39590,\quad Q(12,3)=309000,\quad Q(123,45)=70542215894646.$$
Искомая величина: \(Q(12345,6789)\bmod 135707531\).
Программа не перебирает четвёрки точек напрямую. Вместо этого задача раскладывается на четыре глобальные суммы: число коллинеарных троек, число коллинеарных четвёрок, суммарное количество граничных узлов по всем решёточным треугольникам и суммарную удвоенную площадь по всем решёточным треугольникам.
Выбрать четыре узла решётки можно \(\binom{N}{4}\) способами. Если среди выбранных четырёх точек хотя бы три лежат на одной прямой, то такое множество сразу непригодно: простого четырёхугольника с этими четырьмя вершинами не существует.
Для отрезка со смещением \((i,j)\) число решёточных точек на нём равно \(\gcd(i,j)+1\). Следовательно, число внутренних решёточных точек равно \(\gcd(i,j)-1\). Именно это свойство на основе НОД и используется во всех дальнейших подсчётах.
Обозначим через \(\mathcal{D}\) множество всех ненулевых смещений \((i,j)\), где \(0\le i\le m\) и \(0\le j\le n\). Для \((i,j)\in\mathcal{D}\) положим
$$g_{i,j}=\gcd(i,j),$$
причём \(\gcd(i,0)=i\) и \(\gcd(0,j)=j\). Число отрезков с таким смещением равно
$$M_{i,j}=\begin{cases} (n+1)(m+1-i), & j=0,\\ (m+1)(n+1-j), & i=0,\\ 2(m+1-i)(n+1-j), & i,j\ge 1. \end{cases}$$
Множитель \(2\) в последней строке учитывает оба наклона \((i,j)\) и \((i,-j)\). Тогда
$$L_3=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\bigl(g_{i,j}-1\bigr),\qquad L_4=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\binom{g_{i,j}-1}{2}.$$
Каждая внутренняя точка на отрезке вместе с его двумя концами образует ровно одну коллинеарную тройку, поэтому \(L_3\) есть точное число коллинеарных троек. Аналогично, выбор двух внутренних точек на том же отрезке вместе с концами даёт одну коллинеарную четвёрку, значит \(L_4\) есть число коллинеарных четвёрок.
Если к каждой коллинеарной тройке добавить произвольную четвёртую точку, получится \((N-3)L_3\) плохих 4-точечных множеств. Но множество из четырёх точек на одной прямой содержит четыре разные тройки, поэтому оно было посчитано четырежды и требует поправки \(-3L_4\). Следовательно,
$$C_{\mathrm{bad}}=(N-3)L_3-3L_4.$$
Теперь смотрим только на 4-точечные множества без коллинеарной тройки. Возможны ровно два случая:
1. Четыре точки находятся в выпуклом положении, и тогда существует ровно один простой четырёхугольник.
2. Одна точка лежит строго внутри треугольника, образованного тремя другими, и тогда существует ровно три простых четырёхугольника.
Значит, каждое недегенератное множество даёт вклад \(1+2t\), где \(t\in\{0,1\}\) — число выбранных точек, лежащих строго внутри треугольника, построенного на остальных трёх. Суммируя по всем четвёркам, получаем
$$Q(m,n)=\binom{N}{4}-C_{\mathrm{bad}}+2\Theta,$$
где \(\Theta\) — число всех пар \((T,P)\), в которых \(T\) является недегенератным решёточным треугольником, а \(P\) — строго внутренней для него решёточной точкой.
Для любого решёточного треугольника теорема Пика утверждает, что
$$A=I+\frac{B}{2}-1,$$
где \(A\) — площадь, \(I\) — число внутренних точек решётки, \(B\) — число граничных точек решётки. В форме удвоенной площади это записывается как
$$2A=2I+B-2.$$
После суммирования по всем недегенератным решёточным треугольникам имеем
$$2\Theta=S_{\mathrm{A}}-S_{\mathrm{B}}+2T,$$
где \(T=\binom{N}{3}-L_3\) — число недегенератных треугольников, \(S_{\mathrm{A}}\) — суммарная удвоенная площадь, а \(S_{\mathrm{B}}\) — суммарное число граничных точек.
Для фиксированного отрезка его вклад в число граничных точек любого треугольника, содержащего этот отрезок, равен ровно \(\gcd(i,j)\). Поэтому вводим
$$S_{\mathrm{seg}}=\sum_{(i,j)\in\mathcal{D}} M_{i,j}g_{i,j}.$$
Если умножить эту сумму на \(N\), мы временно считаем, будто каждая точка решётки может быть третьей вершиной. Из-за этого пересчитываются точки, лежащие на той же максимальной решёточной прямой, что и отрезок. Если такая прямая содержит \(k\) решёточных точек, то
$$\sum_{\{A,B\}\subset \ell}\gcd\bigl(|x_B-x_A|,|y_B-y_A|\bigr)=\binom{k+1}{3},$$
поскольку пары, удалённые на \(r\) примитивных шагов, дают вклад \(r\), и таких пар ровно \(k-r\). Значит, запрещённый вклад этой прямой равен \(k\binom{k+1}{3}\). Используя тождество
$$k\binom{k+1}{3}=2\binom{k}{2}+6\binom{k}{3}+4\binom{k}{4},$$
и суммируя по всем максимальным решёточным прямым, получаем
$$S_{\mathrm{B}}=N\,S_{\mathrm{seg}}-\left(2\binom{N}{2}+6L_3+4L_4\right).$$
У каждого недегенератного треугольника положительны и горизонтальный, и вертикальный размах. Поэтому группируем треугольники по размерам \(i\times j\) их минимального осево-ориентированного ограничивающего прямоугольника, где \(1\le i\le m\) и \(1\le j\le n\). Такой прямоугольник можно сдвинуть
$$w(i,j)=(m+1-i)(n+1-j)$$
различными способами.
Для фиксированных \(i\) и \(j\) прямое включение-исключение по всем положениям трёх вершин на границе даёт точную формулу для суммарной удвоенной площади:
$$E(i,j)=\frac{i^2+j^2+11i^2j^2-\gcd(i,j)^2}{3}.$$
Это всегда целое число. Например, \(E(1,1)=4\) и \(E(2,1)=16\), что в точности совпадает с прямым перебором внутри таких прямоугольников. Следовательно,
$$S_{\mathrm{A}}=\sum_{i=1}^{m}\sum_{j=1}^{n} w(i,j)\,E(i,j).$$
Подставляя все составные части, получаем формулу, реализованную на C++, Python и Java:
$$\boxed{Q(m,n)=\binom{N}{4}-\bigl((N-3)L_3-3L_4\bigr)+2\binom{N}{3}-2L_3+S_{\mathrm{A}}-S_{\mathrm{B}}.}$$
При \(m=n=2\) имеем \(N=9\), \(L_3=8\), \(L_4=0\), \(S_{\mathrm{A}}=140\), \(S_{\mathrm{B}}=276\). Тогда
$$Q(2,2)=\binom{9}{4}-(6\cdot 8)+2\binom{9}{3}-2\cdot 8+140-276=94,$$
что точно совпадает с контрольным значением.
Реализации на C++, Python и Java вычисляют именно эти агрегированные суммы. Сначала предварительно строятся коэффициенты, зависящие от НОД, затем отдельно обрабатываются горизонтальные и вертикальные отрезки, после чего выполняется основной двойной цикл по положительным ширинам и высотам ограничивающих прямоугольников. Большая целевая задача считается по модулю простого числа \(135707531\), а малые контрольные прямоугольники дополнительно проверяются точной целочисленной арифметикой.
Главный объём работы задаётся двойной суммой по \(1\le i\le m\) и \(1\le j\le n\), поэтому время работы равно \(O(mn)\). Вспомогательные таблицы квадратов, кратностей и коэффициентов, зависящих от НОД, занимают \(O(m+n)\) памяти. Распараллеливание внешнего цикла улучшает реальное время выполнения, но не меняет асимптотику.
ليكن
$$G_{m,n}=\{0,1,\dots,m\}\times\{0,1,\dots,n\},\qquad N=(m+1)(n+1).$$
نريد إيجاد \(Q(m,n)\)، أي عدد الأشكال الرباعية البسيطة التي تكون رؤوسها الأربع نقاطًا شبكية مختلفة من \(G_{m,n}\). قيم التحقق المستخدمة في التنفيذ هي
$$Q(2,2)=94,\quad Q(3,7)=39590,\quad Q(12,3)=309000,\quad Q(123,45)=70542215894646.$$
والهدف النهائي هو \(Q(12345,6789)\bmod 135707531\).
لا يعتمد الحل على تعداد كل رباعية نقاط مباشرة. بدلًا من ذلك يُعاد تنظيم المسألة إلى أربع كميات كلية: الثلاثيات الواقعة على خط واحد، والرباعيات الواقعة على خط واحد، ومجموع نقاط الحدود عبر جميع المثلثات الشبكية، ومجموع المساحات المضاعفة عبر جميع هذه المثلثات.
عدد طرق اختيار أربع نقاط شبكية هو \(\binom{N}{4}\). ويصبح الاختيار غير صالح فورًا إذا احتوى على ثلاث نقاط أو أكثر على استقامة واحدة، لأن شكلًا رباعيًا بسيطًا لا يمكنه استخدام الرؤوس الأربع في هذه الحالة.
إذا كانت إزاحة القطعة المستقيمة هي \((i,j)\)، فإن عدد النقاط الشبكية على القطعة يساوي \(\gcd(i,j)+1\)، ومن ثم يكون عدد النقاط الداخلية على القطعة هو \(\gcd(i,j)-1\). وهذه القاعدة المعتمدة على القاسم المشترك الأكبر هي الأساس المحلي للحساب كله.
لنرمز بـ \(\mathcal{D}\) إلى مجموعة جميع الإزاحات غير الصفرية \((i,j)\) حيث \(0\le i\le m\) و \(0\le j\le n\). لكل \((i,j)\in\mathcal{D}\) نعرّف
$$g_{i,j}=\gcd(i,j),$$
مع الاتفاق على أن \(\gcd(i,0)=i\) و\(\gcd(0,j)=j\). وعدد القطع المستقيمة التي تمتلك هذه الإزاحة هو
$$M_{i,j}=\begin{cases} (n+1)(m+1-i), & j=0,\\ (m+1)(n+1-j), & i=0,\\ 2(m+1-i)(n+1-j), & i,j\ge 1. \end{cases}$$
العامل \(2\) في السطر الأخير يحسب الميلين \((i,j)\) و\((i,-j)\) معًا. وعندئذ
$$L_3=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\bigl(g_{i,j}-1\bigr),\qquad L_4=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\binom{g_{i,j}-1}{2}.$$
كل نقطة داخلية على قطعة مستقيمة، مع طرفي القطعة، تعطي ثلاثية واحدة على خط واحد؛ لذلك فإن \(L_3\) هو بالضبط عدد الثلاثيات المستقيمة. وبالمثل، اختيار نقطتين داخليتين من القطعة نفسها مع الطرفين يعطي رباعية واحدة على خط واحد؛ ومن ثم فإن \(L_4\) هو عدد الرباعيات المستقيمة.
إذا مددنا كل ثلاثية مستقيمة بنقطة رابعة كيفما اتفق، فإننا نحصل على \((N-3)L_3\) من المجموعات الرديئة ذات الأربع نقاط. أما إذا كانت النقاط الأربع نفسها على خط واحد، فإن هذه المجموعة تحتوي على أربع ثلاثيات مختلفة، أي إنها عُدَّت أربع مرات، ولذلك يجب طرح \(3L_4\). إذن
$$C_{\mathrm{bad}}=(N-3)L_3-3L_4.$$
لننظر الآن فقط إلى مجموعات النقاط الأربع التي لا تحتوي على ثلاثية مستقيمة. هنا لا توجد إلا حالتان:
1. النقاط الأربع في وضع محدب، وعندئذ يوجد شكل رباعي بسيط واحد فقط.
2. توجد نقطة واحدة داخل المثلث الذي تصنعه النقاط الثلاث الأخرى، وعندئذ توجد ثلاثة أشكال رباعية بسيطة.
إذًا كل مجموعة غير منحلّة تساهم بمقدار \(1+2t\)، حيث \(t\in\{0,1\}\) هو عدد النقاط المختارة الواقعة بدقة داخل المثلث المتكوّن من النقاط الثلاث الأخرى. وبجمع ذلك على جميع المجموعات نحصل على
$$Q(m,n)=\binom{N}{4}-C_{\mathrm{bad}}+2\Theta,$$
حيث إن \(\Theta\) هو عدد جميع الأزواج \((T,P)\) التي يكون فيها \(T\) مثلثًا شبكيًا غير منحل، و\(P\) نقطة شبكية تقع بدقة داخل \(T\).
لكل مثلث شبكي تقول مبرهنة Pick إن
$$A=I+\frac{B}{2}-1,$$
حيث \(A\) هي المساحة، و\(I\) عدد النقاط الداخلية، و\(B\) عدد نقاط الحدود. وبصيغة المساحة المضاعفة يصبح ذلك
$$2A=2I+B-2.$$
وبعد الجمع على جميع المثلثات الشبكية غير المنحلّة نحصل على
$$2\Theta=S_{\mathrm{A}}-S_{\mathrm{B}}+2T,$$
حيث \(T=\binom{N}{3}-L_3\) هو عدد المثلثات غير المنحلّة، و\(S_{\mathrm{A}}\) هو مجموع المساحات المضاعفة، و\(S_{\mathrm{B}}\) هو مجموع نقاط الحدود.
بالنسبة إلى قطعة مستقيمة ثابتة، فإن مساهمتها في عدد نقاط حدود أي مثلث يستخدمها تساوي تمامًا \(\gcd(i,j)\). لذلك نعرّف
$$S_{\mathrm{seg}}=\sum_{(i,j)\in\mathcal{D}} M_{i,j}g_{i,j}.$$
إذا ضربنا هذه الكمية في \(N\)، فنحن نتظاهر مؤقتًا بأن كل نقطة شبكية يمكن أن تكون الرأس الثالث. لكن هذا يسبب زيادة عدّ للنقاط الواقعة على الخط الشبكي الأعظمي نفسه الذي تقع عليه القطعة. فإذا احتوى مثل هذا الخط على \(k\) نقطة شبكية، فإن
$$\sum_{\{A,B\}\subset \ell}\gcd\bigl(|x_B-x_A|,|y_B-y_A|\bigr)=\binom{k+1}{3},$$
لأن الأزواج التي تفصل بينها \(r\) خطوات أولية تسهم بمقدار \(r\)، وعدد هذه الأزواج هو \(k-r\). ومن ثم فإن المساهمة الممنوعة لذلك الخط هي \(k\binom{k+1}{3}\). وباستخدام الهوية
$$k\binom{k+1}{3}=2\binom{k}{2}+6\binom{k}{3}+4\binom{k}{4},$$
ثم الجمع على جميع الخطوط الشبكية العظمى نحصل على
$$S_{\mathrm{B}}=N\,S_{\mathrm{seg}}-\left(2\binom{N}{2}+6L_3+4L_4\right).$$
كل مثلث غير منحل يملك امتدادًا أفقيًا موجبًا وامتدادًا رأسيًا موجبًا. لذلك نُصنّف المثلثات بحسب حجم الصندوق المحيط الأدنى الموازي للمحاور، أي \(i\times j\)، حيث \(1\le i\le m\) و\(1\le j\le n\). ويمكن نقل هذا الصندوق إلى
$$w(i,j)=(m+1-i)(n+1-j)$$
مواضع مختلفة.
عند تثبيت \(i\) و\(j\)، فإن تطبيق شمول-استبعاد مباشر على جميع أوضاع الرؤوس الثلاثة على الحدود يتبسط إلى الصيغة المغلقة
$$E(i,j)=\frac{i^2+j^2+11i^2j^2-\gcd(i,j)^2}{3}.$$
وهذه قيمة صحيحة دائمًا. على سبيل المثال \(E(1,1)=4\) و\(E(2,1)=16\)، وهو ما يطابق التعداد المباشر داخل هذه الصناديق. وبالتالي
$$S_{\mathrm{A}}=\sum_{i=1}^{m}\sum_{j=1}^{n} w(i,j)\,E(i,j).$$
بالتعويض عن جميع الأجزاء السابقة نحصل على الصيغة التي تطبقها النسخ الثلاث:
$$\boxed{Q(m,n)=\binom{N}{4}-\bigl((N-3)L_3-3L_4\bigr)+2\binom{N}{3}-2L_3+S_{\mathrm{A}}-S_{\mathrm{B}}.}$$
عندما \(m=n=2\) يكون \(N=9\)، و\(L_3=8\)، و\(L_4=0\)، و\(S_{\mathrm{A}}=140\)، و\(S_{\mathrm{B}}=276\). ومن ثم
$$Q(2,2)=\binom{9}{4}-(6\cdot 8)+2\binom{9}{3}-2\cdot 8+140-276=94,$$
وهو يطابق قيمة التحقق تمامًا.
تنفيذات C++ وPython وJava تحسب هذه المجاميع المجمعة مباشرة. فهي تهيئ مسبقًا المعاملات المشتقة من القاسم المشترك الأكبر، وتعالج القطع الأفقية والرأسية على حدة، ثم تشغّل الحلقة المزدوجة الرئيسية على العروض والارتفاعات الموجبة للصناديق المحيطة. وتُحسب المسألة الكبيرة تحت المعيار الأولي \(135707531\)، بينما تُراجع أمثلة التحقق الصغيرة أيضًا بحساب صحيح كامل.
العمل المهيمن هو الجمع المزدوج على \(1\le i\le m\) و\(1\le j\le n\)، ولذلك فإن زمن التنفيذ هو \(O(mn)\). أما الجداول المساعدة الخاصة بالمربعات والمضاعفات والمعاملات المشتقة من القاسم المشترك الأكبر فتحتاج إلى \(O(m+n)\) من الذاكرة. وتقسيم الحلقة الخارجية على عدة عمال يقلل الزمن العملي لكنه لا يغير التعقيد التقاربي.