A lenticular hole is the convex region enclosed by two circles such that both centres are lattice points, the two circles intersect at two distinct lattice points, and the interior of the lens contains no lattice points. A lenticular pair is an ordered radius pair \((r_1,r_2)\) for which such two circles exist. We must count distinct pairs with
$$0 < r_1 \le r_2 \le N.$$
Take two lattice intersection points \(P,Q\). After a translation we may assume
$$P=(0,0),\qquad Q=(a,b).$$
Only the difference vector matters. The code keeps only primitive vectors with
$$\gcd(a,b)=1.$$
If \(a\) and \(b\) had opposite parity, then the midpoint of \(PQ\) would have one integer and one half-integer coordinate, and the perpendicular bisector could not pass through two lattice centres. Since the vector is primitive, the only possible equal-parity case is that both \(a\) and \(b\) are odd. That is exactly why the search runs over primitive odd vectors.
Let
$$s^2 = a^2+b^2.$$
The midpoint of the chord is \((a/2,b/2)\), and the perpendicular direction is \((-b,a)\). Therefore every circle through \(P\) and \(Q\) has centre
$$O_k=\left(\frac{a-kb}{2},\frac{b+ka}{2}\right)$$
for some real parameter \(k\). Because \(a\) and \(b\) are both odd, \(O_k\) is a lattice point exactly when \(k\) is odd. So lattice-centred circles through the chord are indexed by odd integers \(k\).
The radius is the distance from \(O_k\) to \(P\):
$$R_k^2=\left(\frac{a-kb}{2}\right)^2+\left(\frac{b+ka}{2}\right)^2 =\frac{(a^2+b^2)(1+k^2)}{4} =\frac{s^2(1+k^2)}{4}.$$
This is the central formula used throughout the solver.
For a fixed primitive odd \((a,b)\), every odd \(k\) gives a candidate radius. Choosing one circle on each side of the common chord corresponds to parameters \(-m\) and \(n\) with positive odd \(m,n\). Since
$$R_k^2=\frac{s^2(1+k^2)}{4}$$
depends only on \(|k|\), each primitive vector defines a whole increasing sequence of realized radius squares.
Two examples from the problem statement appear immediately:
Family \((a,b)=(1,1)\). Here \(s^2=2\) and the threshold turns out to be \(t=1\). The odd values \(k=1,3,5,7,\ldots\) give
$$R^2=1,5,13,25,\ldots$$
so the pair \((1,5)\) is obtained from \(k=1\) and \(k=7\).
Family \((a,b)=(1,3)\). Here \(s^2=10\) and \(t=3\). Then \(k=3,5,7,\ldots\) gives
$$R^2=25,65,125,\ldots$$
so \((5,\sqrt{65})\) comes from \(k=3\) and \(k=5\).
The subtle part is deciding which odd parameters are actually valid. The lens must not contain any lattice point in its interior. For a fixed chord direction \((a,b)\), lattice points near the chord lie on the parallel lattice lines
$$-bx+ay=c,\qquad c\in\mathbb Z.$$
Because \(\gcd(a,b)=1\), the closest nonzero parallel lines are
$$-bx+ay=\pm 1.$$
It is enough to analyse one of them, say \(-bx+ay=1\), because the other side is symmetric.
Now define
$$A=ax+by.$$
For lattice points on \(-bx+ay=1\), the code shows that the obstruction to keeping such a point outside the lens is controlled by the quadratic expression
$$M(A)=A-\frac{A^2+1}{s^2}.$$
The worst possible obstruction is the maximum of this quantity over all lattice points on that nearest line. If one particular solution of
$$-bx+ay=1$$
is \((x_0,y_0)\), then all other solutions differ by multiples of \((a,b)\), so \(A\) is determined modulo \(s^2\). That is why the code computes one residue
$$A_0=ax_0+by_0,$$
reduces it to the nearest representative
$$r \in [0,s^2/2],$$
and then evaluates
$$M=r-\left\lfloor\frac{r^2+1}{s^2}\right\rfloor.$$
The minimal valid odd parameter is the smallest odd integer not below \(M\), but at least \(1\):
$$t(a,b)=\max\!\Bigl(1,\ \text{odd-ceiling}(M)\Bigr).$$
The key geometric fact is that a lens formed by parameters \(-m\) and \(n\) is valid exactly when
$$m\ge t(a,b),\qquad n\ge t(a,b).$$
So every primitive vector produces not all odd \(k\), but only the odd tail
$$k=t,\ t+2,\ t+4,\ldots$$
until the global radius bound cuts it off.
For a fixed family \((s^2,t)\), the largest admissible odd parameter is determined by
$$R_k \le N \quad\Longleftrightarrow\quad \frac{s^2(1+k^2)}{4}\le N^2.$$
Hence
$$k_{\max}=\text{largest odd }k\text{ with }k^2\le \frac{4N^2}{s^2}-1.$$
The code stores every realized occurrence as
$$\bigl(R^2,\text{sequence id}\bigr).$$
It uses \(R^2\) instead of \(R\) so that equality can be checked exactly with integers and no floating-point comparison is ever needed.
Different primitive vectors can lead to the same radius sequence, so generation is deduplicated by the pair \((s^2,t)\).
After all occurrences are collected and sorted by \(R^2\), each distinct radius receives a small membership set
$$I(R)=\{\text{sequence ids that realize }R\}.$$
A pair \((r_1,r_2)\) is lenticular exactly when the two radii come from at least one common sequence family, namely when
$$I(r_1)\cap I(r_2)\neq\varnothing.$$
So the problem is no longer geometric; it has become a pure set-intersection counting problem.
Let \(c_J\) be the number of distinct radii whose membership set contains a fixed nonempty id-subset \(J\):
$$c_J=\#\{R:J\subseteq I(R)\}.$$
Then \(\binom{c_J}{2}\) counts unordered pairs of distinct radii that share every id in \(J\). Summing over all nonempty \(J\) with alternating signs gives exactly the number of unordered distinct-radius pairs with nonempty intersection:
$$\sum_{J\ne\varnothing}(-1)^{|J|+1}\binom{c_J}{2}.$$
Finally, every realized radius also forms the diagonal pair \((R,R)\), so the solver adds the number of distinct radii at the end.
The implementation validates itself with the values
$$L(10)=30,\qquad L(100)=3442.$$
These are the official sample results from the problem statement and confirm that both the geometric threshold logic and the set-counting phase are correct.
compute_threshold_for_vector carries out the lattice-line analysis above and returns \(t(a,b)\). generate_sequences enumerates all primitive odd vectors, turns each into a deduplicated sequence \((s^2,t,k_{\max})\), and keeps only families that can produce some radius at most \(N\). build_occurrences expands each family into its realized \((R^2,\text{id})\) occurrences. After sorting, the code compresses equal radii into membership sets, accumulates all subset frequencies, applies inclusion-exclusion, and finally adds the diagonal \((R,R)\) pairs.
If \(T\) is the total number of occurrences \((R^2,\text{id})\), sorting costs
$$O(T\log T).$$
Grouping equal radii is linear in \(T\). The inclusion-exclusion stage iterates over all nonempty subsets of each membership set. Since the membership size is empirically tiny (the code caps it at \(8\) for \(N=100000\)), this part stays practical. Memory usage is \(O(T)\).
Ein linsenförmiges Loch ist die konvexe Fläche zwischen zwei Kreisen, so dass beide Mittelpunkte Gitterpunkte sind, die Kreise sich in zwei verschiedenen Gitterpunkten schneiden und das Innere der Linse keine Gitterpunkte enthält. Ein linsenförmiges Paar ist ein geordnetes Radienpaar \((r_1,r_2)\), für das solche zwei Kreise existieren. Gesucht ist die Anzahl verschiedener Paare mit
$$0 < r_1 \le r_2 \le N.$$
Seien \(P,Q\) die beiden Gitter-Schnittpunkte. Nach einer Translation dürfen wir annehmen
$$P=(0,0),\qquad Q=(a,b).$$
Nur der Differenzvektor ist relevant. Der Code behält nur primitive Vektoren mit
$$\gcd(a,b)=1.$$
Hätten \(a\) und \(b\) verschiedene Parität, dann hätte der Mittelpunkt der Sehne eine ganzzahlige und eine halbzahlige Koordinate, und die Mittelsenkrechte könnte nicht durch zwei Gitterzentren laufen. Da der Vektor primitiv ist, bleibt als gleichpariger Fall nur: beide sind ungerade. Genau deshalb iteriert die Lösung nur über primitive ungerade Vektoren.
Setze
$$s^2 = a^2+b^2.$$
Der Mittelpunkt der Sehne ist \((a/2,b/2)\), die senkrechte Richtung ist \((-b,a)\). Daher hat jeder Kreis durch \(P\) und \(Q\) ein Zentrum der Form
$$O_k=\left(\frac{a-kb}{2},\frac{b+ka}{2}\right)$$
für einen reellen Parameter \(k\). Weil \(a\) und \(b\) beide ungerade sind, ist \(O_k\) genau dann ein Gitterpunkt, wenn \(k\) ungerade ist. Somit werden alle solchen Kreise durch ungerade ganze \(k\) parametrisiert.
Der Radius ist der Abstand von \(O_k\) zu \(P\):
$$R_k^2=\left(\frac{a-kb}{2}\right)^2+\left(\frac{b+ka}{2}\right)^2 =\frac{(a^2+b^2)(1+k^2)}{4} =\frac{s^2(1+k^2)}{4}.$$
Das ist die zentrale Formel des ganzen Verfahrens.
Für ein fixes primitives ungerades \((a,b)\) liefert jedes ungerade \(k\) einen Kandidatenradius. Wählt man je einen Kreis auf jeder Seite der Sehne, so entspricht das den Parametern \(-m\) und \(n\) mit positiven ungeraden \(m,n\). Da
$$R_k^2=\frac{s^2(1+k^2)}{4}$$
nur von \(|k|\) abhängt, definiert jeder primitive Vektor eine ganze wachsende Folge realisierbarer Radienquadrate.
Zwei Beispiele aus der Aufgabenstellung erscheinen sofort:
Familie \((a,b)=(1,1)\). Hier ist \(s^2=2\) und der Schwellwert \(t=1\). Für \(k=1,3,5,7,\ldots\) erhält man
$$R^2=1,5,13,25,\ldots,$$
also stammt das Paar \((1,5)\) aus \(k=1\) und \(k=7\).
Familie \((a,b)=(1,3)\). Hier ist \(s^2=10\) und \(t=3\). Dann liefert \(k=3,5,7,\ldots\)
$$R^2=25,65,125,\ldots,$$
also kommt \((5,\sqrt{65})\) von \(k=3\) und \(k=5\).
Der subtile Teil ist die Entscheidung, welche ungeraden Parameter wirklich zulässig sind. Das Innere der Linse darf keine Gitterpunkte enthalten. Für eine feste Sehnenrichtung \((a,b)\) liegen Gitterpunkte nahe der Sehne auf den parallelen Gittergeraden
$$-bx+ay=c,\qquad c\in\mathbb Z.$$
Wegen \(\gcd(a,b)=1\) sind die nächsten nichttrivialen parallelen Geraden
$$-bx+ay=\pm 1.$$
Es genügt, eine Seite zu analysieren, etwa \(-bx+ay=1\), denn die andere ist symmetrisch.
Definiere nun
$$A=ax+by.$$
Für Gitterpunkte auf \(-bx+ay=1\) zeigt der Code, dass das Hindernis für das Herausdrängen solcher Punkte aus der Linse durch den quadratischen Ausdruck
$$M(A)=A-\frac{A^2+1}{s^2}$$
beschrieben wird. Das schlimmste Hindernis ist das Maximum dieser Größe über alle Gitterpunkte auf der nächsten Parallelen.
Ist \((x_0,y_0)\) eine konkrete Lösung von
$$-bx+ay=1,$$
dann unterscheiden sich alle anderen Lösungen um Vielfache von \((a,b)\). Deshalb ist \(A\) nur modulo \(s^2\) relevant. Darum berechnet der Code zuerst
$$A_0=ax_0+by_0,$$
reduziert auf den nächstliegenden Repräsentanten
$$r \in [0,s^2/2],$$
und wertet dann
$$M=r-\left\lfloor\frac{r^2+1}{s^2}\right\rfloor$$
aus. Der kleinste zulässige ungerade Parameter ist die kleinste ungerade Zahl, die nicht unter \(M\) liegt, mindestens aber \(1\):
$$t(a,b)=\max\!\Bigl(1,\ \text{ungerade-Decke}(M)\Bigr).$$
Die geometrische Kernaussage lautet: Eine Linse aus den Parametern \(-m\) und \(n\) ist genau dann gültig, wenn
$$m\ge t(a,b),\qquad n\ge t(a,b).$$
Damit erzeugt jeder primitive Vektor nicht alle ungeraden \(k\), sondern nur den ungeraden Schwanz
$$k=t,\ t+2,\ t+4,\ldots$$
bis die globale Radiusschranke greift.
Für eine feste Familie \((s^2,t)\) bestimmt die Bedingung
$$R_k \le N \quad\Longleftrightarrow\quad \frac{s^2(1+k^2)}{4}\le N^2$$
den größten zulässigen ungeraden Parameter. Also ist
$$k_{\max}=\text{größte ungerade Zahl }k\text{ mit }k^2\le \frac{4N^2}{s^2}-1.$$
Jedes Auftreten wird als
$$\bigl(R^2,\text{Sequenz-ID}\bigr)$$
gespeichert. Verwendet wird \(R^2\) statt \(R\), damit Gleichheit exakt mit ganzen Zahlen geprüft werden kann. Verschiedene primitive Vektoren können dieselbe Radiusfolge erzeugen; deshalb dedupliziert der Code nach dem Paar \((s^2,t)\).
Nach dem Sammeln und Sortieren aller Vorkommen nach \(R^2\) erhält jeder verschiedene Radius eine kleine Mitgliedermenge
$$I(R)=\{\text{Sequenz-IDs, die }R\text{ erzeugen}\}.$$
Ein Paar \((r_1,r_2)\) ist genau dann linsenförmig, wenn die beiden Radien mindestens eine gemeinsame Sequenzfamilie besitzen, also wenn
$$I(r_1)\cap I(r_2)\neq\varnothing.$$
Ab diesem Punkt ist das Problem nicht mehr geometrisch, sondern nur noch eine Aufgabe des Zählens von Mengenüberschneidungen.
Sei \(c_J\) die Anzahl der verschiedenen Radien, deren Mitgliedermenge eine feste nichtleere ID-Teilmenge \(J\) enthält:
$$c_J=\#\{R:J\subseteq I(R)\}.$$
Dann zählt \(\binom{c_J}{2}\) die ungeordneten Paare verschiedener Radien, die alle IDs aus \(J\) gemeinsam haben. Die alternierende Summe über alle nichtleeren \(J\) liefert exakt die Zahl der ungeordneten Paare verschiedener Radien mit nichtleerem Schnitt:
$$\sum_{J\ne\varnothing}(-1)^{|J|+1}\binom{c_J}{2}.$$
Zum Schluss bildet jeder realisierte Radius noch das Diagonalpaar \((R,R)\), daher addiert die Lösung die Anzahl verschiedener Radien hinzu.
Die Implementierung prüft sich mit
$$L(10)=30,\qquad L(100)=3442.$$
Das sind die offiziellen Beispielwerte der Aufgabenstellung und bestätigen, dass sowohl die Geometrie des Schwellwerts als auch die Mengen-Zählung korrekt umgesetzt sind.
compute_threshold_for_vector implementiert die beschriebene Analyse der nächsten Gittergeraden und liefert \(t(a,b)\). generate_sequences durchläuft alle primitiven ungeraden Vektoren, erzeugt daraus deduplizierte Folgen \((s^2,t,k_{\max})\) und behält nur Familien, die überhaupt einen Radius bis \(N\) liefern. build_occurrences expandiert jede Familie zu ihren \((R^2,\text{id})\)-Vorkommen. Nach dem Sortieren komprimiert der Code gleiche Radien zu Mitgliedermengen, sammelt alle Teilmengenhäufigkeiten, wendet Inklusion-Exklusion an und addiert schließlich die Diagonalpaare \((R,R)\).
Ist \(T\) die Gesamtzahl der Vorkommen \((R^2,\text{id})\), dann kostet das Sortieren
$$O(T\log T).$$
Das Gruppieren gleicher Radien ist linear in \(T\). In der Inklusion-Exklusion werden alle nichtleeren Teilmengen jeder Mitgliedermenge erzeugt. Da die Mitgliedschaft in der Praxis sehr klein bleibt (der Code begrenzt sie für \(N=100000\) auf \(8\)), bleibt dieser Teil beherrschbar. Der Speicherverbrauch ist \(O(T)\).
Lenticular hole, iki çemberin çevrelediği konveks bölgedir ve şu üç şartı sağlar: iki merkezin de kafes noktası olması, iki çemberin iki farklı kafes noktasında kesişmesi ve lens iç bölgesinde hiç kafes noktası bulunmaması. Lenticular pair ise böyle iki çemberin yarıçaplarıyla elde edilen sıralı \((r_1,r_2)\) çiftidir. İstenen,
$$0 < r_1 \le r_2 \le N$$
koşulunu sağlayan farklı çiftlerin sayısıdır.
İki kafes kesişim noktasına \(P,Q\) diyelim. Bir ötelemeden sonra
$$P=(0,0),\qquad Q=(a,b)$$
varsayabiliriz. Önemli olan yalnızca fark vektörüdür. Kod sadece
$$\gcd(a,b)=1$$
olan primitive vektörleri tutar. Eğer \(a\) ve \(b\) farklı parity'ye sahip olsaydı, kiriş orta noktası bir tam sayı ve bir yarım sayı koordinat taşırdı; bu durumda orta dikme iki kafes merkezden geçemezdi. Vektör primitive olduğu için aynı parity'li tek olasılık her ikisinin de tek olmasıdır. Bu yüzden arama primitive tek vektörler üzerinde yapılır.
Şunu tanımlayalım:
$$s^2 = a^2+b^2.$$
Kirişin orta noktası \((a/2,b/2)\), dik yönü ise \((-b,a)\)'dır. Bu nedenle \(P\) ve \(Q\)'dan geçen her çemberin merkezi
$$O_k=\left(\frac{a-kb}{2},\frac{b+ka}{2}\right)$$
biçimindedir. \(a\) ve \(b\) tek olduğundan \(O_k\)'nin kafes noktası olması tam olarak \(k\)'nin tek olmasına eşdeğerdir. Yani aynı kirişi paylaşan kafes-merkezli çemberler tek tamsayı \(k\) ile indekslenir.
Yarıçap, \(O_k\)'nin \(P\)'ye uzaklığıdır:
$$R_k^2=\left(\frac{a-kb}{2}\right)^2+\left(\frac{b+ka}{2}\right)^2 =\frac{(a^2+b^2)(1+k^2)}{4} =\frac{s^2(1+k^2)}{4}.$$
Bütün çözücünün temel taşı bu formüldür.
Sabit bir primitive tek \((a,b)\) için her tek \(k\) bir aday yarıçap verir. Kirişin iki farklı tarafında birer çember seçmek, parametrelerin \(-m\) ve \(n\) olduğu; \(m,n\)'nin pozitif tek olduğu anlamına gelir. Çünkü
$$R_k^2=\frac{s^2(1+k^2)}{4}$$
sadece \(|k|\)'ye bağlıdır; dolayısıyla her primitive vektör, gerçekleşebilen yarıçap karelerinden oluşan artan bir dizi tanımlar.
Problem metnindeki iki örnek doğrudan buradan çıkar:
\((a,b)=(1,1)\) ailesi. Burada \(s^2=2\) ve eşik \(t=1\)'dir. \(k=1,3,5,7,\ldots\) için
$$R^2=1,5,13,25,\ldots$$
elde edilir; dolayısıyla \((1,5)\) çifti \(k=1\) ve \(k=7\)'den gelir.
\((a,b)=(1,3)\) ailesi. Burada \(s^2=10\) ve \(t=3\)'tür. O zaman \(k=3,5,7,\ldots\) için
$$R^2=25,65,125,\ldots$$
çıkar; yani \((5,\sqrt{65})\) çifti \(k=3\) ve \(k=5\)'ten gelir.
Zor kısım, hangi tek parametrelerin gerçekten geçerli olduğunu belirlemektir. Lensin içi hiçbir kafes noktası içermemelidir. Sabit bir kiriş yönü \((a,b)\) için kirişe yakın kafes noktaları
$$-bx+ay=c,\qquad c\in\mathbb Z$$
paralel kafes doğruları üzerinde yatar. \(\gcd(a,b)=1\) olduğu için kirişe en yakın sıfır-dışı doğrular
$$-bx+ay=\pm 1$$
olur. Simetri nedeniyle yalnızca \(-bx+ay=1\) doğrusunu incelemek yeterlidir.
Şimdi
$$A=ax+by$$
tanımını yapalım. Kod, bu doğru üzerindeki bir kafes noktasının lens dışında kalma engelinin şu kuadratik ifade tarafından kontrol edildiğini gösterir:
$$M(A)=A-\frac{A^2+1}{s^2}.$$
En kötü engel, bu ifadenin en yakın paralel doğru üzerindeki tüm kafes noktaları arasında aldığı maksimum değerdir. Eğer
$$-bx+ay=1$$
denkleminin bir çözümü \((x_0,y_0)\) ise, diğer bütün çözümler \((a,b)\)'nin katları kadar kayar. Dolayısıyla \(A\) değeri aslında yalnızca \(s^2\) modunda önemlidir. Bu yüzden kod önce
$$A_0=ax_0+by_0$$
hesaplar, bunu en yakın temsilciye indirger:
$$r \in [0,s^2/2],$$
sonra da
$$M=r-\left\lfloor\frac{r^2+1}{s^2}\right\rfloor$$
ifadesini değerlendirir. Geçerli en küçük tek parametre, \(M\)'den küçük olmayan en küçük tek sayı ama en az \(1\) olacak biçimde seçilir:
$$t(a,b)=\max\!\Bigl(1,\ \text{odd-ceiling}(M)\Bigr).$$
Asıl geometrik sonuç şudur: \(-m\) ve \(n\) parametrelerinden oluşan lens ancak ve ancak
$$m\ge t(a,b),\qquad n\ge t(a,b)$$
olduğunda geçerlidir. Bu nedenle her primitive vektör tüm tek \(k\)'leri değil, yalnızca
$$k=t,\ t+2,\ t+4,\ldots$$
şeklindeki tek kuyruğu üretir; sonra global yarıçap sınırı bu kuyruğu keser.
Sabit bir \((s^2,t)\) ailesi için en büyük uygun tek parametre şu koşuldan gelir:
$$R_k \le N \quad\Longleftrightarrow\quad \frac{s^2(1+k^2)}{4}\le N^2.$$
Dolayısıyla
$$k_{\max}=\text{en büyük tek }k\text{, }k^2\le \frac{4N^2}{s^2}-1$$
olacak şekilde seçilir. Her gerçekleşen kayıt
$$\bigl(R^2,\text{dizi kimliği}\bigr)$$
olarak saklanır. Eşitlik kontrolleri tam sayı aritmetiğiyle ve hatasız yapılabilsin diye \(R\) yerine \(R^2\) kullanılır. Farklı primitive vektörler aynı yarıçap dizisini verebildiğinden, üretim \((s^2,t)\) çiftiyle tekilleştirilir.
Tüm kayıtlar \(R^2\)'ye göre sıralandıktan sonra her farklı yarıçap için küçük bir üyelik kümesi elde edilir:
$$I(R)=\{\text{bu }R\text{'yi üreten dizi kimlikleri}\}.$$
Bir \((r_1,r_2)\) çifti ancak ve ancak iki yarıçapın en az bir ortak aileden gelmesi halinde geçerlidir; yani
$$I(r_1)\cap I(r_2)\neq\varnothing.$$
Böylece problem artık geometrik olmaktan çıkar ve saf bir küme-kesişim sayımına dönüşür.
Boş olmayan sabit bir kimlik altkümesi \(J\) için
$$c_J=\#\{R:J\subseteq I(R)\}$$
olsun. O zaman \(\binom{c_J}{2}\), \(J\)'nin tüm kimliklerini ortak paylaşan farklı yarıçap çiftlerini sayar. Tüm boş olmayan \(J\)'ler üzerinde işaret değiştirerek toplarsak, kesişimi boş olmayan farklı yarıçap çiftlerinin tam sayısını elde ederiz:
$$\sum_{J\ne\varnothing}(-1)^{|J|+1}\binom{c_J}{2}.$$
Son olarak her gerçekleşen yarıçap kendiyle de \((R,R)\) çifti oluşturur; bu yüzden çözücü farklı yarıçap sayısını ayrıca ekler.
Uygulama şu değerlerle kendini doğrular:
$$L(10)=30,\qquad L(100)=3442.$$
Bunlar problem metnindeki resmî örnek sonuçlardır ve hem geometrik eşik mantığının hem de kümesel sayımın doğru olduğunu gösterir.
compute_threshold_for_vector yukarıdaki en yakın paralel doğru analizini kodlar ve \(t(a,b)\)'yi döndürür. generate_sequences tüm primitive tek vektörleri dolaşır, bunlardan tekrarsız \((s^2,t,k_{\max})\) aileleri üretir ve en az bir yarıçapı \(N\)'in altında kalanları tutar. build_occurrences her aileyi gerçekleşen \((R^2,\text{id})\) kayıtlarına açar. Sıralama sonrası kod eşit yarıçapları üyelik kümelerine sıkıştırır, tüm altküme frekanslarını toplar, inclusion-exclusion uygular ve en sonda \((R,R)\) çaprazlarını ekler.
Toplam \((R^2,\text{id})\) kayıt sayısı \(T\) ise sıralama maliyeti
$$O(T\log T)$$
olur. Eşit yarıçapları gruplayıp üyelik kümeleri oluşturmak \(T\) üzerinde lineerdir. Inclusion-exclusion aşaması her üyelik kümesinin boş olmayan altkümelerini gezer. Üyelik boyutu pratikte çok küçük kaldığı için (kod \(N=100000\) için bunu \(8\) ile sınırlar) bu bölüm yönetilebilir kalır. Bellek kullanımı \(O(T)\)'dir.
Un agujero lenticular es la región convexa encerrada por dos circunferencias tales que ambos centros son puntos de la red, las circunferencias se cortan en dos puntos de la red distintos y el interior de la lente no contiene puntos de la red. Un par lenticular es un par ordenado de radios \((r_1,r_2)\) para el que existen dos circunferencias así. Debemos contar los pares distintos con
$$0 < r_1 \le r_2 \le N.$$
Sean \(P,Q\) los dos puntos de intersección de la red. Tras una traslación podemos suponer
$$P=(0,0),\qquad Q=(a,b).$$
Solo importa el vector diferencia. El código conserva únicamente vectores primitivos con
$$\gcd(a,b)=1.$$
Si \(a\) y \(b\) tuvieran distinta paridad, el punto medio de \(PQ\) tendría una coordenada entera y otra semientera, y la mediatriz no podría pasar por dos centros de la red. Como además el vector es primitivo, el único caso de misma paridad es que ambos sean impares. Por eso la búsqueda recorre vectores primitivos impares.
Definimos
$$s^2 = a^2+b^2.$$
El punto medio de la cuerda es \((a/2,b/2)\) y la dirección perpendicular es \((-b,a)\). Por tanto, toda circunferencia que pasa por \(P\) y \(Q\) tiene centro
$$O_k=\left(\frac{a-kb}{2},\frac{b+ka}{2}\right)$$
para algún parámetro real \(k\). Como \(a\) y \(b\) son impares, \(O_k\) es punto de la red exactamente cuando \(k\) es impar. Así, las circunferencias con centro en la red que comparten la cuerda quedan indexadas por enteros impares \(k\).
El radio es la distancia de \(O_k\) a \(P\):
$$R_k^2=\left(\frac{a-kb}{2}\right)^2+\left(\frac{b+ka}{2}\right)^2 =\frac{(a^2+b^2)(1+k^2)}{4} =\frac{s^2(1+k^2)}{4}.$$
Ésta es la fórmula central del solucionador.
Fijado un \((a,b)\) primitivo e impar, cada \(k\) impar da un radio candidato. Elegir una circunferencia a cada lado de la cuerda equivale a tomar parámetros \(-m\) y \(n\), con \(m,n\) impares positivos. Como
$$R_k^2=\frac{s^2(1+k^2)}{4}$$
depende solo de \(|k|\), cada vector primitivo define una secuencia creciente de cuadrados de radio realizables.
Dos ejemplos del enunciado salen de inmediato:
Familia \((a,b)=(1,1)\). Aquí \(s^2=2\) y el umbral es \(t=1\). Con \(k=1,3,5,7,\ldots\) obtenemos
$$R^2=1,5,13,25,\ldots,$$
así que el par \((1,5)\) aparece con \(k=1\) y \(k=7\).
Familia \((a,b)=(1,3)\). Aquí \(s^2=10\) y \(t=3\). Entonces \(k=3,5,7,\ldots\) da
$$R^2=25,65,125,\ldots,$$
y por tanto \((5,\sqrt{65})\) viene de \(k=3\) y \(k=5\).
La parte sutil es decidir qué parámetros impares son realmente válidos. El interior de la lente no debe contener puntos de la red. Para una dirección de cuerda fija \((a,b)\), los puntos de la red cercanos a la cuerda viven en las rectas paralelas
$$-bx+ay=c,\qquad c\in\mathbb Z.$$
Como \(\gcd(a,b)=1\), las rectas paralelas no triviales más cercanas son
$$-bx+ay=\pm 1.$$
Basta analizar una de ellas, por ejemplo \(-bx+ay=1\), porque el otro lado es simétrico.
Definimos
$$A=ax+by.$$
El código muestra que la obstrucción a mantener un punto de esa recta fuera de la lente está gobernada por la expresión cuadrática
$$M(A)=A-\frac{A^2+1}{s^2}.$$
La peor obstrucción es el máximo de esta cantidad sobre todos los puntos de la red de la recta más próxima. Si \((x_0,y_0)\) es una solución de
$$-bx+ay=1,$$
todas las demás soluciones difieren en múltiplos de \((a,b)\). Por eso \(A\) solo importa módulo \(s^2\). El código calcula primero
$$A_0=ax_0+by_0,$$
lo reduce al representante más cercano
$$r \in [0,s^2/2],$$
y evalúa
$$M=r-\left\lfloor\frac{r^2+1}{s^2}\right\rfloor.$$
El menor parámetro impar válido es el menor impar no inferior a \(M\), pero al menos \(1\):
$$t(a,b)=\max\!\Bigl(1,\ \text{techo impar}(M)\Bigr).$$
El hecho geométrico clave es que una lente formada por los parámetros \(-m\) y \(n\) es válida exactamente cuando
$$m\ge t(a,b),\qquad n\ge t(a,b).$$
Así, cada vector primitivo no produce todos los \(k\) impares, sino solo la cola impar
$$k=t,\ t+2,\ t+4,\ldots$$
hasta que el límite global del radio la corta.
Para una familia fija \((s^2,t)\), el mayor parámetro impar permitido viene de
$$R_k \le N \quad\Longleftrightarrow\quad \frac{s^2(1+k^2)}{4}\le N^2.$$
Por tanto
$$k_{\max}=\text{el mayor impar }k\text{ con }k^2\le \frac{4N^2}{s^2}-1.$$
Cada aparición se guarda como
$$\bigl(R^2,\text{id de secuencia}\bigr).$$
Se usa \(R^2\) en vez de \(R\) para comprobar igualdades exactamente con enteros y evitar por completo el punto flotante. Vectores primitivos distintos pueden conducir a la misma secuencia de radios, así que la generación se deduplica por el par \((s^2,t)\).
Después de reunir y ordenar todas las apariciones por \(R^2\), a cada radio distinto se le asigna un pequeño conjunto de pertenencia
$$I(R)=\{\text{ids de secuencia que generan }R\}.$$
Un par \((r_1,r_2)\) es lenticular exactamente cuando ambos radios comparten al menos una familia común, es decir, cuando
$$I(r_1)\cap I(r_2)\neq\varnothing.$$
En ese punto el problema deja de ser geométrico y se convierte en uno puramente combinatorio de intersección de conjuntos.
Sea \(c_J\) el número de radios distintos cuyo conjunto de pertenencia contiene un subconjunto fijo no vacío \(J\):
$$c_J=\#\{R:J\subseteq I(R)\}.$$
Entonces \(\binom{c_J}{2}\) cuenta pares no ordenados de radios distintos que comparten todos los ids de \(J\). Al sumar sobre todos los \(J\) no vacíos con signos alternados obtenemos exactamente el número de pares no ordenados de radios distintos con intersección no vacía:
$$\sum_{J\ne\varnothing}(-1)^{|J|+1}\binom{c_J}{2}.$$
Finalmente, cada radio realizado también forma el par diagonal \((R,R)\), así que el solucionador añade el número de radios distintos.
La implementación se valida con
$$L(10)=30,\qquad L(100)=3442.$$
Estos son los valores oficiales de ejemplo del enunciado y confirman que tanto la lógica geométrica del umbral como la fase combinatoria son correctas.
compute_threshold_for_vector implementa el análisis de la recta paralela más cercana y devuelve \(t(a,b)\). generate_sequences recorre todos los vectores primitivos impares, los convierte en familias deduplicadas \((s^2,t,k_{\max})\) y conserva solo las que pueden producir algún radio menor o igual que \(N\). build_occurrences expande cada familia a sus apariciones \((R^2,\text{id})\). Tras ordenar, el código comprime radios iguales en conjuntos de pertenencia, acumula frecuencias de subconjuntos, aplica inclusión-exclusión y al final suma los pares diagonales \((R,R)\).
Si \(T\) es el número total de apariciones \((R^2,\text{id})\), ordenar cuesta
$$O(T\log T).$$
Agrupar radios iguales es lineal en \(T\). La fase de inclusión-exclusión itera sobre todos los subconjuntos no vacíos de cada conjunto de pertenencia. Como el tamaño de pertenencia es muy pequeño en la práctica, esa parte sigue siendo manejable. La memoria usada es \(O(T)\).
所谓 lenticular hole，是由两条圆弧围成的凸透镜区域，并且满足：两个圆心都是格点、两圆在两个不同格点相交、透镜内部没有格点。若存在这样一对圆，其半径为 \((r_1,r_2)\)，就称 \((r_1,r_2)\) 为 lenticular pair。我们要统计满足
$$0 < r_1 \le r_2 \le N$$
的不同半径对个数。
设两圆的格点交点为 \(P,Q\)。平移之后可以设
$$P=(0,0),\qquad Q=(a,b).$$
真正重要的是差向量。代码只保留满足
$$\gcd(a,b)=1$$
的 primitive 向量。如果 \(a,b\) 奇偶性不同，那么弦中点会出现一个整数坐标和一个半整数坐标，垂直平分线就不可能同时经过两个格点圆心。由于向量还要求 primitive，因此同奇偶的唯一可能就是二者都为奇数。这就是代码只枚举 primitive odd 向量的原因。
记
$$s^2 = a^2+b^2.$$
公共弦的中点是 \((a/2,b/2)\)，垂直方向是 \((-b,a)\)。因此经过 \(P,Q\) 的任意圆，其圆心都可写成
$$O_k=\left(\frac{a-kb}{2},\frac{b+ka}{2}\right)$$
其中 \(k\) 是一个实参数。由于 \(a,b\) 都是奇数，\(O_k\) 成为格点当且仅当 \(k\) 是奇整数。也就是说，共享同一条弦的所有格点圆心圆都由奇整数 \(k\) 编号。
半径就是 \(O_k\) 到 \(P\) 的距离：
$$R_k^2=\left(\frac{a-kb}{2}\right)^2+\left(\frac{b+ka}{2}\right)^2 =\frac{(a^2+b^2)(1+k^2)}{4} =\frac{s^2(1+k^2)}{4}.$$
这就是整个求解器的核心公式。
固定一个 primitive odd 向量 \((a,b)\)，每个奇整数 \(k\) 都对应一个候选半径。在公共弦两侧各选一个圆，等价于选择参数 \(-m\) 和 \(n\)，其中 \(m,n\) 是正奇数。由于
$$R_k^2=\frac{s^2(1+k^2)}{4}$$
只依赖于 \(|k|\)，所以每个 primitive 向量都会产生一个单调增长的可实现半径平方序列。
题目中的两个示例可以直接从这里得到：
族 \((a,b)=(1,1)\)。 此时 \(s^2=2\)，阈值 \(t=1\)。当 \(k=1,3,5,7,\ldots\) 时有
$$R^2=1,5,13,25,\ldots,$$
于是 \((1,5)\) 对应 \(k=1\) 与 \(k=7\)。
族 \((a,b)=(1,3)\)。 此时 \(s^2=10\)，阈值 \(t=3\)。当 \(k=3,5,7,\ldots\) 时有
$$R^2=25,65,125,\ldots,$$
于是 \((5,\sqrt{65})\) 对应 \(k=3\) 与 \(k=5\)。
真正困难的是判断哪些奇参数 \(k\) 才有效。透镜内部不能含有格点。对于固定的弦方向 \((a,b)\)，靠近弦的格点位于平行直线族
$$-bx+ay=c,\qquad c\in\mathbb Z$$
上。因为 \(\gcd(a,b)=1\)，离弦最近的非零平行格线就是
$$-bx+ay=\pm 1.$$
由于两侧对称，只需分析其中一条，例如 \(-bx+ay=1\)。
定义
$$A=ax+by.$$
代码表明：对这条最近平行线上的格点而言，是否会落入透镜内部，取决于二次表达式
$$M(A)=A-\frac{A^2+1}{s^2}.$$
最坏的障碍量，就是该表达式在最近平行线所有格点上的最大值。若 \((x_0,y_0)\) 是
$$-bx+ay=1$$
的一组解，那么其他所有解都只是在 \((a,b)\) 方向上平移若干倍，所以 \(A\) 实际上只在模 \(s^2\) 意义下有区别。这就是为什么代码先算
$$A_0=ax_0+by_0,$$
再把它化到最近代表元
$$r \in [0,s^2/2],$$
并计算
$$M=r-\left\lfloor\frac{r^2+1}{s^2}\right\rfloor.$$
最小有效奇阈值就是不小于 \(M\) 的最小奇数，同时至少为 \(1\)：
$$t(a,b)=\max\!\Bigl(1,\ \text{odd-ceiling}(M)\Bigr).$$
几何上的关键结论是：由参数 \(-m\) 与 \(n\) 形成的透镜恰好在下列条件下有效：
$$m\ge t(a,b),\qquad n\ge t(a,b).$$
因此每个 primitive 向量并不会产生全部奇 \(k\)，而只会产生奇尾巴
$$k=t,\ t+2,\ t+4,\ldots$$
直到全局半径上界把它截断为止。
对固定族 \((s^2,t)\)，最大允许奇参数由
$$R_k \le N \quad\Longleftrightarrow\quad \frac{s^2(1+k^2)}{4}\le N^2$$
决定，因此
$$k_{\max}=\text{满足 }k^2\le \frac{4N^2}{s^2}-1\text{ 的最大奇数 }k.$$
代码把每个实现都记录成
$$\bigl(R^2,\text{sequence id}\bigr).$$
之所以存 \(R^2\) 而不是 \(R\)，是为了用整数精确比较半径是否相等，完全避免浮点误差。不同的 primitive 向量可能对应同一条半径序列，因此代码还会用 \((s^2,t)\) 对序列进行去重。
收集并按 \(R^2\) 排序后，每个不同半径都会得到一个很小的成员集合
$$I(R)=\{\text{能够产生 }R\text{ 的序列 id}\}.$$
一个半径对 \((r_1,r_2)\) 是有效 lenticular pair，当且仅当它们至少来自一个共同的序列族，也就是
$$I(r_1)\cap I(r_2)\neq\varnothing.$$
到这里问题已经从几何问题变成了纯粹的集合交计数问题。
对任意固定的非空 id 子集 \(J\)，定义
$$c_J=\#\{R:J\subseteq I(R)\}.$$
那么 \(\binom{c_J}{2}\) 统计的是：共享 \(J\) 中全部 id 的不同半径无序对数。对所有非空 \(J\) 做交替符号求和，就得到成员集合交非空的不同半径对数：
$$\sum_{J\ne\varnothing}(-1)^{|J|+1}\binom{c_J}{2}.$$
最后，每个已经实现的半径还会形成对角对 \((R,R)\)，因此求解器再加上不同半径的个数。
程序用
$$L(10)=30,\qquad L(100)=3442$$
来验证自己。这正是题目给出的官方样例结果，说明几何阈值计算和后面的集合计数都一致正确。
compute_threshold_for_vector 实现最近平行格线分析并返回 \(t(a,b)\)。generate_sequences 枚举所有 primitive odd 向量，把它们变成去重后的 \((s^2,t,k_{\max})\) 序列族，并只保留能产生某个 \(R\le N\) 的族。build_occurrences 再把每个族展开成所有 \((R^2,\text{id})\) 记录。排序后，代码把相同半径压缩成成员集合，统计所有子集频次，应用容斥公式，最后再加上 \((R,R)\) 这样的对角对。
若总记录数为 \(T\)，排序代价为
$$O(T\log T).$$
合并相同半径在 \(T\) 上是线性的。容斥阶段需要遍历每个成员集合的所有非空子集；由于成员数在实践中非常小，所以这一步仍然可控。空间复杂度为 \(O(T)\)。
Линзовидной дырой называется выпуклая область, ограниченная двумя окружностями, если оба центра лежат в узлах решётки, окружности пересекаются в двух различных узлах решётки, а внутри линзы нет узлов решётки. Линзовая пара — это упорядоченная пара радиусов \((r_1,r_2)\), для которой существуют такие две окружности. Нужно посчитать число различных пар с
$$0 < r_1 \le r_2 \le N.$$
Пусть \(P,Q\) — два решёточных пункта пересечения. После переноса можно считать, что
$$P=(0,0),\qquad Q=(a,b).$$
Существенен только вектор разности. Код оставляет лишь примитивные векторы с
$$\gcd(a,b)=1.$$
Если бы \(a\) и \(b\) имели разную чётность, середина хорды имела бы одну целую и одну полуцелую координату, и серединный перпендикуляр не мог бы проходить через два решёточных центра. Так как вектор ещё и примитивен, единственный вариант одинаковой чётности — оба числа нечётны. Поэтому перебор идёт только по примитивным нечётным векторам.
Обозначим
$$s^2 = a^2+b^2.$$
Середина хорды равна \((a/2,b/2)\), а перпендикулярное направление — \((-b,a)\). Поэтому любая окружность через \(P\) и \(Q\) имеет центр вида
$$O_k=\left(\frac{a-kb}{2},\frac{b+ka}{2}\right)$$
для некоторого вещественного параметра \(k\). Так как \(a\) и \(b\) нечётны, центр \(O_k\) является узлом решётки тогда и только тогда, когда \(k\) нечётно. Значит, все такие окружности индексируются нечётными целыми \(k\).
Радиус — это расстояние от \(O_k\) до \(P\):
$$R_k^2=\left(\frac{a-kb}{2}\right)^2+\left(\frac{b+ka}{2}\right)^2 =\frac{(a^2+b^2)(1+k^2)}{4} =\frac{s^2(1+k^2)}{4}.$$
Это центральная формула всего решения.
Для фиксированного примитивного нечётного \((a,b)\) каждое нечётное \(k\) даёт кандидат на радиус. Выбор по одной окружности с каждой стороны хорды соответствует параметрам \(-m\) и \(n\), где \(m,n\) — положительные нечётные числа. Так как
$$R_k^2=\frac{s^2(1+k^2)}{4}$$
зависит только от \(|k|\), каждый примитивный вектор задаёт возрастающую последовательность реализуемых квадратов радиусов.
Два примера из условия возникают сразу:
Семейство \((a,b)=(1,1)\). Здесь \(s^2=2\), а порог \(t=1\). При \(k=1,3,5,7,\ldots\) получаем
$$R^2=1,5,13,25,\ldots,$$
поэтому пара \((1,5)\) появляется из \(k=1\) и \(k=7\).
Семейство \((a,b)=(1,3)\). Здесь \(s^2=10\), а \(t=3\). Тогда \(k=3,5,7,\ldots\) даёт
$$R^2=25,65,125,\ldots,$$
и потому \((5,\sqrt{65})\) получается из \(k=3\) и \(k=5\).
Самая тонкая часть — определить, какие нечётные параметры действительно допустимы. Внутри линзы не должно быть узлов решётки. Для фиксированного направления хорды \((a,b)\) ближайшие к хорде решёточные точки лежат на параллельных прямых
$$-bx+ay=c,\qquad c\in\mathbb Z.$$
Поскольку \(\gcd(a,b)=1\), ближайшие ненулевые параллели имеют вид
$$-bx+ay=\pm 1.$$
Из-за симметрии достаточно рассмотреть одну из них, скажем \(-bx+ay=1\).
Введём
$$A=ax+by.$$
Код показывает, что препятствие к тому, чтобы держать такую точку вне линзы, контролируется квадратичным выражением
$$M(A)=A-\frac{A^2+1}{s^2}.$$
Худшее препятствие — максимум этой величины по всем решёточным точкам на ближайшей параллели. Если \((x_0,y_0)\) — некоторое решение уравнения
$$-bx+ay=1,$$
то все остальные решения отличаются на кратные \((a,b)\). Поэтому \(A\) важно только по модулю \(s^2\). Именно поэтому код сначала вычисляет
$$A_0=ax_0+by_0,$$
сводит его к ближайшему представителю
$$r \in [0,s^2/2],$$
а затем рассматривает
$$M=r-\left\lfloor\frac{r^2+1}{s^2}\right\rfloor.$$
Минимальный допустимый нечётный параметр — это наименьшее нечётное число не меньше \(M\), но не меньше \(1\):
$$t(a,b)=\max\!\Bigl(1,\ \text{нечётный потолок}(M)\Bigr).$$
Ключевой геометрический факт: линза, образованная параметрами \(-m\) и \(n\), допустима тогда и только тогда, когда
$$m\ge t(a,b),\qquad n\ge t(a,b).$$
Следовательно, каждый примитивный вектор порождает не все нечётные \(k\), а только нечётный хвост
$$k=t,\ t+2,\ t+4,\ldots$$
до тех пор, пока глобальное ограничение по радиусу не остановит последовательность.
Для фиксированного семейства \((s^2,t)\) наибольший допустимый нечётный параметр задаётся условием
$$R_k \le N \quad\Longleftrightarrow\quad \frac{s^2(1+k^2)}{4}\le N^2.$$
Отсюда
$$k_{\max}=\text{наибольшее нечётное }k\text{, для которого }k^2\le \frac{4N^2}{s^2}-1.$$
Каждое реализованное вхождение хранится как
$$\bigl(R^2,\text{id последовательности}\bigr).$$
Используется именно \(R^2\), а не \(R\), чтобы сравнивать радиусы точно при помощи целых чисел и полностью избежать вещественных ошибок. Разные примитивные векторы могут задавать одну и ту же последовательность радиусов, поэтому генерация дедуплицируется по паре \((s^2,t)\).
После сбора и сортировки по \(R^2\) каждый различный радиус получает маленькое множество принадлежности
$$I(R)=\{\text{id последовательностей, реализующих }R\}.$$
Пара \((r_1,r_2)\) является линзовой тогда и только тогда, когда оба радиуса имеют хотя бы одно общее семейство, то есть
$$I(r_1)\cap I(r_2)\neq\varnothing.$$
С этого момента задача уже не геометрическая, а чисто комбинаторная: нужно считать пересечения множеств.
Для фиксированного непустого подмножества идентификаторов \(J\) обозначим через
$$c_J=\#\{R:J\subseteq I(R)\}$$
число различных радиусов, чьи множества принадлежности содержат \(J\). Тогда \(\binom{c_J}{2}\) считает неупорядоченные пары различных радиусов, которые разделяют все id из \(J\). Попеременная сумма по всем непустым \(J\) даёт точное число неупорядоченных пар различных радиусов с непустым пересечением:
$$\sum_{J\ne\varnothing}(-1)^{|J|+1}\binom{c_J}{2}.$$
Наконец, каждый реализованный радиус даёт ещё и диагональную пару \((R,R)\), поэтому в конце код добавляет число различных радиусов.
Реализация проверяет себя на значениях
$$L(10)=30,\qquad L(100)=3442.$$
Это официальные примеры из условия, подтверждающие корректность и геометрической части с порогом, и последующего комбинаторного счёта.
compute_threshold_for_vector реализует описанный анализ ближайших параллельных решёточных прямых и возвращает \(t(a,b)\). generate_sequences перебирает все примитивные нечётные векторы, превращает их в дедуплицированные семейства \((s^2,t,k_{\max})\) и сохраняет только те, что дают хотя бы один радиус не больше \(N\). build_occurrences разворачивает каждое семейство в его появления \((R^2,\text{id})\). После сортировки код сжимает одинаковые радиусы в множества принадлежности, накапливает частоты всех подмножеств, применяет включение-исключение и в конце добавляет диагональные пары \((R,R)\).
Если \(T\) — общее число появлений \((R^2,\text{id})\), то сортировка стоит
$$O(T\log T).$$
Группировка одинаковых радиусов линейна по \(T\). На этапе включения-исключения перечисляются все непустые подмножества каждого множества принадлежности. Поскольку размеры этих множеств на практике очень малы, этот этап остаётся выполнимым. Память равна \(O(T)\).
الـ lenticular hole هو المنطقة العدسية المحدبة المحصورة بين دائرتين بحيث يكون مركزا الدائرتين نقطتين شبكيتين، وتتقاطع الدائرتان في نقطتين شبكيتين مختلفتين، ولا يحتوي داخل العدسة على أي نقطة شبكية. ويُسمّى الزوج المرتب \((r_1,r_2)\) زوجًا عدسيًا إذا وُجدت دائرتان بهذين نصفَي القطر وتشكّلان عدسة من هذا النوع. المطلوب هو عدّ الأزواج المختلفة التي تحقق
$$0 < r_1 \le r_2 \le N.$$
لتكن \(P,Q\) نقطتي التقاطع الشبكيتين. بعد إزاحة مناسبة يمكننا أن نفترض
$$P=(0,0),\qquad Q=(a,b).$$
المهم هنا هو متجه الفرق فقط. يحتفظ الكود فقط بالمتجهات البدائية التي تحقق
$$\gcd(a,b)=1.$$
لو كان \(a\) و\(b\) مختلفي الفردية والزوجية، لكان منتصف الوتر ذا إحداثي صحيح وآخر نصف صحيح، وعندها لا يمكن أن يمر العمود المنصف بمركزين شبكيين. وبما أن المتجه بدائي أيضًا، فإن الحالة الوحيدة ذات الفردية نفسها هي أن يكون كلاهما فرديًا. لهذا السبب يمرّ البحث على المتجهات البدائية الفردية فقط.
نعرّف
$$s^2 = a^2+b^2.$$
منتصف الوتر هو \((a/2,b/2)\)، والاتجاه العمودي هو \((-b,a)\). لذلك فإن كل دائرة تمر بـ \(P\) و\(Q\) يكون مركزها من الشكل
$$O_k=\left(\frac{a-kb}{2},\frac{b+ka}{2}\right)$$
لبعض المعامل الحقيقي \(k\). وبما أن \(a\) و\(b\) فرديان، فإن \(O_k\) يكون نقطة شبكية بالضبط عندما يكون \(k\) عددًا فرديًا. وهكذا تُفهرس جميع هذه الدوائر بالأعداد الصحيحة الفردية \(k\).
أما نصف القطر فهو المسافة من \(O_k\) إلى \(P\):
$$R_k^2=\left(\frac{a-kb}{2}\right)^2+\left(\frac{b+ka}{2}\right)^2 =\frac{(a^2+b^2)(1+k^2)}{4} =\frac{s^2(1+k^2)}{4}.$$
وهذه هي الصيغة المركزية التي يعتمد عليها الحل كله.
للمتجه البدائي الفردي الثابت \((a,b)\)، تعطي كل قيمة فردية لـ \(k\) نصف قطر مرشحًا. واختيار دائرة على كل جانب من الوتر يقابل اختيار المعاملين \(-m\) و\(n\)، حيث \(m,n\) عددان فرديان موجبان. وبما أن
$$R_k^2=\frac{s^2(1+k^2)}{4}$$
يعتمد فقط على \(|k|\)، فإن كل متجه بدائي يحدد متتالية متزايدة من مربعات أنصاف الأقطار الممكنة.
وهكذا تظهر الأمثلة المذكورة في نص المسألة مباشرة:
العائلة \((a,b)=(1,1)\). هنا \(s^2=2\) والعتبة \(t=1\). عند \(k=1,3,5,7,\ldots\) نحصل على
$$R^2=1,5,13,25,\ldots,$$
ومن ثم يأتي الزوج \((1,5)\) من القيمتين \(k=1\) و\(k=7\).
العائلة \((a,b)=(1,3)\). هنا \(s^2=10\) و\(t=3\). عندئذ تعطي القيم \(k=3,5,7,\ldots\)
$$R^2=25,65,125,\ldots,$$
ومن ثم ينتج الزوج \((5,\sqrt{65})\) من \(k=3\) و\(k=5\).
الجزء الدقيق هو تحديد أي القيم الفردية لـ \(k\) تكون صالحة فعلًا. يجب ألا يحتوي داخل العدسة على أي نقطة شبكية. وللاتجاه الثابت للوتر \((a,b)\)، تقع النقاط الشبكية القريبة من الوتر على العائلة
$$-bx+ay=c,\qquad c\in\mathbb Z.$$
وبسبب \(\gcd(a,b)=1\)، فإن أقرب المستقيمات الموازية غير الصفرية هي
$$-bx+ay=\pm 1.$$
ويكفي تحليل أحد الجانبين، مثل \(-bx+ay=1\)، لأن الجانب الآخر متماثل.
لنعرّف الآن
$$A=ax+by.$$
يبين الكود أن العائق الذي يحدد ما إذا كانت نقطة شبكية على هذا المستقيم القريب ستقع داخل العدسة تحكمه العبارة التربيعية
$$M(A)=A-\frac{A^2+1}{s^2}.$$
وأشد عائق ممكن هو القيمة العظمى لهذه العبارة على جميع النقاط الشبكية الواقعة على أقرب مستقيم موازٍ. وإذا كانت \((x_0,y_0)\) حلًا للمعادلة
$$-bx+ay=1,$$
فإن جميع الحلول الأخرى تختلف عنها بمضاعفات المتجه \((a,b)\)، ولذلك فإن قيمة \(A\) لا يهم منها إلا باقيها modulo \(s^2\). ولهذا يحسب الكود أولًا
$$A_0=ax_0+by_0,$$
ثم يختزلها إلى أقرب ممثل
$$r \in [0,s^2/2],$$
ويقيّم بعد ذلك
$$M=r-\left\lfloor\frac{r^2+1}{s^2}\right\rfloor.$$
أصغر معامل فردي صالح هو أصغر عدد فردي لا يقل عن \(M\)، مع فرض ألا يقل عن \(1\):
$$t(a,b)=\max\!\Bigl(1,\ \text{السقف الفردي}(M)\Bigr).$$
والحقيقة الهندسية الأساسية هي أن العدسة المتولدة من المعاملين \(-m\) و\(n\) تكون صالحة إذا وفقط إذا تحقق
$$m\ge t(a,b),\qquad n\ge t(a,b).$$
إذًا لا يعطي كل متجه بدائي جميع القيم الفردية لـ \(k\)، بل فقط الذيل الفردي
$$k=t,\ t+2,\ t+4,\ldots$$
إلى أن يقطعه الحد العالمي لنصف القطر.
للعائلة الثابتة \((s^2,t)\)، يُحدد أكبر معامل فردي صالح من الشرط
$$R_k \le N \quad\Longleftrightarrow\quad \frac{s^2(1+k^2)}{4}\le N^2.$$
ومن ثم
$$k_{\max}=\text{أكبر }k\text{ فردي يحقق }k^2\le \frac{4N^2}{s^2}-1.$$
ويسجل الكود كل تحقق على صورة
$$\bigl(R^2,\text{معرّف المتتالية}\bigr).$$
يُستخدم \(R^2\) بدلًا من \(R\) حتى تتم مقارنة أنصاف الأقطار بدقة تامة بالأعداد الصحيحة ومن دون أي حسابات فاصلة عائمة. وقد تعطي متجهات بدائية مختلفة المتتالية نفسها، لذلك تُزال التكرارات بواسطة الزوج \((s^2,t)\).
بعد جمع جميع الحالات وفرزها حسب \(R^2\)، يحصل كل نصف قطر مميز على مجموعة انتماء صغيرة
$$I(R)=\{\text{معرّفات المتتاليات التي تولد }R\}.$$
ويكون الزوج \((r_1,r_2)\) عدسيًا إذا وفقط إذا كان نصفي القطر يشتركان في عائلة واحدة على الأقل، أي عندما
$$I(r_1)\cap I(r_2)\neq\varnothing.$$
وعند هذه المرحلة تتحول المسألة من مسألة هندسية إلى مسألة عدّ تقاطعات مجموعات.
لكل مجموعة فرعية غير فارغة ثابتة \(J\) من المعرّفات، نعرّف
$$c_J=\#\{R:J\subseteq I(R)\}.$$
عندئذ تحسب \(\binom{c_J}{2}\) الأزواج غير المرتبة من أنصاف الأقطار المختلفة التي تشترك في جميع عناصر \(J\). وبجمع هذه القيم على جميع \(J\) غير الفارغة مع الإشارات المتناوبة نحصل على العدد الدقيق للأزواج غير المرتبة من أنصاف الأقطار المختلفة التي يكون تقاطع مجموعات انتمائها غير فارغ:
$$\sum_{J\ne\varnothing}(-1)^{|J|+1}\binom{c_J}{2}.$$
ثم يضيف الحل في النهاية الأزواج القطرية \((R,R)\)، لأن كل نصف قطر محقق يمكن أن يقترن بنفسه.
يتحقق التنفيذ من نفسه بالقيمتين
$$L(10)=30,\qquad L(100)=3442.$$
وهما القيمتان المثاليتان الرسميتان في نص المسألة، وتؤكدان صحة كل من منطق العتبة الهندسي ومرحلة العدّ التجميعي.
تقوم الدالة compute_threshold_for_vector بتنفيذ تحليل المستقيمات الشبكية الموازية الأقرب وإرجاع \(t(a,b)\). ثم تمر generate_sequences على جميع المتجهات البدائية الفردية، وتحولها إلى عائلات منزوعة التكرار \((s^2,t,k_{\max})\)، وتحتفظ فقط بالعائلات التي تنتج نصف قطر واحدًا على الأقل لا يتجاوز \(N\). بعد ذلك توسع build_occurrences كل عائلة إلى جميع سجلاتها \((R^2,\text{id})\). وبعد الفرز يضغط الكود أنصاف الأقطار المتساوية في مجموعات انتماء، ويجمع تكرارات جميع المجموعات الفرعية، ويطبق مبدأ التضمين والاستبعاد، ثم يضيف في النهاية الأزواج \((R,R)\).
إذا كان \(T\) هو العدد الكلي للسجلات \((R^2,\text{id})\)، فإن الفرز يكلف
$$O(T\log T).$$
أما تجميع أنصاف الأقطار المتساوية فهو خطي في \(T\). وفي مرحلة التضمين والاستبعاد تُعد جميع المجموعات الفرعية غير الفارغة لكل مجموعة انتماء. ولأن حجم مجموعة الانتماء يبقى صغيرًا جدًا عمليًا، تبقى هذه المرحلة قابلة للتنفيذ. استهلاك الذاكرة هو \(O(T)\).