For each quadruple \((a,b,c,d)\) with \(1\le a,b,c,d\le m\), consider the lattice quadrilateral with vertices \((a,0)\), \((0,b)\), \((-c,0)\), and \((0,-d)\). The task is to count how many such quadrilaterals contain a perfect-square number of interior lattice points.
The implementations do not inspect lattice points one by one inside each polygon. Instead, they convert the geometry into a closed arithmetic formula for the interior count and then test that value against a precomputed set of squares.
Let \(I(a,b,c,d)\) denote the number of interior lattice points of the quadrilateral determined by \((a,b,c,d)\). The whole problem is therefore to count the quadruples for which \(I(a,b,c,d)\) is a square.
The vertices are visited as
$$ (a,0)\to(0,b)\to(-c,0)\to(0,-d)\to(a,0). $$
Because each vertex lies on one of the coordinate axes, the figure naturally breaks into four right triangles around the origin. That symmetry is what makes the area and boundary formulas compact.
The four triangles have areas \(\frac{ab}{2}\), \(\frac{bc}{2}\), \(\frac{cd}{2}\), and \(\frac{da}{2}\). Adding them gives
$$A=\frac{ab+bc+cd+da}{2}.$$
Factoring the same expression yields an equivalent form that is convenient in code:
$$2A=ab+bc+cd+da=(a+c)(b+d).$$
So the area depends only on simple products of neighboring or opposite side lengths on the axes.
An edge joining \((u,0)\) and \((0,v)\) has displacement \((-u,v)\). A standard lattice-point fact says that such a segment contributes \(\gcd(u,v)\) boundary steps, or equivalently \(\gcd(u,v)+1\) lattice points including both endpoints.
Applying this to the four edges gives the total number of boundary lattice points
$$B=\gcd(a,b)+\gcd(b,c)+\gcd(c,d)+\gcd(d,a).$$
This is the correct polygon-level boundary count: shared vertices are handled automatically by the formula \(B=\sum \gcd(|\Delta x|,|\Delta y|)\).
Pick's theorem states
$$A=I+\frac{B}{2}-1.$$
Solving for the interior count gives
$$I=A-\frac{B}{2}+1=\frac{ab+bc+cd+da-B}{2}+1.$$
Substituting the boundary expression produces the exact arithmetic test used by the implementations:
$$I(a,b,c,d)=\frac{(a+c)(b+d)-\gcd(a,b)-\gcd(b,c)-\gcd(c,d)-\gcd(d,a)}{2}+1.$$
So each quadruple is reduced to one integer, and the geometric question becomes a perfect-square test.
Take \((a,b,c,d)=(2,2,2,1)\). Then
$$2A=(2+2)(2+1)=12,$$
and
$$B=\gcd(2,2)+\gcd(2,2)+\gcd(2,1)+\gcd(1,2)=2+2+1+1=6.$$
Therefore
$$I=\frac{12-6}{2}+1=4.$$
Since \(4=2^2\), this quadruple contributes to the answer. The same formula handles every other quadruple without any geometric case split.
The C++, Python, and Java implementations all follow the same plan. First they precompute \(\gcd(x,y)\) for every \(1\le x,y\le m\). That turns each boundary contribution into a table lookup instead of a fresh gcd computation inside the innermost loop.
Next they precompute all perfect squares up to a safe upper bound. Since \((a+c)(b+d)\le 4m^2\) and \(B\ge 4\), we have
$$I\le \frac{4m^2-4}{2}+1=2m^2-1,$$
so marking squares up to \(2m^2+1\) is comfortably sufficient.
Finally the implementations run four nested loops over \(a\), \(b\), \(c\), and \(d\). Inside those loops they reuse boundary values already determined by the outer indices, evaluate the formula for \(I(a,b,c,d)\), and increment the answer exactly when that value is square.
For the sample case \(m=4\), the full enumeration gives \(42\), which matches the known reference value.
Building the gcd table stores \(O(m^2)\) values and needs \(O(m^2\log m)\) arithmetic if each entry is computed with the Euclidean algorithm. Marking all relevant squares is \(O(m)\) time with an \(O(m^2)\)-sized lookup table under the bound above. The dominant cost is the exhaustive scan of all \(m^4\) quadruples, with only \(O(1)\) work per quadruple after precomputation. Therefore the overall complexity is \(O(m^4)\) time and \(O(m^2)\) memory.
Für jedes Tupel \((a,b,c,d)\) mit \(1\le a,b,c,d\le m\) betrachten wir das Gittervierseit mit den Eckpunkten \((a,0)\), \((0,b)\), \((-c,0)\) und \((0,-d)\). Gesucht ist die Anzahl der Fälle, in denen die Zahl der inneren Gitterpunkte ein Quadrat ist.
Die Implementierungen zählen diese inneren Punkte nicht einzeln aus. Stattdessen wird die Geometrie auf eine geschlossene arithmetische Formel reduziert, und anschließend wird nur noch geprüft, ob der so erhaltene Wert eine Quadratzahl ist.
Sei \(I(a,b,c,d)\) die Anzahl der inneren Gitterpunkte des durch \((a,b,c,d)\) bestimmten Vierecks. Das Problem besteht also darin, genau die Tupel zu zählen, für die \(I(a,b,c,d)\) eine Quadratzahl ist.
Die Eckpunkte werden in der Reihenfolge
$$ (a,0)\to(0,b)\to(-c,0)\to(0,-d)\to(a,0) $$
durchlaufen. Da jeder Eckpunkt auf einer Koordinatenachse liegt, zerfällt die Figur auf natürliche Weise in vier rechtwinklige Dreiecke um den Ursprung. Genau diese Symmetrie macht die späteren Formeln so kurz.
Die vier Dreiecke haben die Flächen \(\frac{ab}{2}\), \(\frac{bc}{2}\), \(\frac{cd}{2}\) und \(\frac{da}{2}\). Daher gilt
$$A=\frac{ab+bc+cd+da}{2}.$$
Dieselbe Summe lässt sich auch faktorisiert schreiben:
$$2A=ab+bc+cd+da=(a+c)(b+d).$$
So hängt die Fläche nur von einfachen Produkten benachbarter beziehungsweise gegenüberliegender Achsenlängen ab.
Eine Kante von \((u,0)\) nach \((0,v)\) hat den Verschiebungsvektor \((-u,v)\). Für solche Gitterstrecken ist bekannt, dass sie \(\gcd(u,v)\) Gitterabschnitte beziehungsweise \(\gcd(u,v)+1\) Gitterpunkte inklusive der Endpunkte enthalten.
Auf die vier Kanten angewandt ergibt das die Gesamtzahl der Randgitterpunkte
$$B=\gcd(a,b)+\gcd(b,c)+\gcd(c,d)+\gcd(d,a).$$
Das ist bereits die richtige Randzahl des gesamten Polygons; gemeinsam genutzte Eckpunkte werden durch die Standardformel \(B=\sum \gcd(|\Delta x|,|\Delta y|)\) korrekt berücksichtigt.
Der Satz von Pick lautet
$$A=I+\frac{B}{2}-1.$$
Nach \(I\) aufgelöst erhält man
$$I=A-\frac{B}{2}+1=\frac{ab+bc+cd+da-B}{2}+1.$$
Mit dem Randterm eingesetzt entsteht genau der Test, den die Implementierungen verwenden:
$$I(a,b,c,d)=\frac{(a+c)(b+d)-\gcd(a,b)-\gcd(b,c)-\gcd(c,d)-\gcd(d,a)}{2}+1.$$
Damit wird jedes Tupel auf eine einzige ganze Zahl reduziert, und die geometrische Frage lautet nur noch: Ist diese Zahl ein Quadrat?
Nehmen wir \((a,b,c,d)=(2,2,2,1)\). Dann gilt
$$2A=(2+2)(2+1)=12,$$
und
$$B=\gcd(2,2)+\gcd(2,2)+\gcd(2,1)+\gcd(1,2)=2+2+1+1=6.$$
Also folgt
$$I=\frac{12-6}{2}+1=4.$$
Da \(4=2^2\) ist, trägt dieses Tupel zum Ergebnis bei. Dieselbe Formel behandelt alle anderen Tupel ohne zusätzliche geometrische Fallunterscheidung.
Die C++-, Python- und Java-Implementierungen folgen demselben Schema. Zuerst wird \(\gcd(x,y)\) für alle \(1\le x,y\le m\) vorab berechnet. Dadurch wird jeder Randbeitrag in der innersten Schleife zu einem Tabellenzugriff statt zu einer neuen ggT-Berechnung.
Anschließend werden alle Quadratzahlen bis zu einer sicheren Obergrenze markiert. Wegen \((a+c)(b+d)\le 4m^2\) und \(B\ge 4\) gilt
$$I\le \frac{4m^2-4}{2}+1=2m^2-1,$$
sodass das Markieren aller Quadrate bis \(2m^2+1\) bequem ausreicht.
Danach durchlaufen die Implementierungen vier geschachtelte Schleifen über \(a\), \(b\), \(c\) und \(d\). In diesen Schleifen werden bereits bekannte Randwerte wiederverwendet, die Formel für \(I(a,b,c,d)\) ausgewertet und das Ergebnis genau dann erhöht, wenn dieser Wert eine Quadratzahl ist.
Für den Beispielwert \(m=4\) liefert die vollständige Enumeration \(42\), also genau den bekannten Referenzwert.
Die ggT-Tabelle speichert \(O(m^2)\) Werte und benötigt \(O(m^2\log m)\) Rechenarbeit, wenn jeder Eintrag mit dem euklidischen Algorithmus erzeugt wird. Das Markieren aller relevanten Quadrate kostet \(O(m)\) Zeit bei einer Nachschlagetabelle der Größe \(O(m^2)\). Dominant ist die vollständige Durchmusterung aller \(m^4\) Tupel, wobei nach der Vorberechnung pro Tupel nur noch \(O(1)\) Arbeit anfällt. Insgesamt ergibt sich also \(O(m^4)\) Zeit und \(O(m^2)\) Speicher.
\(1\le a,b,c,d\le m\) koşulunu sağlayan her \((a,b,c,d)\) dörtlüsü için köşeleri \((a,0)\), \((0,b)\), \((-c,0)\) ve \((0,-d)\) olan bir kafes dörtgeni kurulur. Amaç, iç kafes nokta sayısı tam kare olan dörtgenlerin sayısını bulmaktır.
Uygulamalar çokgenlerin içindeki noktaları tek tek saymaz. Bunun yerine geometri kapalı bir aritmetik formüle dönüştürülür ve elde edilen iç nokta sayısının tam kare olup olmadığına bakılır.
\(I(a,b,c,d)\), \((a,b,c,d)\) tarafından belirlenen dörtgenin iç kafes nokta sayısı olsun. O halde bütün problem, \(I(a,b,c,d)\) değeri kare olan dörtlüleri saymaktır.
Köşeler şu sırayla dolaşılır:
$$ (a,0)\to(0,b)\to(-c,0)\to(0,-d)\to(a,0). $$
Her köşe koordinat eksenlerinden biri üzerinde olduğundan şekil orijin çevresinde doğal olarak dört dik üçgene ayrılır. Alan ve sınır formüllerinin kısa çıkmasının nedeni bu simetridir.
Dört üçgenin alanları sırasıyla \(\frac{ab}{2}\), \(\frac{bc}{2}\), \(\frac{cd}{2}\) ve \(\frac{da}{2}\) olur. Toplayınca
$$A=\frac{ab+bc+cd+da}{2}$$
elde edilir. Aynı ifade çarpanlara ayrılınca
$$2A=ab+bc+cd+da=(a+c)(b+d)$$
biçimini alır. Böylece alan, eksenler üzerindeki komşu ve karşı uzunlukların basit çarpımlarıyla yazılır.
\((u,0)\) ile \((0,v)\) arasındaki bir kenarın yer değiştirme vektörü \((-u,v)\) olur. Kafes geometride böyle bir doğru parçasının \(\gcd(u,v)\) adet kafes adımı, yani uç noktalar dahil \(\gcd(u,v)+1\) kafes noktası içerdiği bilinir.
Bunu dört kenara uygularsak toplam sınır noktası sayısı
$$B=\gcd(a,b)+\gcd(b,c)+\gcd(c,d)+\gcd(d,a)$$
olur. Bu, çokgen seviyesindeki doğru sınır sayısıdır; ortak köşeler \(B=\sum \gcd(|\Delta x|,|\Delta y|)\) formülüyle otomatik olarak doğru hesaba katılır.
Pick teoremi
$$A=I+\frac{B}{2}-1$$
der. Buradan iç nokta sayısı
$$I=A-\frac{B}{2}+1=\frac{ab+bc+cd+da-B}{2}+1$$
şeklinde bulunur. Sınır ifadesini yerine koyunca uygulamaların kullandığı tam test elde edilir:
$$I(a,b,c,d)=\frac{(a+c)(b+d)-\gcd(a,b)-\gcd(b,c)-\gcd(c,d)-\gcd(d,a)}{2}+1.$$
Böylece her dörtlü tek bir tam sayıya indirgenir ve soru artık sadece bunun tam kare olup olmadığıdır.
\((a,b,c,d)=(2,2,2,1)\) seçelim. O zaman
$$2A=(2+2)(2+1)=12,$$
ve
$$B=\gcd(2,2)+\gcd(2,2)+\gcd(2,1)+\gcd(1,2)=2+2+1+1=6.$$
Dolayısıyla
$$I=\frac{12-6}{2}+1=4.$$
\(4=2^2\) olduğu için bu dörtlü sayıya katkı yapar. Aynı formül bütün diğer dörtlüler için de ek bir geometrik durum ayrımı gerektirmeden çalışır.
C++, Python ve Java uygulamaları aynı planı izler. Önce \(1\le x,y\le m\) için bütün \(\gcd(x,y)\) değerleri önceden hesaplanır. Böylece sınır katkıları en iç döngüde yeni bir EBOB hesabı yerine tablo erişimi olur.
Daha sonra güvenli bir üst sınıra kadar tüm kare sayılar işaretlenir. Çünkü \((a+c)(b+d)\le 4m^2\) ve \(B\ge 4\) olduğundan
$$I\le \frac{4m^2-4}{2}+1=2m^2-1,$$
yani kareleri \(2m^2+1\) sınırına kadar işaretlemek rahatça yeterlidir.
Son olarak uygulamalar \(a\), \(b\), \(c\) ve \(d\) üzerinde dört iç içe döngü çalıştırır. Bu sırada dış döngülerden zaten belli olan sınır katkıları yeniden kullanılır, \(I(a,b,c,d)\) formülü hesaplanır ve yalnızca sonuç kareyse toplam artırılır.
Örnek değer \(m=4\) için tam tarama sonucu \(42\) çıkar; bu da bilinen referans değerdir.
EBOB tablosu \(O(m^2)\) değer saklar ve her giriş Öklid algoritmasıyla hesaplanırsa \(O(m^2\log m)\) işlem gerektirir. İlgili kareleri işaretlemek \(O(m)\) zamanda yapılır ve kullanılan arama tablosu \(O(m^2)\) boyutundadır. Baskın maliyet, tüm \(m^4\) dörtlünün taranmasıdır; ön hesaplamalardan sonra her dörtlü için yalnızca \(O(1)\) iş yapılır. Bu yüzden toplam karmaşıklık \(O(m^4)\) zaman ve \(O(m^2)\) bellektir.
Para cada cuádrupla \((a,b,c,d)\) con \(1\le a,b,c,d\le m\), consideramos el cuadrilátero de retícula cuyos vértices son \((a,0)\), \((0,b)\), \((-c,0)\) y \((0,-d)\). Hay que contar cuántos de esos cuadriláteros tienen un número cuadrado perfecto de puntos interiores de retícula.
Las implementaciones no enumeran punto por punto el interior de cada polígono. En cambio, convierten la geometría en una fórmula aritmética cerrada para el número de puntos interiores y luego comprueban si ese valor es un cuadrado.
Sea \(I(a,b,c,d)\) el número de puntos interiores de retícula del cuadrilátero determinado por \((a,b,c,d)\). Entonces todo el problema consiste en contar las cuádruplas para las que \(I(a,b,c,d)\) es un cuadrado.
Los vértices se recorren como
$$ (a,0)\to(0,b)\to(-c,0)\to(0,-d)\to(a,0). $$
Como cada vértice está sobre uno de los ejes coordenados, la figura se descompone de forma natural en cuatro triángulos rectángulos alrededor del origen. Esa simetría es la razón de que las fórmulas finales sean tan compactas.
Las áreas de esos cuatro triángulos son \(\frac{ab}{2}\), \(\frac{bc}{2}\), \(\frac{cd}{2}\) y \(\frac{da}{2}\). Por tanto,
$$A=\frac{ab+bc+cd+da}{2}.$$
La misma expresión también puede factorizarse como
$$2A=ab+bc+cd+da=(a+c)(b+d).$$
Así, el área queda expresada mediante productos simples de longitudes vecinas y opuestas sobre los ejes.
Un lado que une \((u,0)\) con \((0,v)\) tiene desplazamiento \((-u,v)\). Un hecho clásico de geometría de retícula dice que ese segmento aporta \(\gcd(u,v)\) pasos de retícula, o equivalentemente \(\gcd(u,v)+1\) puntos de retícula contando ambos extremos.
Aplicando esto a los cuatro lados obtenemos el número total de puntos de borde
$$B=\gcd(a,b)+\gcd(b,c)+\gcd(c,d)+\gcd(d,a).$$
Esa es la cuenta correcta de la frontera del polígono completo; los vértices compartidos quedan tratados automáticamente por la fórmula estándar \(B=\sum \gcd(|\Delta x|,|\Delta y|)\).
El teorema de Pick afirma que
$$A=I+\frac{B}{2}-1.$$
Despejando \(I\), se obtiene
$$I=A-\frac{B}{2}+1=\frac{ab+bc+cd+da-B}{2}+1.$$
Sustituyendo la expresión de la frontera aparece exactamente la prueba aritmética usada por las implementaciones:
$$I(a,b,c,d)=\frac{(a+c)(b+d)-\gcd(a,b)-\gcd(b,c)-\gcd(c,d)-\gcd(d,a)}{2}+1.$$
De ese modo, cada cuádrupla se reduce a un único entero y la pregunta geométrica pasa a ser una simple comprobación de cuadrado perfecto.
Tomemos \((a,b,c,d)=(2,2,2,1)\). Entonces
$$2A=(2+2)(2+1)=12,$$
y
$$B=\gcd(2,2)+\gcd(2,2)+\gcd(2,1)+\gcd(1,2)=2+2+1+1=6.$$
Por lo tanto,
$$I=\frac{12-6}{2}+1=4.$$
Como \(4=2^2\), esta cuádrupla sí contribuye al conteo. La misma fórmula sirve para todas las demás sin necesidad de separar casos geométricos.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero precalculan \(\gcd(x,y)\) para todos los pares \(1\le x,y\le m\). Así, cada contribución de frontera se convierte en una consulta a tabla en lugar de recalcular el mcd en la parte más interna.
Después precalculan todos los cuadrados perfectos hasta una cota superior segura. Como \((a+c)(b+d)\le 4m^2\) y \(B\ge 4\), se cumple
$$I\le \frac{4m^2-4}{2}+1=2m^2-1,$$
de modo que marcar los cuadrados hasta \(2m^2+1\) basta con margen.
Por último, las implementaciones recorren con cuatro bucles anidados todos los valores de \(a\), \(b\), \(c\) y \(d\). En el interior reutilizan las contribuciones de borde ya determinadas por los índices exteriores, evalúan la fórmula de \(I(a,b,c,d)\) y aumentan la respuesta solo cuando ese valor es cuadrado.
Para el caso de muestra \(m=4\), la enumeración completa produce \(42\), que es el valor de referencia conocido.
La tabla de mcd almacena \(O(m^2)\) valores y requiere \(O(m^2\log m)\) trabajo si cada entrada se calcula con el algoritmo de Euclides. Marcar todos los cuadrados relevantes cuesta \(O(m)\) tiempo y usa una estructura de consulta de tamaño \(O(m^2)\). El coste dominante es el barrido exhaustivo de las \(m^4\) cuádruplas, con solo \(O(1)\) trabajo por cuádrupla después del precálculo. En conjunto, la complejidad total es \(O(m^4)\) en tiempo y \(O(m^2)\) en memoria.
对每个满足 \(1\le a,b,c,d\le m\) 的四元组 \((a,b,c,d)\)，我们构造一个格点四边形，其顶点分别是 \((a,0)\)、\((0,b)\)、\((-c,0)\) 和 \((0,-d)\)。题目要求统计其中有多少个四边形的内部格点数是完全平方数。
三个实现都没有在每个多边形内部逐点检查，而是先把几何问题化成一个闭式算术公式，再对得到的内部格点数做完全平方判断。真正的难点不是几何构造本身，而是如何把每个四边形快速化简成常数时间计算。
记 \(I(a,b,c,d)\) 为由 \((a,b,c,d)\) 决定的四边形内部格点数。于是整个问题就变成：有多少个四元组使得 \(I(a,b,c,d)\) 恰好是一个平方数。
四边形的顶点按顺时针或逆时针都可以看成下面这个循环顺序：
$$ (a,0)\to(0,b)\to(-c,0)\to(0,-d)\to(a,0). $$
由于四个顶点分别落在四条半轴上，这个图形会自然地围绕原点分解成四个直角三角形。也正因为有这样的对称结构，面积与边界点数都可以写成非常整齐的公式。
围绕原点的四个直角三角形面积分别是 \(\frac{ab}{2}\)、\(\frac{bc}{2}\)、\(\frac{cd}{2}\) 和 \(\frac{da}{2}\)。把它们相加，就得到整个四边形的面积
$$A=\frac{ab+bc+cd+da}{2}.$$
同一个表达式还可以整理成
$$2A=ab+bc+cd+da=(a+c)(b+d).$$
这个乘积形式与实现里的计算方式完全一致，因为它把左右两个水平长度合并成 \(a+c\)，把上下两个竖直长度合并成 \(b+d\)，从而避免重复乘法。
考虑一条从 \((u,0)\) 连到 \((0,v)\) 的边。它的位移向量是 \((-u,v)\)。格点几何中的标准结论告诉我们：这条线段上的格点步数是 \(\gcd(u,v)\)，等价地说，包含两个端点在内的格点总数是 \(\gcd(u,v)+1\)。
把这个事实应用到四条边上，就得到整个四边形的边界格点数
$$B=\gcd(a,b)+\gcd(b,c)+\gcd(c,d)+\gcd(d,a).$$
这里不需要额外处理顶点重复计数的问题，因为对于格点多边形，统一的边界公式本来就是 \(B=\sum \gcd(|\Delta x|,|\Delta y|)\)。四个顶点虽然由相邻边共享，但在这个求和方式下已经被正确吸收进总边界计数里了。
Pick 定理给出
$$A=I+\frac{B}{2}-1.$$
把它改写成内部格点数的形式，可得
$$I=A-\frac{B}{2}+1=\frac{ab+bc+cd+da-B}{2}+1.$$
再把上一步的边界公式代入，就得到实现真正使用的判定式：
$$I(a,b,c,d)=\frac{(a+c)(b+d)-\gcd(a,b)-\gcd(b,c)-\gcd(c,d)-\gcd(d,a)}{2}+1.$$
到这里，几何问题已经完全变成整数运算。对每个四元组，我们只需要算出这个 \(I(a,b,c,d)\)，再判断它是不是完全平方数即可。
取 \((a,b,c,d)=(2,2,2,1)\)。先算面积：
$$2A=(2+2)(2+1)=12.$$
再算边界格点数：
$$B=\gcd(2,2)+\gcd(2,2)+\gcd(2,1)+\gcd(1,2)=2+2+1+1=6.$$
于是内部格点数为
$$I=\frac{12-6}{2}+1=4.$$
因为 \(4=2^2\)，所以这个四元组要计入答案。这个例子同时说明了为什么 gcd 项不能省略：面积本身还不够，边界上的格点数会直接影响内部点数。
C++、Python 和 Java 实现采取的是同一套流程。第一步，预先计算所有 \(1\le x,y\le m\) 的 \(\gcd(x,y)\)，形成一张二维查表。这样在四重循环最内层就不需要重复运行 gcd 运算了，只要读取表中的结果即可。
第二步，预先标记所有可能出现的完全平方数。由于 \((a+c)(b+d)\le 4m^2\)，并且四条边至少各自贡献 1，所以 \(B\ge 4\)。因此
$$I\le \frac{4m^2-4}{2}+1=2m^2-1.$$
这说明只要把不超过 \(2m^2+1\) 的平方数全部标记出来，就一定覆盖了所有可能的内部格点数。
第三步，程序对 \(a\)、\(b\)、\(c\)、\(d\) 做四重枚举。外层索引已经确定时，一部分边界 gcd 值也已经确定，所以实现会复用这些中间结果，让最内层只剩下几次加减乘法、几次表查询，以及一次平方判定。
这种写法的关键是：虽然总共仍要遍历 \(m^4\) 个四元组，但每个四元组的处理已经被压缩成常数时间。对于题目的标准样例 \(m=4\)，完整枚举得到的结果是 \(42\)，与已知参考值一致。
gcd 查表需要存储 \(O(m^2)\) 个整数；如果每个表项都通过欧几里得算法计算，那么预处理时间是 \(O(m^2\log m)\)。完全平方数标记只需要枚举到 \(\sqrt{2m^2+1}\)，因此构建时间是 \(O(m)\)，而布尔查表数组大小为 \(O(m^2)\)。真正的主耗时来自四重循环，总共有 \(m^4\) 个四元组需要检查，而每个四元组在预处理之后只做 \(O(1)\) 工作。因此总时间复杂度是 \(O(m^4)\)，总空间复杂度是 \(O(m^2)\)。
Для каждого набора \((a,b,c,d)\), где \(1\le a,b,c,d\le m\), рассматривается решётчатый четырёхугольник с вершинами \((a,0)\), \((0,b)\), \((-c,0)\) и \((0,-d)\). Требуется посчитать, у скольких таких четырёхугольников число внутренних решётчатых точек является полным квадратом.
Реализации не перебирают точки внутри каждого многоугольника по одной. Вместо этого геометрия переводится в замкнутую арифметическую формулу для числа внутренних точек, после чего остаётся только проверить, является ли полученное число квадратом.
Обозначим через \(I(a,b,c,d)\) число внутренних решётчатых точек четырёхугольника, заданного \((a,b,c,d)\). Тогда вся задача сводится к подсчёту тех четвёрок, для которых \(I(a,b,c,d)\) является квадратом.
Вершины обходятся так:
$$ (a,0)\to(0,b)\to(-c,0)\to(0,-d)\to(a,0). $$
Поскольку каждая вершина лежит на одной из координатных осей, фигура естественным образом распадается на четыре прямоугольных треугольника вокруг начала координат. Именно эта симметрия делает формулы для площади и границы особенно простыми.
Площади четырёх треугольников равны \(\frac{ab}{2}\), \(\frac{bc}{2}\), \(\frac{cd}{2}\) и \(\frac{da}{2}\). Поэтому
$$A=\frac{ab+bc+cd+da}{2}.$$
То же выражение можно записать и в факторизованном виде:
$$2A=ab+bc+cd+da=(a+c)(b+d).$$
Такой вид удобен для реализации, потому что объединяет противоположные длины по горизонтали и вертикали.
Ребро, соединяющее \((u,0)\) и \((0,v)\), имеет вектор смещения \((-u,v)\). Для таких отрезков известно, что число решётчатых шагов на нём равно \(\gcd(u,v)\), а число решётчатых точек с учётом концов равно \(\gcd(u,v)+1\).
Применяя это к четырём сторонам, получаем общее число граничных точек
$$B=\gcd(a,b)+\gcd(b,c)+\gcd(c,d)+\gcd(d,a).$$
Это уже правильный счёт для всей границы многоугольника; общие вершины автоматически учтены стандартной формулой \(B=\sum \gcd(|\Delta x|,|\Delta y|)\).
Теорема Пика утверждает, что
$$A=I+\frac{B}{2}-1.$$
Выразим отсюда число внутренних точек:
$$I=A-\frac{B}{2}+1=\frac{ab+bc+cd+da-B}{2}+1.$$
Подставляя выражение для границы, получаем точную формулу, которую используют реализации:
$$I(a,b,c,d)=\frac{(a+c)(b+d)-\gcd(a,b)-\gcd(b,c)-\gcd(c,d)-\gcd(d,a)}{2}+1.$$
После этого вся геометрическая часть сведена к вычислению одного целого числа и проверке, является ли оно полным квадратом.
Возьмём \((a,b,c,d)=(2,2,2,1)\). Тогда
$$2A=(2+2)(2+1)=12,$$
а также
$$B=\gcd(2,2)+\gcd(2,2)+\gcd(2,1)+\gcd(1,2)=2+2+1+1=6.$$
Следовательно,
$$I=\frac{12-6}{2}+1=4.$$
Так как \(4=2^2\), эта четвёрка входит в ответ. Точно так же обрабатываются все остальные случаи, без дополнительного геометрического разветвления.
Реализации на C++, Python и Java устроены одинаково. Сначала заранее вычисляются все значения \(\gcd(x,y)\) для \(1\le x,y\le m\). Благодаря этому вклад каждой стороны берётся из таблицы, а не пересчитывается заново внутри самой глубокой части перебора.
Затем заранее отмечаются все полные квадраты до безопасной верхней границы. Поскольку \((a+c)(b+d)\le 4m^2\) и \(B\ge 4\), имеем
$$I\le \frac{4m^2-4}{2}+1=2m^2-1,$$
поэтому достаточно пометить квадраты до \(2m^2+1\).
После этого выполняются четыре вложенных цикла по \(a\), \(b\), \(c\) и \(d\). Внутри переиспользуются граничные значения, уже определённые внешними индексами, вычисляется \(I(a,b,c,d)\), и ответ увеличивается тогда и только тогда, когда это число является квадратом.
Для контрольного случая \(m=4\) полный перебор даёт \(42\), что совпадает с известным эталонным значением.
Таблица gcd хранит \(O(m^2)\) значений и требует \(O(m^2\log m)\) вычислений, если каждый элемент строится алгоритмом Евклида. Таблица квадратов строится за \(O(m)\) времени и занимает \(O(m^2)\) памяти в рамках указанной верхней границы. Основной расход времени - это полный перебор всех \(m^4\) четвёрок; после предвычислений на каждую четвёрку приходится только \(O(1)\) операций. Следовательно, общая сложность равна \(O(m^4)\) по времени и \(O(m^2)\) по памяти.
لكل رباعية \((a,b,c,d)\) تحقق \(1\le a,b,c,d\le m\)، ننظر إلى الرباعي الشبكي ذي الرؤوس \((a,0)\) و\((0,b)\) و\((-c,0)\) و\((0,-d)\). المطلوب هو عدّ عدد هذه الأشكال التي يكون فيها عدد نقاط الشبكة الداخلية مربعًا كاملاً.
التنفيذات لا تفحص نقاط الشبكة داخل كل مضلع نقطةً نقطة. بدلاً من ذلك تُحوِّل المسألة الهندسية إلى صيغة حسابية مغلقة لعدد النقاط الداخلية، ثم تختبر هل هذه القيمة مربع كامل أم لا.
لنرمز إلى عدد نقاط الشبكة الداخلية في الرباعي المحدد بالرباعية \((a,b,c,d)\) بالرمز \(I(a,b,c,d)\). عندئذ تصبح المسألة كلها هي عدّ الرباعيات التي يكون فيها \(I(a,b,c,d)\) عددًا مربعًا.
يمكن تتبّع الرؤوس بالترتيب
$$ (a,0)\to(0,b)\to(-c,0)\to(0,-d)\to(a,0). $$
ولأن كل رأس يقع على أحد المحورين، فإن الشكل ينقسم طبيعيًا إلى أربعة مثلثات قائمة حول الأصل. وهذه البنية المتماثلة هي السبب في أن صيغتي المساحة والحدود تخرجان بصورة بسيطة.
مساحات المثلثات الأربعة هي \(\frac{ab}{2}\) و\(\frac{bc}{2}\) و\(\frac{cd}{2}\) و\(\frac{da}{2}\). ومن ثم
$$A=\frac{ab+bc+cd+da}{2}.$$
ويمكن إعادة كتابة المقدار نفسه على الصورة
$$2A=ab+bc+cd+da=(a+c)(b+d).$$
وهذه الصيغة المضروبة مريحة في التنفيذ لأنها تجمع الطولين الأفقيين المتقابلين في \(a+c\) والطولين الرأسيين المتقابلين في \(b+d\).
الحافة الواصلة بين \((u,0)\) و\((0,v)\) لها متجه إزاحة \((-u,v)\). ومن الحقائق القياسية في هندسة الشبكات أن هذا المقطع يحتوي على \(\gcd(u,v)\) خطوات شبكية، أو بصورة مكافئة \(\gcd(u,v)+1\) نقطة شبكية إذا حسبنا الطرفين.
بتطبيق ذلك على الحواف الأربع نحصل على عدد نقاط الحد:
$$B=\gcd(a,b)+\gcd(b,c)+\gcd(c,d)+\gcd(d,a).$$
وهذا هو العدّ الصحيح لحدود المضلع كله؛ فالرؤوس المشتركة بين الحواف تُعالَج تلقائيًا بواسطة الصيغة القياسية \(B=\sum \gcd(|\Delta x|,|\Delta y|)\).
تنص نظرية Pick على أن
$$A=I+\frac{B}{2}-1.$$
وبحلها بالنسبة إلى \(I\) نحصل على
$$I=A-\frac{B}{2}+1=\frac{ab+bc+cd+da-B}{2}+1.$$
وبالتعويض عن \(B\) نحصل على الصيغة الحسابية الدقيقة التي تعتمد عليها التنفيذات:
$$I(a,b,c,d)=\frac{(a+c)(b+d)-\gcd(a,b)-\gcd(b,c)-\gcd(c,d)-\gcd(d,a)}{2}+1.$$
وهكذا تتحول المسألة من سؤال هندسي إلى حساب عدد صحيح واحد لكل رباعية ثم اختبار كونه مربعًا كاملاً.
خذ \((a,b,c,d)=(2,2,2,1)\). عندئذ
$$2A=(2+2)(2+1)=12,$$
وكذلك
$$B=\gcd(2,2)+\gcd(2,2)+\gcd(2,1)+\gcd(1,2)=2+2+1+1=6.$$
إذًا
$$I=\frac{12-6}{2}+1=4.$$
وبما أن \(4=2^2\)، فإن هذه الرباعية تُحتسب ضمن الجواب. والصيغة نفسها تعمل مع جميع الرباعيات الأخرى من دون أي تفريع هندسي إضافي.
تتبع تنفيذات C++ وPython وJava الخطة نفسها. أولاً تُحسب جميع قيم \(\gcd(x,y)\) مسبقًا لكل \(1\le x,y\le m\). وبذلك تصبح مساهمة كل حافة قراءةً من جدول بدلاً من إعادة حساب القاسم المشترك الأكبر في أعمق حلقة.
بعد ذلك تُعلَّم جميع المربعات الكاملة حتى حد أعلى آمن. فبما أن \((a+c)(b+d)\le 4m^2\) و\(B\ge 4\)، فإن
$$I\le \frac{4m^2-4}{2}+1=2m^2-1,$$
ولذلك فإن تعليم المربعات حتى \(2m^2+1\) يكفي بهامش مريح.
ثم تُنفَّذ أربع حلقات متداخلة على \(a\) و\(b\) و\(c\) و\(d\). داخل هذه الحلقات يُعاد استخدام بعض قيم الحدود التي حُددت بالفعل من المؤشرات الخارجية، ثم تُقيَّم صيغة \(I(a,b,c,d)\)، ويُزاد العداد فقط عندما تكون القيمة مربعًا كاملاً.
في حالة العينة \(m=4\)، يعطي هذا التعداد الكامل القيمة \(42\)، وهي القيمة المرجعية المعروفة.
يخزن جدول القاسم المشترك الأكبر \(O(m^2)\) قيمة، وإذا حُسب كل عنصر بخوارزمية إقليدس فإن زمن بنائه يكون \(O(m^2\log m)\). أما جدول المربعات فيُبنى خلال \(O(m)\) زمنًا، ويحتاج إلى مساحة \(O(m^2)\) ضمن الحد الأعلى السابق. الكلفة المهيمنة هي المرور على جميع الرباعيات وعددها \(m^4\)، ومع وجود المعالجة المسبقة يصبح العمل داخل كل رباعية \(O(1)\) فقط. لذلك فالتعقيد الكلي هو \(O(m^4)\) زمنًا و\(O(m^2)\) ذاكرة.