Write
$$r=AO=CO,\qquad s=BO=DO=\frac{BD}{2},\qquad 0<r\le s.$$
Then every biclinic quadrilateral lives on one fixed pair of concentric circles centered at \(O\): the vertices \(A,C\) lie on radius \(r\), while \(B,D\) are the opposite endpoints of a diameter of radius \(s\).
The key invariant is
$$AB^2+BC^2+CD^2+AD^2=4(r^2+s^2).$$
So if we define
$$n=r^2+s^2,$$
then the condition in the problem is simply \(n\le N/4\). The whole problem becomes: for each \(n\), how many biclinic quadrilaterals are produced by the representations of \(n\) as a sum of two squares?
1) Every side pair gives a strict representation of the same \(n\).
Look at vertex \(A\). Let
$$u=AB,\qquad v=AD,\qquad u<v.$$
Define
$$x=\frac{u+v}{2},\qquad y=\frac{v-u}{2},\qquad u=x-y,\quad v=x+y.$$
In triangle \(BAD\), the point \(O\) is the midpoint of \(BD\). Apollonius gives
$$u^2+v^2=2(AO^2+BO^2)=2(r^2+s^2)=2n.$$
But also
$$u^2+v^2=(x-y)^2+(x+y)^2=2(x^2+y^2).$$
Therefore
$$x^2+y^2=n.$$
Because \(u\) and \(v\) are distinct positive integers, we get a strict representation \(x>y>0\). The same argument at vertex \(C\) gives another strict representation of the same \(n\).
2) The reverse construction.
Suppose we already know one representation
$$n=s^2+r^2,\qquad s\ge r>0,$$
which will be used for the diagonal data \(BD=2s\) and \(AO=CO=r\). Now take another strict representation
$$n=x^2+y^2,\qquad x>y>0.$$
Set
$$u=x-y,\qquad v=x+y.$$
Then
$$u^2+v^2=2n=2(r^2+s^2),$$
so by Apollonius any point \(P\) with \(PB=u\) and \(PD=v\) automatically satisfies \(PO=r\). Thus the pair \((x,y)\) determines a valid vertex on the inner circle.
To make the circles intersect, we need the triangle inequalities with base \(BD=2s\):
$$v-u=2y<2s<2x=u+v.$$
This is exactly why the diagonal representation must be the smallest one in the ordering below.
3) Order the representations of \(n\).
Let
$$\mathcal R(n)=\{(x,y)\in\mathbb Z_{>0}^2:\ x>y,\ x^2+y^2=n\},\qquad m(n)=|\mathcal R(n)|.$$
Sort the pairs by increasing \(x\):
$$x_1<x_2<\cdots<x_{m(n)}.$$
Because \(x_i^2+y_i^2=n\), the corresponding \(y_i\) values strictly decrease:
$$y_1>y_2>\cdots>y_{m(n)}.$$
On the branch \(x>\sqrt{n/2}\), the two functions
$$x-y\quad\text{and}\quad x+y$$
behave monotonically in opposite directions:
$$x-y\ \text{increases},\qquad x+y\ \text{decreases}.$$
So if we choose three strict representations
$$ (x_i,y_i),\ (x_j,y_j),\ (x_k,y_k)\qquad (i<j<k),$$
then the smallest one \((x_i,y_i)\) is the only possible diagonal pair \((s,r)\), because it guarantees \(x_j>s\) and \(x_k>s\), while the reverse choice would violate the triangle inequality.
4) One 3-subset of representations gives one quadrilateral.
Take the diagonal data from the smallest representation:
$$s=x_i,\qquad r=y_i,\qquad BD=2x_i,\qquad AO=CO=y_i.$$
Use the next two representations for the two vertices:
$$AB=x_j-y_j,\qquad AD=x_j+y_j,$$
$$BC=x_k-y_k,\qquad CD=x_k+y_k.$$
The monotonicity above gives the strict side order automatically:
$$AB<BC<CD<AD.$$
Hence every 3-element subset of \(\mathcal R(n)\) contributes exactly one biclinic integral quadrilateral. This yields the generic term
$$\binom{m(n)}{3}.$$
5) The special case \(n=2t^2\).
If
$$n=2t^2,$$
then besides the strict representations there is also the symmetric one \((t,t)\). It is not counted in \(m(n)\) because it is not strict, but it is perfectly valid for the diagonal data:
$$s=t,\qquad r=t,\qquad AO=BO=CO=DO=t.$$
Once this diagonal pair is fixed, any two strict representations of \(n\) can play the roles of the two vertices, so this case contributes
$$\binom{m(n)}{2}.$$
6) Final counting formula.
Putting the generic and special cases together,
$$B(N)=\sum_{1\le n\le N/4}\left[\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2}\right].$$
Official sample. The example in the statement has
$$AO=CO=23,\qquad BO=DO=24,$$
so
$$n=23^2+24^2=1105.$$
The strict representations of \(1105\) are
$$1105=24^2+23^2=31^2+12^2=32^2+9^2=33^2+4^2.$$
Choose \((24,23)\) as the diagonal pair. Then using \((31,12)\) and \((33,4)\) for the two vertices gives
$$AB=31-12=19,\qquad AD=31+12=43,$$
$$BC=33-4=29,\qquad CD=33+4=37,$$
and
$$BD=2\cdot 24=48,\qquad AO=CO=23.$$
This is exactly the quadrilateral from the problem statement. Since \(m(1105)=4\), the value \(n=1105\) actually contributes \(\binom{4}{3}=4\) quadrilaterals in total.
Why the extra \(\binom{m(n)}{2}\) term exists. Consider
$$1250=25^2+25^2=31^2+17^2=35^2+5^2.$$
Here \(m(1250)=2\) because only the two strict representations are counted. The generic term is \(\binom{2}{3}=0\), but the symmetric pair \((25,25)\) can be used as the diagonal representation, so we get one extra quadrilateral:
$$\binom{2}{2}=1.$$
1) Work blockwise in \(n\). Let \(T=N/4\). The code processes intervals
$$[L,H]\subseteq [1,T]$$
of width \(W\). For one block it stores a local counter array `counts[n-L]`.
2) Enumerate all strict representations in the block.
For every \(y\ge 1\), the smallest possible strict value is
$$y^2+(y+1)^2.$$
If that already exceeds \(H\), we stop. Otherwise the feasible \(x\)-range is
$$x_{\min}=\max\!\left(y+1,\left\lceil \sqrt{L-y^2}\right\rceil\right),\qquad x_{\max}=\left\lfloor \sqrt{H-y^2}\right\rfloor.$$
Every pair \((x,y)\) with \(x_{\min}\le x\le x_{\max}\) contributes one strict representation to
$$n=x^2+y^2.$$
3) Convert representation counts into quadrilateral counts.
After the block is filled, every touched value \(n\) has \(m(n)\) stored in its counter. The code adds
$$\binom{m(n)}{3}$$
and, if \(n/2\) is a square, also
$$\binom{m(n)}{2}.$$
Then the touched counters are reset to zero and the next block is processed.
4) Why the implementation is fast.
It never factors every integer \(n\). It only enumerates lattice points \((x,y)\) that actually satisfy \(x^2+y^2\le T\). The `touched` list ensures that only entries hit in the current block are visited when the block is finalized.
Let \(T=N/4\). The memory usage is \(O(W)\) for block width \(W\). The running time is essentially proportional to the number of strict lattice representations
$$x^2+y^2\le T,\qquad x>y>0,$$
that are generated across all blocks. The code also parallelizes naturally because different blocks are independent.
The C++ implementation verifies
$$B(10\,000)=49,\qquad B(1\,000\,000)=38239,$$
and the default full run returns
$$B(10\,000\,000\,000)=2466018557.$$
Setze
$$r=AO=CO,\qquad s=BO=DO=\frac{BD}{2},\qquad 0<r\le s.$$
Dann liegen \(A\) und \(C\) auf dem inneren Kreis mit Radius \(r\), waehrend \(B\) und \(D\) die Endpunkte eines Durchmessers des aeusseren Kreises mit Radius \(s\) sind.
Die zentrale Invariante ist
$$AB^2+BC^2+CD^2+AD^2=4(r^2+s^2).$$
Mit
$$n=r^2+s^2$$
wird die Nebenbedingung des Problems zu \(n\le N/4\). Also muessen wir fuer jedes \(n\) nur noch zaehlen, wie viele passende Quadrilate aus den Darstellungen von \(n\) als Summe zweier Quadrate entstehen.
1) Jedes Seitenpaar liefert eine strenge Darstellung von \(n\).
Betrachte den Eckpunkt \(A\) und schreibe
$$u=AB,\qquad v=AD,\qquad u<v.$$
Definiere
$$x=\frac{u+v}{2},\qquad y=\frac{v-u}{2},\qquad u=x-y,\quad v=x+y.$$
Da \(O\) der Mittelpunkt von \(BD\) ist, liefert der Satz des Apollonius in \(\triangle BAD\)
$$u^2+v^2=2(AO^2+BO^2)=2(r^2+s^2)=2n.$$
Andererseits gilt
$$u^2+v^2=(x-y)^2+(x+y)^2=2(x^2+y^2).$$
Also folgt
$$x^2+y^2=n.$$
Wegen \(u\neq v\) und \(u,v>0\) ist dies eine strenge Darstellung \(x>y>0\). Dasselbe gilt fuer den Eckpunkt \(C\).
2) Rueckrichtung.
Sei zuerst eine Darstellung
$$n=s^2+r^2,\qquad s\ge r>0,$$
gegeben; sie bestimmt die Diagonaldaten \(BD=2s\) und \(AO=CO=r\). Nimm nun eine weitere strenge Darstellung
$$n=x^2+y^2,\qquad x>y>0,$$
und setze
$$u=x-y,\qquad v=x+y.$$
Dann ist
$$u^2+v^2=2n=2(r^2+s^2),$$
also erzwingt Apollonius \(PO=r\) fuer jeden Punkt \(P\) mit \(PB=u\) und \(PD=v\). Die Dreiecksungleichungen zur Basis \(BD=2s\) lauten
$$2y=v-u<2s<u+v=2x.$$
Genau deshalb muss die Diagonaldarstellung in der spaeteren Ordnung die kleinste sein.
3) Ordnung der Darstellungen.
Sei
$$\mathcal R(n)=\{(x,y)\in\mathbb Z_{>0}^2:\ x>y,\ x^2+y^2=n\},\qquad m(n)=|\mathcal R(n)|.$$
Wir sortieren nach wachsendem \(x\):
$$x_1<x_2<\cdots<x_{m(n)}.$$
Dann fallen die \(y_i\) streng ab. Auf dem Zweig \(x>\sqrt{n/2}\) steigt \(x-y\), waehrend \(x+y\) faellt. Deshalb ist bei drei Darstellungen
$$ (x_i,y_i),\ (x_j,y_j),\ (x_k,y_k)\qquad (i<j<k)$$
nur die kleinste als Diagonaldarstellung moeglich.
4) Jede 3-Teilmenge liefert genau ein Quadrilat.
Setze
$$s=x_i,\qquad r=y_i,\qquad BD=2x_i,\qquad AO=CO=y_i,$$
und verwende die anderen beiden Darstellungen fuer die Seiten:
$$AB=x_j-y_j,\qquad AD=x_j+y_j,$$
$$BC=x_k-y_k,\qquad CD=x_k+y_k.$$
Wegen der Monotonie gilt automatisch
$$AB<BC<CD<AD.$$
Somit traegt jede 3-elementige Teilmenge von \(\mathcal R(n)\) genau einmal bei:
$$\binom{m(n)}{3}.$$
5) Spezialfall \(n=2t^2\).
Dann existiert zusaetzlich die symmetrische Darstellung \((t,t)\). Sie ist nicht in \(m(n)\) enthalten, weil sie nicht streng ist, aber sie darf als Diagonaldarstellung verwendet werden:
$$s=t,\qquad r=t.$$
Jede Wahl von zwei strengen Darstellungen erzeugt dann ein weiteres Quadrilat, also den Zusatzterm
$$\binom{m(n)}{2}.$$
6) Endformel.
Damit erhaelt man
$$B(N)=\sum_{1\le n\le N/4}\left[\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2}\right].$$
Beispiel aus der Aufgabenstellung. Dort gilt
$$AO=CO=23,\qquad BO=DO=24,$$
also
$$n=23^2+24^2=1105.$$
Die strengen Darstellungen sind
$$1105=24^2+23^2=31^2+12^2=32^2+9^2=33^2+4^2.$$
Mit \((24,23)\) als Diagonaldarstellung und \((31,12)\), \((33,4)\) fuer die beiden Eckpunkte erhaelt man
$$AB=19,\quad BC=29,\quad CD=37,\quad AD=43,\quad BD=48.$$
Genau das ist das offizielle Beispiel. Da \(m(1105)=4\), liefert \(n=1105\) insgesamt \(\binom{4}{3}=4\) Quadrilate.
Warum der Zusatzterm gebraucht wird. Fuer
$$1250=25^2+25^2=31^2+17^2=35^2+5^2$$
ist \(m(1250)=2\). Der generische Beitrag \(\binom{2}{3}\) ist null, aber die symmetrische Diagonaldarstellung \((25,25)\) erzeugt noch
$$\binom{2}{2}=1$$
zusätzliches Quadrilat.
1) Blockweise ueber \(n\). Mit \(T=N/4\) bearbeitet der Code Intervalle \([L,H]\subseteq[1,T]\) mit Breite \(W\).
2) Alle strengen Darstellungen im Block enumerieren.
Fuer jedes \(y\ge 1\) ist der kleinste strenge Kandidat \(y^2+(y+1)^2\). Sobald dieser Wert groesser als \(H\) ist, kann man abbrechen. Sonst gilt
$$x_{\min}=\max\!\left(y+1,\left\lceil\sqrt{L-y^2}\right\rceil\right),\qquad x_{\max}=\left\lfloor\sqrt{H-y^2}\right\rfloor.$$
Jedes Paar \((x,y)\) erhoeht den Zaehler fuer \(n=x^2+y^2\).
3) Umrechnung in Quadrilatzahlen.
Nach Abschluss des Blocks wird fuer jedes beruehrte \(n\) addiert:
$$\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2}.$$
Danach werden nur die beruehrten Zaehler auf null gesetzt.
Der Speicherbedarf betraegt \(O(W)\). Die Laufzeit ist im Wesentlichen proportional zur Anzahl der erzeugten strengen Gitterdarstellungen \(x^2+y^2\le T\) mit \(x>y>0\). Da die Bloecke unabhaengig sind, laesst sich die Methode direkt parallelisieren.
Die Implementierung prueft
$$B(10\,000)=49,\qquad B(1\,000\,000)=38239,$$
und fuer die volle Aufgabe ergibt sich
$$B(10\,000\,000\,000)=2466018557.$$
Su sekilde yazalim:
$$r=AO=CO,\qquad s=BO=DO=\frac{BD}{2},\qquad 0<r\le s.$$
Bu durumda \(A\) ve \(C\) merkez \(O\) olan yaricapi \(r\) ic dairede, \(B\) ve \(D\) ise yaricapi \(s\) olan dis dairenin bir capinin iki ucunda durur.
Temel invariant su:
$$AB^2+BC^2+CD^2+AD^2=4(r^2+s^2).$$
Dolayisiyla
$$n=r^2+s^2$$
dersek problem kosulu sadece \(n\le N/4\) olur. Geriye kalan is: her \(n\) icin, \(n\)'in iki kare toplami temsillerinden kac biclinic quadrilateral ciktigini saymak.
1) Her komsu kenar cifti ayni \(n\) icin bir strict temsil verir.
\(A\) kosesine bakalim ve
$$u=AB,\qquad v=AD,\qquad u<v$$
yazalim. Sonra
$$x=\frac{u+v}{2},\qquad y=\frac{v-u}{2},\qquad u=x-y,\quad v=x+y$$
tanimini yapalim. \(\triangle BAD\) icinde \(O\), \(BD\)'nin orta noktasi oldugu icin Apollonius teoremi
$$u^2+v^2=2(AO^2+BO^2)=2(r^2+s^2)=2n$$
verir. Diger taraftan
$$u^2+v^2=(x-y)^2+(x+y)^2=2(x^2+y^2).$$
Demek ki
$$x^2+y^2=n.$$
\(u\neq v\) ve ikisi de pozitif oldugu icin burada \(x>y>0\) olur; yani strict bir iki-kare temsili elde ederiz. Ayni sey \(C\) kosesi icin de gecerli.
2) Tersi yon: temsilden kose kurmak.
Elimizde once
$$n=s^2+r^2,\qquad s\ge r>0$$
olsun; bu temsil diagonal verisini belirler:
$$BD=2s,\qquad AO=CO=r.$$
Simdi ayni \(n\) icin baska bir strict temsil alalim:
$$n=x^2+y^2,\qquad x>y>0.$$
Ve
$$u=x-y,\qquad v=x+y$$
yazalim. O zaman
$$u^2+v^2=2n=2(r^2+s^2)$$
olur. Dolayisiyla \(PB=u\), \(PD=v\) olan herhangi bir nokta icin Apollonius dogrudan \(PO=r\) sonucunu verir; yani bu cift ic daire uzerinde gecerli bir kose uretir.
Kesisim icin gereken ucgen esitsizlikleri
$$v-u=2y<2s<2x=u+v$$
seklindedir. Bu da diagonal temsilinin neden en kucuk temsil olmasi gerektigini aciklar.
3) Temsilleri sirala.
Su kumeyi tanimlayalim:
$$\mathcal R(n)=\{(x,y)\in\mathbb Z_{>0}^2:\ x>y,\ x^2+y^2=n\},\qquad m(n)=|\mathcal R(n)|.$$
Temsilleri artan \(x\)'e gore siralayalim:
$$x_1<x_2<\cdots<x_{m(n)}.$$
\(x_i^2+y_i^2=n\) oldugu icin \(y_i\) degerleri kesin bicimde azalir. Ayrica \(x>\sqrt{n/2}\) kolunda
$$x-y\ \text{artar},\qquad x+y\ \text{azalir}.$$
Bu cok kritik: uc temsil secildiginde en kucuk \(x\)'li olan tek mumkun diagonal temsilidir.
4) Her 3'lu altkume tam bir quadrilateral verir.
Uc strict temsil secelim:
$$ (x_i,y_i),\ (x_j,y_j),\ (x_k,y_k)\qquad (i<j<k).$$
En kucuk olanini diagonal icin kullan:
$$s=x_i,\qquad r=y_i,\qquad BD=2x_i,\qquad AO=CO=y_i.$$
Diger ikisi kose olur:
$$AB=x_j-y_j,\qquad AD=x_j+y_j,$$
$$BC=x_k-y_k,\qquad CD=x_k+y_k.$$
Monotonluk sayesinde otomatik olarak
$$AB<BC<CD<AD$$
elde edilir. Yani her 3 elemanli altkume tam bir gecerli quadrilateral uretir. Katki:
$$\binom{m(n)}{3}.$$
5) Ozel durum \(n=2t^2\).
Eger
$$n=2t^2$$
ise strict olmayan ama gecerli olan simetrik temsil \((t,t)\) da vardir. Bu temsil \(m(n)\)'ye dahil degildir cunku \(x>y\) saglanmaz, fakat diagonal icin tamamen gecerlidir:
$$s=t,\qquad r=t.$$
Bu durumda herhangi iki strict temsil kose olarak secilebilir; ek katkimiz
$$\binom{m(n)}{2}$$
olur.
6) Son formül.
Bunlari birlestirince
$$B(N)=\sum_{1\le n\le N/4}\left[\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2}\right]$$
sonucuna ulasiriz.
Resmi ornek. Problem metnindeki ornekte
$$AO=CO=23,\qquad BO=DO=24$$
oldugu icin
$$n=23^2+24^2=1105.$$
Strict temsiller:
$$1105=24^2+23^2=31^2+12^2=32^2+9^2=33^2+4^2.$$
\((24,23)\) diagonal cifti olsun. Sonra \((31,12)\) ve \((33,4)\) kullanilirsa
$$AB=31-12=19,\qquad AD=31+12=43,$$
$$BC=33-4=29,\qquad CD=33+4=37,$$
ve
$$BD=2\cdot 24=48,\qquad AO=CO=23$$
cikar. Bu tam olarak problemde verilen quadrilateral'dir. Burada \(m(1105)=4\) oldugu icin \(1105\) aslinda toplam \(\binom{4}{3}=4\) farkli quadrilateral uretir.
Neden ekstra \(\binom{m(n)}{2}\) terimi var? Ornegin
$$1250=25^2+25^2=31^2+17^2=35^2+5^2.$$
Burada \(m(1250)=2\) dir. Genel terim \(\binom{2}{3}=0\) verir, ama strict olmayan \((25,25)\) temsilini diagonal olarak kullanabildigimiz icin ek olarak
$$\binom{2}{2}=1$$
quadrilateral daha gelir.
1) \(n\) uzayini bloklara ayir. \(T=N/4\) olsun. Kod \([1,T]\) araligini genisligi \(W\) olan bloklara ayirir.
2) Bloktaki tum strict temsilleri enumerate et.
Sabit bir \(y\) icin en kucuk strict aday
$$y^2+(y+1)^2$$
olur. Bu deger \(H\)'yi astiysa daha buyuk \(y\)'lerde de is kalmaz. Aksi halde
$$x_{\min}=\max\!\left(y+1,\left\lceil\sqrt{L-y^2}\right\rceil\right),\qquad x_{\max}=\left\lfloor\sqrt{H-y^2}\right\rfloor$$
araligindaki her \(x\),
$$n=x^2+y^2$$
icin sayaci bir artirir.
3) Blok bitince kombinatorik formulu uygula.
Dokunulan her \(n\) icin sayaç \(m(n)\)'yi tutar. Kod su katkıyı ekler:
$$\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2}.$$
Sonra sadece o blokta dokunulan sayaçlar sifirlanir.
4) Neden hizli?
Her \(n\)'yi tek tek faktorlemiyor. Yalnizca gercekten var olan kafes noktalarini \((x,y)\) geziyor. `touched` listesi de blok sonunda butun dizi yerine sadece degisen girislerin temizlenmesini sagliyor.
Bellek maliyeti blok genisligi \(W\) icin \(O(W)\). Zaman maliyeti esas olarak
$$x^2+y^2\le T,\qquad x>y>0$$
kosulunu saglayan strict temsillerin toplam sayisina orantilidir. Bloklar birbirinden bagimsiz oldugu icin cok cekirdege dogrudan uygundur.
C++ kodu su kontrol degerlerini dogrular:
$$B(10\,000)=49,\qquad B(1\,000\,000)=38239.$$
Varsayilan tam kosuda elde edilen sonuc ise
$$B(10\,000\,000\,000)=2466018557$$
olur.
Escribimos
$$r=AO=CO,\qquad s=BO=DO=\frac{BD}{2},\qquad 0<r\le s.$$
Entonces \(A\) y \(C\) viven en el circulo interior de radio \(r\), mientras que \(B\) y \(D\) son los extremos opuestos de un diametro del circulo exterior de radio \(s\).
El invariante central es
$$AB^2+BC^2+CD^2+AD^2=4(r^2+s^2).$$
Si definimos
$$n=r^2+s^2,$$
la restriccion del problema queda reducida a \(n\le N/4\). Asi, para cada \(n\), solo hay que contar cuantos cuadrilateros salen de las representaciones de \(n\) como suma de dos cuadrados.
1) Cada par de lados vecinos produce una representacion estricta.
En el vertice \(A\), sea
$$u=AB,\qquad v=AD,\qquad u<v.$$
Definimos
$$x=\frac{u+v}{2},\qquad y=\frac{v-u}{2},\qquad u=x-y,\quad v=x+y.$$
Como \(O\) es el punto medio de \(BD\), el teorema de Apolonio en \(\triangle BAD\) da
$$u^2+v^2=2(AO^2+BO^2)=2(r^2+s^2)=2n.$$
Pero tambien
$$u^2+v^2=(x-y)^2+(x+y)^2=2(x^2+y^2),$$
por lo que
$$x^2+y^2=n.$$
Como \(u\neq v\) y ambos son positivos, obtenemos una representacion estricta \(x>y>0\). Lo mismo ocurre en el vertice \(C\).
2) Construccion inversa.
Supongamos primero que conocemos
$$n=s^2+r^2,\qquad s\ge r>0,$$
que fija los datos diagonales \(BD=2s\) y \(AO=CO=r\). Tomemos otra representacion estricta
$$n=x^2+y^2,\qquad x>y>0,$$
y pongamos
$$u=x-y,\qquad v=x+y.$$
Entonces
$$u^2+v^2=2n=2(r^2+s^2),$$
de modo que cualquier punto \(P\) con \(PB=u\) y \(PD=v\) satisface automaticamente \(PO=r\). Para que exista la interseccion con base \(BD=2s\), necesitamos
$$2y=v-u<2s<u+v=2x.$$
Por eso la representacion diagonal debe ser la menor de la terna elegida.
3) Ordenar las representaciones.
Sea
$$\mathcal R(n)=\{(x,y)\in\mathbb Z_{>0}^2:\ x>y,\ x^2+y^2=n\},\qquad m(n)=|\mathcal R(n)|.$$
Ordenamos por \(x\) creciente:
$$x_1<x_2<\cdots<x_{m(n)}.$$
Entonces los \(y_i\) decrecen estrictamente. En la rama \(x>\sqrt{n/2}\), la cantidad \(x-y\) aumenta y \(x+y\) disminuye. Por eso, de tres representaciones
$$ (x_i,y_i),\ (x_j,y_j),\ (x_k,y_k)\qquad (i<j<k),$$
solo la mas pequena puede servir como representacion diagonal.
4) Cada subconjunto de 3 elementos produce exactamente un cuadrilatero.
Tomamos
$$s=x_i,\qquad r=y_i,\qquad BD=2x_i,\qquad AO=CO=y_i,$$
y usamos las otras dos representaciones para los vertices:
$$AB=x_j-y_j,\qquad AD=x_j+y_j,$$
$$BC=x_k-y_k,\qquad CD=x_k+y_k.$$
La monotonia garantiza
$$AB<BC<CD<AD.$$
Asi, cada 3-subconjunto de \(\mathcal R(n)\) aporta
$$\binom{m(n)}{3}.$$
5) Caso especial \(n=2t^2\).
Si
$$n=2t^2,$$
aparece la representacion simetrica \((t,t)\). No entra en \(m(n)\) porque no es estricta, pero si puede usarse como diagonal. Entonces cualquier par de representaciones estrictas genera un cuadrilatero adicional, y el aporte extra es
$$\binom{m(n)}{2}.$$
6) Formula final.
Con todo ello,
$$B(N)=\sum_{1\le n\le N/4}\left[\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2}\right].$$
Ejemplo oficial. En el ejemplo del enunciado,
$$AO=CO=23,\qquad BO=DO=24,$$
asi que
$$n=23^2+24^2=1105.$$
Sus representaciones estrictas son
$$1105=24^2+23^2=31^2+12^2=32^2+9^2=33^2+4^2.$$
Si usamos \((24,23)\) como diagonal y \((31,12)\), \((33,4)\) como vertices, obtenemos
$$AB=19,\quad BC=29,\quad CD=37,\quad AD=43,\quad BD=48,$$
exactamente como en el problema. Como \(m(1105)=4\), ese valor de \(n\) produce en total \(\binom{4}{3}=4\) cuadrilateros.
Termino extra. Para
$$1250=25^2+25^2=31^2+17^2=35^2+5^2$$
tenemos \(m(1250)=2\). El termino generico \(\binom{2}{3}\) vale cero, pero la diagonal simetrica \((25,25)\) anade
$$\binom{2}{2}=1$$
cuadrilatero mas.
1) Procesar \(n\) por bloques. Con \(T=N/4\), el codigo recorre bloques \([L,H]\subseteq[1,T]\) de ancho \(W\).
2) Enumerar todas las representaciones estrictas del bloque.
Para un \(y\) fijo, el menor candidato estricto es
$$y^2+(y+1)^2.$$
Si ya supera \(H\), no quedan mas valores de \(y\). En caso contrario:
$$x_{\min}=\max\!\left(y+1,\left\lceil\sqrt{L-y^2}\right\rceil\right),\qquad x_{\max}=\left\lfloor\sqrt{H-y^2}\right\rfloor.$$
Cada \(x\) de ese intervalo incrementa el contador de
$$n=x^2+y^2.$$
3) Convertir contadores en cuadrilateros.
Al cerrar el bloque, para cada \(n\) tocado se suma
$$\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2},$$
y luego solo esos contadores se reinician.
La memoria es \(O(W)\). El tiempo es esencialmente proporcional al numero total de representaciones estrictas
$$x^2+y^2\le T,\qquad x>y>0$$
que aparecen en todos los bloques. Los bloques son independientes, asi que la paralelizacion es natural.
La implementacion verifica
$$B(10\,000)=49,\qquad B(1\,000\,000)=38239,$$
y la ejecucion completa devuelve
$$B(10\,000\,000\,000)=2466018557.$$
记
$$r=AO=CO,\qquad s=BO=DO=\frac{BD}{2},\qquad 0<r\le s.$$
于是 \(A,C\) 在以 \(O\) 为圆心、半径 \(r\) 的内圆上，\(B,D\) 则是半径 \(s\) 的外圆上一条直径的两个端点。
最重要的不变量是
$$AB^2+BC^2+CD^2+AD^2=4(r^2+s^2).$$
设
$$n=r^2+s^2,$$
那么题目的限制就变成 \(n\le N/4\)。整个问题因此化为：对每个 \(n\)，由 \(n\) 的“两平方和表示”能构造出多少个 biclinic 四边形？
1) 每一对相邻边都会给出同一个 \(n\) 的一个严格表示。
看顶点 \(A\)，设
$$u=AB,\qquad v=AD,\qquad u<v.$$
再定义
$$x=\frac{u+v}{2},\qquad y=\frac{v-u}{2},\qquad u=x-y,\quad v=x+y.$$
因为 \(O\) 是 \(BD\) 的中点，阿波罗尼奥斯定理在 \(\triangle BAD\) 中给出
$$u^2+v^2=2(AO^2+BO^2)=2(r^2+s^2)=2n.$$
另一方面，
$$u^2+v^2=(x-y)^2+(x+y)^2=2(x^2+y^2).$$
所以
$$x^2+y^2=n.$$
由于 \(u,v\) 是两个不同的正整数，因此得到的是严格表示 \(x>y>0\)。顶点 \(C\) 也会产生同样的严格表示。
2) 反向构造。
先取一个表示
$$n=s^2+r^2,\qquad s\ge r>0,$$
它决定了对角线数据
$$BD=2s,\qquad AO=CO=r.$$
再取同一个 \(n\) 的另一个严格表示
$$n=x^2+y^2,\qquad x>y>0,$$
并令
$$u=x-y,\qquad v=x+y.$$
于是
$$u^2+v^2=2n=2(r^2+s^2).$$
因此只要某点 \(P\) 满足 \(PB=u,PD=v\)，阿波罗尼奥斯定理就会自动推出 \(PO=r\)。要使两圆相交，还需要底边 \(BD=2s\) 的三角形不等式：
$$2y=v-u<2s<u+v=2x.$$
这正说明了为什么对角线对应的表示必须是所选表示中“最小”的那一个。
3) 对表示排序。
定义
$$\mathcal R(n)=\{(x,y)\in\mathbb Z_{>0}^2:\ x>y,\ x^2+y^2=n\},\qquad m(n)=|\mathcal R(n)|.$$
按 \(x\) 递增排序：
$$x_1<x_2<\cdots<x_{m(n)}.$$
由于 \(x_i^2+y_i^2=n\)，所以 \(y_i\) 严格递减。在分支 \(x>\sqrt{n/2}\) 上，
$$x-y\ \text{递增},\qquad x+y\ \text{递减}.$$
因此若取三个严格表示
$$ (x_i,y_i),\ (x_j,y_j),\ (x_k,y_k)\qquad (i<j<k),$$
则只有最小的那一个能作为对角线表示。
4) 每个 3 元子集恰好对应一个四边形。
令
$$s=x_i,\qquad r=y_i,\qquad BD=2x_i,\qquad AO=CO=y_i,$$
再用另外两个表示生成两组边：
$$AB=x_j-y_j,\qquad AD=x_j+y_j,$$
$$BC=x_k-y_k,\qquad CD=x_k+y_k.$$
由上面的单调性可自动得到
$$AB<BC<CD<AD.$$
所以 \(\mathcal R(n)\) 的每个三元子集都贡献一个四边形，贡献量为
$$\binom{m(n)}{3}.$$
5) 特殊情形 \(n=2t^2\).
当
$$n=2t^2$$
时，还会出现对称表示 \((t,t)\)。它不计入 \(m(n)\)，因为不是严格表示，但它完全可以作为对角线表示使用：
$$s=t,\qquad r=t.$$
此时任意两个严格表示都能作为两个顶点，因此还要额外加上
$$\binom{m(n)}{2}.$$
6) 总公式。
最终得到
$$B(N)=\sum_{1\le n\le N/4}\left[\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2}\right].$$
题目中的官方例子。 题目给出
$$AO=CO=23,\qquad BO=DO=24,$$
因此
$$n=23^2+24^2=1105.$$
\(1105\) 的严格表示为
$$1105=24^2+23^2=31^2+12^2=32^2+9^2=33^2+4^2.$$
取 \((24,23)\) 作为对角线表示，再取 \((31,12)\) 与 \((33,4)\) 作为两个顶点，就得到
$$AB=19,\quad BC=29,\quad CD=37,\quad AD=43,\quad BD=48,$$
这正是题面样例。由于 \(m(1105)=4\)，所以 \(n=1105\) 实际上一共贡献 \(\binom{4}{3}=4\) 个四边形。
为什么会有额外的 \(\binom{m(n)}{2}\) 项。 例如
$$1250=25^2+25^2=31^2+17^2=35^2+5^2.$$
这里 \(m(1250)=2\)。普通项 \(\binom{2}{3}=0\)，但对称表示 \((25,25)\) 可以拿来做对角线，因此还要额外贡献
$$\binom{2}{2}=1.$$
1) 按 \(n\) 分块处理。 记 \(T=N/4\)。代码把 \([1,T]\) 划分成宽度为 \(W\) 的区间块 \([L,H]\)。
2) 枚举块内全部严格表示。
对固定的 \(y\ge 1\)，最小的严格候选值是
$$y^2+(y+1)^2.$$
若它已经大于 \(H\)，就可以停止。否则可行区间为
$$x_{\min}=\max\!\left(y+1,\left\lceil\sqrt{L-y^2}\right\rceil\right),\qquad x_{\max}=\left\lfloor\sqrt{H-y^2}\right\rfloor.$$
区间中的每个 \(x\) 都给对应的
$$n=x^2+y^2$$
计数加一。
3) 把表示计数转换成四边形计数。
块处理结束后，对每个被访问到的 \(n\)，累计
$$\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2},$$
然后把这些被访问过的计数器清零。
内存为 \(O(W)\)。时间基本与所有满足
$$x^2+y^2\le T,\qquad x>y>0$$
的严格格点表示总数成正比。不同块彼此独立，因此很容易并行化。
C++ 实现验证了
$$B(10\,000)=49,\qquad B(1\,000\,000)=38239,$$
完整运行得到
$$B(10\,000\,000\,000)=2466018557.$$
Обозначим
$$r=AO=CO,\qquad s=BO=DO=\frac{BD}{2},\qquad 0<r\le s.$$
Тогда точки \(A\) и \(C\) лежат на внутренней окружности радиуса \(r\), а \(B\) и \(D\) являются концами диаметра внешней окружности радиуса \(s\).
Главный инвариант таков:
$$AB^2+BC^2+CD^2+AD^2=4(r^2+s^2).$$
Положим
$$n=r^2+s^2.$$
Тогда условие задачи становится просто \(n\le N/4\). Значит, нужно для каждого \(n\) посчитать, сколько biclinic-четырехугольников возникает из представлений \(n\) в виде суммы двух квадратов.
1) Каждая пара соседних сторон задает строгое представление одного и того же \(n\).
Рассмотрим вершину \(A\) и обозначим
$$u=AB,\qquad v=AD,\qquad u<v.$$
Пусть
$$x=\frac{u+v}{2},\qquad y=\frac{v-u}{2},\qquad u=x-y,\quad v=x+y.$$
Так как \(O\) есть середина \(BD\), теорема Аполлония в \(\triangle BAD\) дает
$$u^2+v^2=2(AO^2+BO^2)=2(r^2+s^2)=2n.$$
Но также
$$u^2+v^2=(x-y)^2+(x+y)^2=2(x^2+y^2).$$
Следовательно,
$$x^2+y^2=n.$$
Поскольку \(u\neq v\) и \(u,v>0\), мы получаем строгое представление \(x>y>0\). Точно так же возникает представление и в вершине \(C\).
2) Обратное построение.
Пусть сначала известно
$$n=s^2+r^2,\qquad s\ge r>0,$$
что задает диагональные данные
$$BD=2s,\qquad AO=CO=r.$$
Возьмем другое строгое представление того же \(n\):
$$n=x^2+y^2,\qquad x>y>0,$$
и положим
$$u=x-y,\qquad v=x+y.$$
Тогда
$$u^2+v^2=2n=2(r^2+s^2),$$
поэтому любой пункт \(P\) с \(PB=u\) и \(PD=v\) автоматически удовлетворяет \(PO=r\). Чтобы такая точка существовала при основании \(BD=2s\), нужны неравенства треугольника:
$$2y=v-u<2s<u+v=2x.$$
Именно поэтому диагональное представление должно быть наименьшим в выбранной тройке.
3) Упорядочим представления.
Определим
$$\mathcal R(n)=\{(x,y)\in\mathbb Z_{>0}^2:\ x>y,\ x^2+y^2=n\},\qquad m(n)=|\mathcal R(n)|.$$
Упорядочим по возрастанию \(x\):
$$x_1<x_2<\cdots<x_{m(n)}.$$
Тогда \(y_i\) строго убывают. На ветви \(x>\sqrt{n/2}\) величина \(x-y\) растет, а \(x+y\) убывает. Поэтому среди трех представлений
$$ (x_i,y_i),\ (x_j,y_j),\ (x_k,y_k)\qquad (i<j<k)$$
только наименьшее может играть роль диагонального.
4) Каждый 3-элементный набор дает ровно один четырехугольник.
Берем
$$s=x_i,\qquad r=y_i,\qquad BD=2x_i,\qquad AO=CO=y_i,$$
а две другие пары задают стороны:
$$AB=x_j-y_j,\qquad AD=x_j+y_j,$$
$$BC=x_k-y_k,\qquad CD=x_k+y_k.$$
Из монотонности сразу следует
$$AB<BC<CD<AD.$$
Значит, каждый 3-элементный поднабор \(\mathcal R(n)\) вносит
$$\binom{m(n)}{3}.$$
5) Специальный случай \(n=2t^2\).
Если
$$n=2t^2,$$
то существует еще симметричное представление \((t,t)\). Оно не входит в \(m(n)\), потому что не строгое, но подходит для диагонали. Тогда любая пара строгих представлений дает дополнительный вклад
$$\binom{m(n)}{2}.$$
6) Итоговая формула.
Получаем
$$B(N)=\sum_{1\le n\le N/4}\left[\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2}\right].$$
Официальный пример. В условии дано
$$AO=CO=23,\qquad BO=DO=24,$$
значит
$$n=23^2+24^2=1105.$$
Строгие представления числа \(1105\):
$$1105=24^2+23^2=31^2+12^2=32^2+9^2=33^2+4^2.$$
Если взять \((24,23)\) для диагонали, а \((31,12)\) и \((33,4)\) для двух вершин, получим
$$AB=19,\quad BC=29,\quad CD=37,\quad AD=43,\quad BD=48,$$
то есть ровно пример из условия. Поскольку \(m(1105)=4\), значение \(n=1105\) на самом деле дает \(\binom{4}{3}=4\) четырехугольника.
Откуда берется добавочный член. Для
$$1250=25^2+25^2=31^2+17^2=35^2+5^2$$
имеем \(m(1250)=2\). Обычный вклад \(\binom{2}{3}=0\), но симметричная диагональ \((25,25)\) добавляет еще
$$\binom{2}{2}=1$$
четырехугольник.
1) Блочная обработка по \(n\). Пусть \(T=N/4\). Код проходит блоки \([L,H]\subseteq[1,T]\) ширины \(W\).
2) Перебор всех строгих представлений в блоке.
Для фиксированного \(y\) минимальный строгий кандидат равен
$$y^2+(y+1)^2.$$
Если он уже больше \(H\), можно остановиться. Иначе
$$x_{\min}=\max\!\left(y+1,\left\lceil\sqrt{L-y^2}\right\rceil\right),\qquad x_{\max}=\left\lfloor\sqrt{H-y^2}\right\rfloor.$$
Каждая пара \((x,y)\) увеличивает счетчик для
$$n=x^2+y^2.$$
3) Преобразование счетчиков в число четырехугольников.
После завершения блока для каждого затронутого \(n\) добавляется
$$\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2},$$
после чего затронутые счетчики обнуляются.
Память равна \(O(W)\). Время в основном пропорционально числу строгих решеточных представлений
$$x^2+y^2\le T,\qquad x>y>0,$$
сгенерированных во всех блоках. Блоки независимы, поэтому параллелизация естественна.
Реализация проверяет
$$B(10\,000)=49,\qquad B(1\,000\,000)=38239,$$
а полный запуск дает
$$B(10\,000\,000\,000)=2466018557.$$
لنكتب
$$r=AO=CO,\qquad s=BO=DO=\frac{BD}{2},\qquad 0<r\le s.$$
عندئذ تقع النقطتان \(A\) و\(C\) على دائرة داخلية نصف قطرها \(r\) ومركزها \(O\)، بينما تقع \(B\) و\(D\) على دائرة خارجية نصف قطرها \(s\) وهما طرفا قطر واحد.
الثابت الأساسي هو
$$AB^2+BC^2+CD^2+AD^2=4(r^2+s^2).$$
إذا عرفنا
$$n=r^2+s^2,$$
فإن شرط المسألة يصبح فقط \(n\le N/4\). وهكذا تتحول المسألة إلى: لكل \(n\)، كم رباعيًا biclinic ينتج من تمثيلات \(n\) كمجموع مربعين؟
1) كل زوج من ضلعين متجاورين يعطي تمثيلًا صارمًا لنفس \(n\).
انظر إلى الرأس \(A\)، ولتكن
$$u=AB,\qquad v=AD,\qquad u<v.$$
ثم نعرف
$$x=\frac{u+v}{2},\qquad y=\frac{v-u}{2},\qquad u=x-y,\quad v=x+y.$$
بما أن \(O\) هو منتصف \(BD\)، فإن مبرهنة أبولونيوس في المثلث \(\triangle BAD\) تعطي
$$u^2+v^2=2(AO^2+BO^2)=2(r^2+s^2)=2n.$$
ومن جهة أخرى
$$u^2+v^2=(x-y)^2+(x+y)^2=2(x^2+y^2).$$
إذن
$$x^2+y^2=n.$$
ولأن \(u\neq v\) وكلاهما موجب، نحصل على تمثيل صارم \(x>y>0\). وينطبق البرهان نفسه على الرأس \(C\).
2) البناء العكسي.
افترض أولًا أننا نعرف تمثيلًا
$$n=s^2+r^2,\qquad s\ge r>0,$$
وهو الذي يحدد بيانات القطر:
$$BD=2s,\qquad AO=CO=r.$$
ثم خذ تمثيلًا صارمًا آخر لنفس \(n\):
$$n=x^2+y^2,\qquad x>y>0,$$
واكتب
$$u=x-y,\qquad v=x+y.$$
حينها
$$u^2+v^2=2n=2(r^2+s^2).$$
وبالتالي فإن أي نقطة \(P\) تحقق \(PB=u\) و\(PD=v\) ستعطي تلقائيًا \(PO=r\). ولكي توجد هذه النقطة مع قاعدة طولها \(BD=2s\)، لا بد من متباينات المثلث:
$$2y=v-u<2s<u+v=2x.$$
ولهذا السبب بالضبط يجب أن يكون تمثيل القطر هو الأصغر بين التمثيلات المختارة.
3) ترتيب التمثيلات.
نعرف
$$\mathcal R(n)=\{(x,y)\in\mathbb Z_{>0}^2:\ x>y,\ x^2+y^2=n\},\qquad m(n)=|\mathcal R(n)|.$$
ونرتبها بحسب \(x\) تصاعديًا:
$$x_1<x_2<\cdots<x_{m(n)}.$$
عندئذ تتناقص قيم \(y_i\) تناقصًا صارمًا. وعلى الفرع \(x>\sqrt{n/2}\) نجد أن
$$x-y\ \text{يزداد},\qquad x+y\ \text{يتناقص}.$$
لذلك إذا أخذنا ثلاثة تمثيلات صارمة
$$ (x_i,y_i),\ (x_j,y_j),\ (x_k,y_k)\qquad (i<j<k),$$
فإن أصغرها فقط يصلح لتمثيل القطر.
4) كل مجموعة من ثلاثة تمثيلات تعطي رباعيًا واحدًا بالضبط.
نضع
$$s=x_i,\qquad r=y_i,\qquad BD=2x_i,\qquad AO=CO=y_i,$$
ثم نستعمل التمثيلين الآخرين للرأسين:
$$AB=x_j-y_j,\qquad AD=x_j+y_j,$$
$$BC=x_k-y_k,\qquad CD=x_k+y_k.$$
وبفعل الرتابة السابقة نحصل تلقائيًا على
$$AB<BC<CD<AD.$$
إذن كل مجموعة ثلاثية من \(\mathcal R(n)\) تسهم بمقدار
$$\binom{m(n)}{3}.$$
5) الحالة الخاصة \(n=2t^2\).
إذا كان
$$n=2t^2,$$
فيوجد أيضًا التمثيل المتناظر \((t,t)\). هذا التمثيل غير محسوب داخل \(m(n)\) لأنه غير صارم، لكنه صالح تمامًا كتمثيل قطري. وعند تثبيته، فإن أي زوج من التمثيلات الصارمة يولد رباعيًا إضافيًا، أي الحد
$$\binom{m(n)}{2}.$$
6) الصيغة النهائية.
وبالتالي
$$B(N)=\sum_{1\le n\le N/4}\left[\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2}\right].$$
مثال نص المسألة. في المثال الرسمي لدينا
$$AO=CO=23,\qquad BO=DO=24,$$
ومن ثم
$$n=23^2+24^2=1105.$$
والتمثيلات الصارمة هي
$$1105=24^2+23^2=31^2+12^2=32^2+9^2=33^2+4^2.$$
إذا استعملنا \((24,23)\) لتمثيل القطر، ثم استعملنا \((31,12)\) و\((33,4)\) للرأسين، نحصل على
$$AB=19,\quad BC=29,\quad CD=37,\quad AD=43,\quad BD=48,$$
وهو بالضبط المثال المذكور في المسألة. وبما أن \(m(1105)=4\)، فإن القيمة \(1105\) تسهم فعليًا بمقدار \(\binom{4}{3}=4\) رباعيات.
سبب الحد الإضافي. خذ مثلًا
$$1250=25^2+25^2=31^2+17^2=35^2+5^2.$$
هنا \(m(1250)=2\). الحد العام \(\binom{2}{3}=0\)، لكن التمثيل المتناظر \((25,25)\) يمكن استخدامه كتمثيل قطري، ولذلك يظهر الحد الإضافي
$$\binom{2}{2}=1.$$
1) معالجة \(n\) على شكل كتل. لنكتب \(T=N/4\). الكود يعالج فترات \([L,H]\subseteq[1,T]\) بعرض \(W\).
2) تعداد كل التمثيلات الصارمة داخل الكتلة.
عند تثبيت \(y\ge 1\)، أصغر مرشح صارم هو
$$y^2+(y+1)^2.$$
فإذا تجاوز هذا العدد \(H\) نتوقف. وإلا فإن المجال الممكن لـ \(x\) هو
$$x_{\min}=\max\!\left(y+1,\left\lceil\sqrt{L-y^2}\right\rceil\right),\qquad x_{\max}=\left\lfloor\sqrt{H-y^2}\right\rfloor.$$
وكل \(x\) في هذا المجال يزيد العداد الموافق لـ
$$n=x^2+y^2.$$
3) تحويل عدادات التمثيلات إلى عدد رباعيات.
بعد انتهاء الكتلة يضيف الكود، لكل \(n\) تم الوصول إليه، المقدار
$$\binom{m(n)}{3}+\mathbf 1_{\,n=2t^2}\binom{m(n)}{2},$$
ثم يعيد فقط العدادات التي استُخدمت إلى الصفر.
الذاكرة تساوي \(O(W)\). والزمن يتناسب أساسًا مع عدد التمثيلات الشبكية الصارمة
$$x^2+y^2\le T,\qquad x>y>0$$
التي يتم توليدها عبر جميع الكتل. وبما أن الكتل مستقلة، فالموازاة مباشرة.
ينجح التنفيذ في التحقق من
$$B(10\,000)=49,\qquad B(1\,000\,000)=38239,$$
ويعطي في التشغيل الكامل
$$B(10\,000\,000\,000)=2466018557.$$