Problem 747 asks for a cumulative counting function \(\Psi(n)\) attached to the triangular-pizza configurations, and the required output is \(\Psi(10^8)\bmod (10^9+7)\). The C++, Python, and Java implementations do not enumerate configurations directly. Instead, they use an exact decomposition into a closed-form cubic base term and a correction term indexed by integer pairs \((x,y)\).
The implementations evaluate an exact prefix formula
$$\Psi(n)=B(n)+C(n),\qquad B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
The polynomial \(B(n)\) is the easy family already simplified algebraically. The interesting part is the correction term \(C(n)\), which recovers the remaining configurations by a structured scan over integer parameters.
For every \(n\), the implementations begin with
$$B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
This is a cubic polynomial, so it can be evaluated in constant time. The rest of the work is to add the nontrivial part that depends on three positive integers constrained by a quadratic boundary.
The correction term is organized by choosing
$$1\le x\le y,\qquad 4xy\le n.$$
For each such pair, the third integer \(z\) can never exceed
$$z_{\max}=n-1-x-y.$$
So only values \(z\le z_{\max}\) are relevant. The restriction \(x\le y\) removes one symmetry in advance; a separate multiplicity factor restores that symmetry later.
The boundary test used by the implementations is equivalent to
$$z^2\ge 4(x+y+z+1)xy.$$
Move the mixed term to the left and complete the square:
$$z^2-4xyz\ge 4xy(x+y+1),$$
$$\left(z-2xy\right)^2\ge 4xy(x+1)(y+1).$$
Therefore the smallest admissible integer \(z\) is
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil.$$
If \(z_{\min}>z_{\max}\), then the pair \((x,y)\) contributes nothing.
If the interval \([z_{\min},z_{\max}]\) is nonempty, a first count gives
$$2\left(z_{\max}-z_{\min}+1\right),$$
because each admissible \(z\) normally corresponds to two symmetric configurations. There is one exceptional boundary case: when
$$z_{\min}^2=4(x+y+z_{\min}+1)xy,$$
the lower endpoint lies exactly on the symmetry boundary, so the doubled count overcounts by \(1\). Define
$$\varepsilon(x,y)=\begin{cases} 1,&z_{\min}^2=4(x+y+z_{\min}+1)xy,\\ 0,&\text{otherwise.} \end{cases}$$
Then the exact local count is
$$c(x,y)=2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y).$$
Two outer multiplicities remain. First, when \(x\ne y\), swapping \(x\) and \(y\) creates a distinct configuration, while the diagonal case \(x=y\) should be counted only once. So define
$$\mu(x,y)=\begin{cases} 1,&x=y,\\ 2,&x\ne y. \end{cases}$$
Second, the formula applies an additional factor \(3\), reflecting the three equivalent placements treated symmetrically in the triangular setting. Hence
$$C(n)=3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\,c(x,y).$$
Combining the cubic base term with the corrected pair sum gives
$$\Psi(n)=\frac{(n+18)(n-1)(n-2)}{6}+3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\left(2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y)\right),$$
where
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil,\qquad z_{\max}=n-1-x-y.$$
This is exactly the quantity computed by the implementations before the final reduction modulo \(10^9+7\).
The base term is
$$B(10)=\frac{(10+18)(10-1)(10-2)}{6}=336.$$
The pair scan only needs pairs with \(4xy\le 10\). The pair \((x,y)=(1,1)\) gives
$$z_{\min}=2+\left\lceil\sqrt{16}\right\rceil=6,\qquad z_{\max}=10-1-1-1=7.$$
So the preliminary doubled count is
$$2(7-6+1)=4.$$
Because
$$6^2=4(1+1+6+1)\cdot 1\cdot 1=36,$$
the boundary correction subtracts \(1\), leaving \(c(1,1)=3\). Since \(x=y\), the symmetry factor is \(\mu(1,1)=1\), so the contribution is
$$3\cdot 1\cdot 3=9.$$
The next candidate pair \((1,2)\) already fails because
$$z_{\min}=4+\left\lceil\sqrt{48}\right\rceil=11>z_{\max}=6.$$
Therefore
$$\Psi(10)=336+9=345,$$
which matches the exact checkpoint used by the implementation.
The C++ implementation evaluates the prefix sum exactly in 128-bit integer arithmetic, using corrected integer square roots so that the floor and ceiling values are mathematically exact. It loops over \(x\) while \(4x^2\le n\), then over \(y\ge x\) while \(4xy\le n\), computes the admissible \(z\)-interval, applies the one-point boundary correction when equality occurs, and accumulates the weighted contribution.
The Java implementation uses the same pair enumeration and the same exact integer-square-root logic, but it carries the arithmetic modulo \(10^9+7\) throughout so that the cubic base term never overflows. The Python implementation is a thin wrapper around the same C++ algorithm: it compiles the C++ program when necessary, executes it, and returns the parsed answer.
The outer loop satisfies \(x\le \sqrt{n/4}\). For a fixed \(x\), the inner loop runs for
$$y=x,x+1,\dots,\left\lfloor\frac{n}{4x}\right\rfloor.$$
Hence the number of visited pairs is
$$\sum_{x\le \sqrt{n/4}}\left(\left\lfloor\frac{n}{4x}\right\rfloor-x+1\right)=O(n\log n).$$
Each pair is processed in constant time, so the total running time is \(O(n\log n)\) with \(O(1)\) auxiliary memory. In practice the hyperbolic constraint \(4xy\le n\) makes the scan far smaller than a full quadratic search.
Problem 747 verlangt eine kumulative Zählfunktion \(\Psi(n)\), die zu den Konfigurationen der dreieckigen Pizza gehört; gesucht ist \(\Psi(10^8)\bmod (10^9+7)\). Die C++-, Python- und Java-Implementierungen erzeugen die Konfigurationen nicht direkt. Stattdessen verwenden sie eine exakte Zerlegung in einen geschlossenen kubischen Basisterm und einen Korrekturterm, der über ganzzahlige Paare \((x,y)\) summiert wird.
Die Implementierungen werten die exakte Präfixformel
$$\Psi(n)=B(n)+C(n),\qquad B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
aus. Das Polynom \(B(n)\) beschreibt die einfache Familie bereits in geschlossener Form. Der eigentliche Aufwand steckt im Korrekturterm \(C(n)\), der die übrigen Konfigurationen durch eine strukturierte Suche über ganzzahlige Parameter ergänzt.
Für jedes \(n\) startet die Berechnung mit
$$B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
Das ist ein kubisches Polynom und daher in konstanter Zeit auswertbar. Danach muss nur noch der nichttriviale Teil addiert werden, der von drei positiven ganzen Zahlen unter einer quadratischen Randbedingung abhängt.
Der Korrekturterm wird über
$$1\le x\le y,\qquad 4xy\le n$$
organisiert. Für ein festes Paar kann die dritte Zahl \(z\) niemals größer sein als
$$z_{\max}=n-1-x-y.$$
Damit sind nur Werte \(z\le z_{\max}\) relevant. Die Bedingung \(x\le y\) entfernt eine Symmetrie bereits im Voraus; eine zusätzliche Vielfachheit stellt sie später wieder her.
Der in den Implementierungen verwendete Randtest ist äquivalent zu
$$z^2\ge 4(x+y+z+1)xy.$$
Bringt man den gemischten Term nach links und vervollständigt das Quadrat, erhält man
$$z^2-4xyz\ge 4xy(x+y+1),$$
$$\left(z-2xy\right)^2\ge 4xy(x+1)(y+1).$$
Also ist die kleinste zulässige ganze Zahl \(z\)
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil.$$
Gilt \(z_{\min}>z_{\max}\), dann trägt das Paar \((x,y)\) nichts bei.
Ist das Intervall \([z_{\min},z_{\max}]\) nicht leer, liefert ein erster Ansatz
$$2\left(z_{\max}-z_{\min}+1\right),$$
weil jedes zulässige \(z\) normalerweise zwei symmetrischen Konfigurationen entspricht. Es gibt jedoch genau einen Randfall: Wenn
$$z_{\min}^2=4(x+y+z_{\min}+1)xy,$$
dann liegt der linke Randpunkt exakt auf der Symmetriegrenze, und die Verdopplung zählt einen Fall zu viel. Definiere daher
$$\varepsilon(x,y)=\begin{cases} 1,&z_{\min}^2=4(x+y+z_{\min}+1)xy,\\ 0,&\text{otherwise.} \end{cases}$$
Dann ist die exakte lokale Anzahl
$$c(x,y)=2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y).$$
Zwei äußere Vielfachheiten bleiben übrig. Erstens erzeugt bei \(x\ne y\) das Vertauschen von \(x\) und \(y\) eine andere Konfiguration, während der Diagonalfall \(x=y\) nur einmal gezählt werden darf. Daher setzen wir
$$\mu(x,y)=\begin{cases} 1,&x=y,\\ 2,&x\ne y. \end{cases}$$
Zweitens verwendet die Formel noch einen Faktor \(3\), der die drei gleichwertigen Platzierungen im dreieckigen Aufbau widerspiegelt. Somit gilt
$$C(n)=3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\,c(x,y).$$
Durch Kombination des kubischen Basisterms mit der korrigierten Paarsumme erhält man
$$\Psi(n)=\frac{(n+18)(n-1)(n-2)}{6}+3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\left(2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y)\right),$$
wobei
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil,\qquad z_{\max}=n-1-x-y.$$
Genau diese Größe berechnen die Implementierungen vor der abschließenden Reduktion modulo \(10^9+7\).
Der Basisterm ist
$$B(10)=\frac{(10+18)(10-1)(10-2)}{6}=336.$$
Die Paarsuche benötigt nur Werte mit \(4xy\le 10\). Für \((x,y)=(1,1)\) erhält man
$$z_{\min}=2+\left\lceil\sqrt{16}\right\rceil=6,\qquad z_{\max}=10-1-1-1=7.$$
Die vorläufige verdoppelte Anzahl ist also
$$2(7-6+1)=4.$$
Da
$$6^2=4(1+1+6+1)\cdot 1\cdot 1=36,$$
wird am Rand \(1\) abgezogen, also \(c(1,1)=3\). Weil \(x=y\), ist \(\mu(1,1)=1\), und der Beitrag lautet
$$3\cdot 1\cdot 3=9.$$
Das nächste Kandidatenpaar \((1,2)\) scheitert bereits, denn
$$z_{\min}=4+\left\lceil\sqrt{48}\right\rceil=11>z_{\max}=6.$$
Damit folgt
$$\Psi(10)=336+9=345,$$
genau der exakte Kontrollwert aus der Implementierung.
Die C++-Implementierung wertet die Präfixsumme in exakter 128-Bit-Arithmetik aus und verwendet korrigierte ganzzahlige Quadratwurzeln, damit Floor- und Ceiling-Werte mathematisch exakt sind. Sie iteriert über \(x\) mit \(4x^2\le n\), dann über \(y\ge x\) mit \(4xy\le n\), bestimmt das zulässige \(z\)-Intervall, wendet bei Gleichheit die Einpunkt-Randkorrektur an und akkumuliert den gewichteten Beitrag.
Die Java-Implementierung benutzt dieselbe Paaraufzählung und dieselbe exakte Quadratwurzel-Logik, führt aber die Arithmetik durchgehend modulo \(10^9+7\), damit der kubische Basisterm nicht überläuft. Die Python-Implementierung ist ein schlanker Wrapper um denselben C++-Algorithmus: Sie kompiliert das C++-Programm bei Bedarf, führt es aus und gibt die geparste numerische Antwort zurück.
Die äußere Schleife erfüllt \(x\le \sqrt{n/4}\). Für ein festes \(x\) läuft die innere Schleife über
$$y=x,x+1,\dots,\left\lfloor\frac{n}{4x}\right\rfloor.$$
Daher ist die Anzahl besuchter Paare
$$\sum_{x\le \sqrt{n/4}}\left(\left\lfloor\frac{n}{4x}\right\rfloor-x+1\right)=O(n\log n).$$
Jedes Paar wird in konstanter Zeit verarbeitet. Insgesamt ergibt das eine Laufzeit von \(O(n\log n)\) bei \(O(1)\) Zusatzspeicher. In der Praxis ist die Suche wegen der hyperbolischen Bedingung \(4xy\le n\) deutlich kleiner als ein vollständiger quadratischer Scan.
Problem 747, üçgensel pizza düzenlerine ait kümülatif bir sayım fonksiyonu olan \(\Psi(n)\)'yi ister; hedef çıktı \(\Psi(10^8)\bmod (10^9+7)\) değeridir. C++, Python ve Java implementasyonları konfigürasyonları tek tek üretmez. Bunun yerine hesabı, kapalı biçimli kübik bir temel terim ile \((x,y)\) çiftleri üzerinden dolaşan bir düzeltme terimine ayırırlar.
Implementasyonların hesapladığı kesin önek formülü şudur:
$$\Psi(n)=B(n)+C(n),\qquad B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
\(B(n)\) polinomu kolay aileyi kapalı formda verir. Asıl iş, kalan konfigürasyonları tam sayı parametreleri üzerinden ekleyen \(C(n)\) düzeltme terimindedir.
Her \(n\) için hesap şu değerle başlar:
$$B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
Bu ifade kübik bir polinomdur; dolayısıyla sabit zamanda hesaplanabilir. Sonra, karesel bir sınır koşuluna bağlı üç pozitif tam sayıdan gelen zor kısım eklenir.
Düzeltme toplamı
$$1\le x\le y,\qquad 4xy\le n$$
koşulunu sağlayan çiftler üzerinden kurulur. Böyle bir çift için üçüncü tam sayı \(z\) en fazla
$$z_{\max}=n-1-x-y$$
olabilir. Yani yalnızca \(z\le z_{\max}\) değerleri önemlidir. \(x\le y\) koşulu bir simetriyi baştan kaldırır; eksik kalan simetri daha sonra ayrı bir çarpanla geri eklenir.
Implementasyonların kullandığı sınır testi şu eşitsizliğe denktir:
$$z^2\ge 4(x+y+z+1)xy.$$
Karışık terimi sola taşıyıp kare tamamlarsak
$$z^2-4xyz\ge 4xy(x+y+1),$$
$$\left(z-2xy\right)^2\ge 4xy(x+1)(y+1)$$
elde edilir. Buna göre uygun en küçük tam sayı \(z\)
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil$$
olur. Eğer \(z_{\min}>z_{\max}\) ise \((x,y)\) çifti hiç katkı yapmaz.
\([z_{\min},z_{\max}]\) aralığı boş değilse ilk sayım
$$2\left(z_{\max}-z_{\min}+1\right)$$
olur; çünkü normal durumda her uygun \(z\), iki simetrik konfigürasyona karşılık gelir. Ancak tek bir sınır durumu vardır: eğer
$$z_{\min}^2=4(x+y+z_{\min}+1)xy$$
ise sol uç tam simetri sınırında durur ve ikiyle çarpılmış sayım \(1\) fazla saymış olur. Bu yüzden
$$\varepsilon(x,y)=\begin{cases} 1,&z_{\min}^2=4(x+y+z_{\min}+1)xy,\\ 0,&\text{otherwise.} \end{cases}$$
tanımıyla tam yerel sayı
$$c(x,y)=2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y)$$
şeklinde yazılır.
Dış tarafta iki çarpan daha vardır. İlk olarak, \(x\ne y\) iken \(x\) ile \(y\)'nin yer değiştirmesi farklı bir konfigürasyon üretir; buna karşılık köşegen durumu \(x=y\) yalnızca bir kez sayılmalıdır. Bu nedenle
$$\mu(x,y)=\begin{cases} 1,&x=y,\\ 2,&x\ne y \end{cases}$$
alınır. İkinci olarak formülde ek bir \(3\) katsayısı vardır; bu, üçgensel yapıda simetrik kabul edilen üç eşdeğer yerleşimi temsil eder. Dolayısıyla
$$C(n)=3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\,c(x,y).$$
Kübik temel terim ile düzeltilmiş çift toplamını birleştirince
$$\Psi(n)=\frac{(n+18)(n-1)(n-2)}{6}+3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\left(2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y)\right),$$
burada
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil,\qquad z_{\max}=n-1-x-y.$$
İşte implementasyonların son mod alma işleminden önce hesapladığı nicelik tam olarak budur.
Temel terim
$$B(10)=\frac{(10+18)(10-1)(10-2)}{6}=336$$
olur. Çift taramasında yalnızca \(4xy\le 10\) sağlayan değerler gerekir. \((x,y)=(1,1)\) için
$$z_{\min}=2+\left\lceil\sqrt{16}\right\rceil=6,\qquad z_{\max}=10-1-1-1=7$$
elde edilir. Önceki iki katlı sayım
$$2(7-6+1)=4$$
olur. Ama
$$6^2=4(1+1+6+1)\cdot 1\cdot 1=36$$
eşitliği sağlandığı için sınır düzeltmesi \(1\) çıkarır ve \(c(1,1)=3\) kalır. \(x=y\) olduğundan \(\mu(1,1)=1\), katkı ise
$$3\cdot 1\cdot 3=9$$
olur. Bir sonraki aday çift \((1,2)\) ise
$$z_{\min}=4+\left\lceil\sqrt{48}\right\rceil=11>z_{\max}=6$$
olduğu için katkı vermez. Böylece
$$\Psi(10)=336+9=345$$
sonucu çıkar; bu da implementasyondaki kesin kontrol değeriyle aynıdır.
C++ implementasyonu önek toplamı 128 bit tam sayı aritmetiğiyle tam olarak hesaplar ve taban ile tavan kareköklerini matematiksel olarak doğru yapmak için düzeltilmiş tam sayı karekökleri kullanır. \(4x^2\le n\) olduğu sürece \(x\) üzerinde, sonra \(4xy\le n\) olduğu sürece \(y\ge x\) üzerinde dolaşır; uygun \(z\) aralığını bulur, eşitlik oluştuğunda tek noktalık sınır düzeltmesini uygular ve ağırlıklı katkıyı toplar.
Java implementasyonu aynı çift taramasını ve aynı tam sayı karekök mantığını kullanır; ancak kübik temel terimde taşma olmaması için aritmetiği baştan sona \(10^9+7\) modunda yürütür. Python implementasyonu ise aynı C++ algoritmasının ince bir sarmalayıcısıdır: gerekirse C++ programını derler, çalıştırır ve çıkan sayısal sonucu ayrıştırıp döndürür.
Dış döngü \(x\le \sqrt{n/4}\) koşulunu sağlar. Sabit bir \(x\) için iç döngü
$$y=x,x+1,\dots,\left\lfloor\frac{n}{4x}\right\rfloor$$
aralığında çalışır. Bu nedenle ziyaret edilen çift sayısı
$$\sum_{x\le \sqrt{n/4}}\left(\left\lfloor\frac{n}{4x}\right\rfloor-x+1\right)=O(n\log n)$$
olur. Her çift sabit zamanda işlendiğinden toplam süre \(O(n\log n)\), ek bellek ise \(O(1)\)'dir. Pratikte \(4xy\le n\) hiperbolik kısıtı, taramayı tam bir karesel aramadan çok daha küçük tutar.
El problema 747 pide una función acumulada \(\Psi(n)\) asociada a las configuraciones de la pizza triangular, y el valor final buscado es \(\Psi(10^8)\bmod (10^9+7)\). Las implementaciones en C++, Python y Java no enumeran las configuraciones directamente. En su lugar, usan una descomposición exacta en un término base cúbico de forma cerrada y un término de corrección indexado por pares enteros \((x,y)\).
Las implementaciones evalúan la fórmula prefijo exacta
$$\Psi(n)=B(n)+C(n),\qquad B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
El polinomio \(B(n)\) describe la familia sencilla ya simplificada algebraicamente. La parte interesante es \(C(n)\), que recupera las configuraciones restantes mediante un recorrido estructurado sobre parámetros enteros.
Para cada \(n\), el cálculo comienza con
$$B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
Es un polinomio cúbico, así que se evalúa en tiempo constante. Después solo queda añadir la parte no trivial, que depende de tres enteros positivos sujetos a una frontera cuadrática.
El término de corrección se organiza con
$$1\le x\le y,\qquad 4xy\le n.$$
Para cada par de este tipo, el tercer entero \(z\) no puede superar
$$z_{\max}=n-1-x-y.$$
Por tanto, solo importan los valores \(z\le z_{\max}\). La condición \(x\le y\) elimina una simetría de antemano; otra multiplicidad la restituye más adelante.
La prueba de frontera usada por las implementaciones es equivalente a
$$z^2\ge 4(x+y+z+1)xy.$$
Llevando el término mixto a la izquierda y completando el cuadrado se obtiene
$$z^2-4xyz\ge 4xy(x+y+1),$$
$$\left(z-2xy\right)^2\ge 4xy(x+1)(y+1).$$
Por lo tanto, el menor entero admisible es
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil.$$
Si \(z_{\min}>z_{\max}\), el par \((x,y)\) no aporta nada.
Si el intervalo \([z_{\min},z_{\max}]\) no está vacío, un primer conteo da
$$2\left(z_{\max}-z_{\min}+1\right),$$
porque cada \(z\) admisible suele corresponder a dos configuraciones simétricas. Hay un único caso de borde: cuando
$$z_{\min}^2=4(x+y+z_{\min}+1)xy,$$
el extremo inferior cae exactamente sobre la frontera de simetría y el conteo doblado se pasa en \(1\). Definimos
$$\varepsilon(x,y)=\begin{cases} 1,&z_{\min}^2=4(x+y+z_{\min}+1)xy,\\ 0,&\text{otherwise.} \end{cases}$$
Entonces el conteo local exacto es
$$c(x,y)=2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y).$$
Quedan dos multiplicidades externas. Primero, si \(x\ne y\), intercambiar \(x\) e \(y\) produce una configuración distinta, mientras que el caso diagonal \(x=y\) debe contarse una sola vez. Por eso
$$\mu(x,y)=\begin{cases} 1,&x=y,\\ 2,&x\ne y. \end{cases}$$
Segundo, la fórmula incluye además un factor \(3\), que refleja las tres colocaciones equivalentes tratadas simétricamente en el marco triangular. Así,
$$C(n)=3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\,c(x,y).$$
Al combinar el término base cúbico con la suma corregida sobre pares se obtiene
$$\Psi(n)=\frac{(n+18)(n-1)(n-2)}{6}+3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\left(2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y)\right),$$
donde
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil,\qquad z_{\max}=n-1-x-y.$$
Esa es exactamente la cantidad que calculan las implementaciones antes de la reducción final módulo \(10^9+7\).
El término base vale
$$B(10)=\frac{(10+18)(10-1)(10-2)}{6}=336.$$
El recorrido de pares solo necesita \(4xy\le 10\). El par \((x,y)=(1,1)\) produce
$$z_{\min}=2+\left\lceil\sqrt{16}\right\rceil=6,\qquad z_{\max}=10-1-1-1=7.$$
Por tanto, el conteo doblado preliminar es
$$2(7-6+1)=4.$$
Como
$$6^2=4(1+1+6+1)\cdot 1\cdot 1=36,$$
la corrección de borde resta \(1\), de modo que \(c(1,1)=3\). Como \(x=y\), el factor de simetría es \(\mu(1,1)=1\), y la contribución total es
$$3\cdot 1\cdot 3=9.$$
El siguiente par candidato \((1,2)\) ya falla porque
$$z_{\min}=4+\left\lceil\sqrt{48}\right\rceil=11>z_{\max}=6.$$
En consecuencia,
$$\Psi(10)=336+9=345,$$
que coincide con el valor exacto de comprobación usado por la implementación.
La implementación en C++ evalúa la suma prefijo exactamente con aritmética entera de 128 bits y usa raíces cuadradas enteras corregidas para que los valores de piso y techo sean matemáticamente exactos. Recorre \(x\) mientras \(4x^2\le n\), luego \(y\ge x\) mientras \(4xy\le n\), calcula el intervalo admisible de \(z\), aplica la corrección de un solo punto cuando hay igualdad en la frontera y acumula la contribución ponderada.
La implementación en Java usa la misma enumeración de pares y la misma lógica exacta de raíz cuadrada entera, pero mantiene toda la aritmética módulo \(10^9+7\) para que el término base cúbico no desborde. La implementación en Python es un envoltorio ligero del mismo algoritmo en C++: compila el programa en C++ cuando hace falta, lo ejecuta y devuelve la respuesta numérica parseada.
El bucle exterior satisface \(x\le \sqrt{n/4}\). Para un \(x\) fijo, el bucle interior recorre
$$y=x,x+1,\dots,\left\lfloor\frac{n}{4x}\right\rfloor.$$
Por ello, el número de pares visitados es
$$\sum_{x\le \sqrt{n/4}}\left(\left\lfloor\frac{n}{4x}\right\rfloor-x+1\right)=O(n\log n).$$
Cada par se procesa en tiempo constante, así que el tiempo total es \(O(n\log n)\) con memoria auxiliar \(O(1)\). En la práctica, la restricción hiperbólica \(4xy\le n\) reduce mucho el recorrido frente a una búsqueda cuadrática completa.
第 747 题要求计算与“三角披萨”构型有关的累积计数函数 \(\Psi(n)\)，最终需要输出的是 \(\Psi(10^8)\bmod (10^9+7)\)。C++、Python 和 Java 三份实现都没有直接枚举所有构型，而是把整个计数过程拆成两个部分：一个可以直接写成闭式的三次基项，以及一个按整数对 \((x,y)\) 精确求和的修正项。
实现中实际计算的是下面这个精确前缀公式：
$$\Psi(n)=B(n)+C(n),\qquad B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
其中 \(B(n)\) 已经把“容易处理”的那一类构型压缩成了一个三次多项式；真正需要枚举的是修正项 \(C(n)\)，它负责把剩下的构型精确补回来。
对任意 \(n\)，计算都从
$$B(n)=\frac{(n+18)(n-1)(n-2)}{6}$$
开始。这个表达式只是一个三次多项式，因此可以在常数时间内得到。之后才需要处理真正困难的部分，也就是由三个正整数决定、并且受到二次边界约束的那一类构型。
修正项按照满足
$$1\le x\le y,\qquad 4xy\le n$$
的整数对来组织。对每一个这样的 \((x,y)\)，第三个整数 \(z\) 不可能超过
$$z_{\max}=n-1-x-y.$$
因此只需要考虑 \(z\le z_{\max}\) 的情形。条件 \(x\le y\) 先把一部分对称性消掉，等到后面汇总时再通过额外的倍数补回来。
代码里使用的边界判定等价于
$$z^2\ge 4(x+y+z+1)xy.$$
把混合项移到左边，再配方，可以得到
$$z^2-4xyz\ge 4xy(x+y+1),$$
$$\left(z-2xy\right)^2\ge 4xy(x+1)(y+1).$$
于是，满足条件的最小整数 \(z\) 就是
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil.$$
如果出现 \(z_{\min}>z_{\max}\)，说明这个 \((x,y)\) 根本没有可行的 \(z\)，它对总和没有贡献。
一旦区间 \([z_{\min},z_{\max}]\) 非空，最直接的计数是
$$2\left(z_{\max}-z_{\min}+1\right),$$
因为通常每一个可行的 \(z\) 都对应两个对称构型。但这里有一个必须单独处理的边界点：当
$$z_{\min}^2=4(x+y+z_{\min}+1)xy$$
时，下端点正好落在对称边界上，这时“乘以 2”的做法会多算 \(1\) 个。于是定义
$$\varepsilon(x,y)=\begin{cases} 1,&z_{\min}^2=4(x+y+z_{\min}+1)xy,\\ 0,&\text{otherwise.} \end{cases}$$
那么固定 \((x,y)\) 时的精确局部计数为
$$c(x,y)=2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y).$$
外层还有两个倍数需要恢复。第一，如果 \(x\ne y\)，交换 \(x\) 和 \(y\) 会得到另一个不同的构型；而当 \(x=y\) 时，这种交换不会产生新情况，所以只能算一次。于是定义
$$\mu(x,y)=\begin{cases} 1,&x=y,\\ 2,&x\ne y. \end{cases}$$
第二，整个公式还要再乘一个 \(3\)，对应题目中三角结构里被视为等价的三种放置方式。因此修正项写成
$$C(n)=3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\,c(x,y).$$
把闭式基项和修正后的双重求和合并起来，就得到
$$\Psi(n)=\frac{(n+18)(n-1)(n-2)}{6}+3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\left(2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y)\right),$$
其中
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil,\qquad z_{\max}=n-1-x-y.$$
这就是三份实现真正计算的数学对象，最后再对 \(10^9+7\) 取模。
先算基项：
$$B(10)=\frac{(10+18)(10-1)(10-2)}{6}=336.$$
接下来只需要检查满足 \(4xy\le 10\) 的整数对。对 \((x,y)=(1,1)\)，有
$$z_{\min}=2+\left\lceil\sqrt{16}\right\rceil=6,\qquad z_{\max}=10-1-1-1=7.$$
所以初步的双倍计数是
$$2(7-6+1)=4.$$
但是这里恰好满足
$$6^2=4(1+1+6+1)\cdot 1\cdot 1=36,$$
因此边界修正要减去 \(1\)，得到 \(c(1,1)=3\)。又因为 \(x=y\)，所以 \(\mu(1,1)=1\)，这个整数对的总贡献是
$$3\cdot 1\cdot 3=9.$$
再看下一个候选 \((1,2)\)：
$$z_{\min}=4+\left\lceil\sqrt{48}\right\rceil=11>z_{\max}=6,$$
已经没有可行的 \(z\) 了。于是最终
$$\Psi(10)=336+9=345,$$
这与实现里使用的精确校验值完全一致。
C++ 实现先用 128 位整数精确计算整个前缀和，并使用经过修正的整数平方根过程，确保向下取整和向上取整的结果都是严格正确的。它在 \(4x^2\le n\) 的范围内枚举 \(x\)，再在 \(4xy\le n\) 的范围内枚举满足 \(y\ge x\) 的 \(y\)，据此求出可行的 \(z\) 区间；如果下端点恰好处在边界上，就执行一次单点修正，然后把加权贡献累加到答案中。
Java 实现使用完全相同的整数对枚举方式和同样的整数平方根逻辑，不过它从一开始就在模 \(10^9+7\) 下进行运算，以避免三次基项溢出。Python 实现本身并不重写算法，而是作为同一套 C++ 算法的轻量封装：需要时先编译 C++ 程序，再执行它，并把输出解析成最终答案。
外层循环满足 \(x\le \sqrt{n/4}\)。当 \(x\) 固定后，内层循环遍历
$$y=x,x+1,\dots,\left\lfloor\frac{n}{4x}\right\rfloor.$$
因此被访问的整数对总数为
$$\sum_{x\le \sqrt{n/4}}\left(\left\lfloor\frac{n}{4x}\right\rfloor-x+1\right)=O(n\log n).$$
每一个整数对都只需常数时间处理，所以总时间复杂度是 \(O(n\log n)\)，辅助空间复杂度是 \(O(1)\)。实际运行时，由于 \(4xy\le n\) 形成的是双曲线区域，扫描规模会远小于朴素的二维全枚举。
В задаче 747 требуется вычислить накопительную функцию \(\Psi(n)\), связанную с конфигурациями «треугольной пиццы»; итоговый ответ равен \(\Psi(10^8)\bmod (10^9+7)\). Реализации на C++, Python и Java не перебирают конфигурации напрямую. Вместо этого они используют точное разложение на замкнутый кубический базовый член и корректирующую сумму по целочисленным парам \((x,y)\).
Реализации вычисляют точную префиксную формулу
$$\Psi(n)=B(n)+C(n),\qquad B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
Полином \(B(n)\) уже в закрытом виде описывает простую часть подсчета. Основная работа сосредоточена в корректирующем члене \(C(n)\), который добирает все остальные конфигурации через структурированный перебор целых параметров.
Для каждого \(n\) вычисление начинается с
$$B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
Это кубический полином, поэтому он считается за константное время. После этого остается добавить нетривиальную часть, зависящую от трех положительных целых чисел и ограниченную квадратичной границей.
Корректирующая сумма организована по парам
$$1\le x\le y,\qquad 4xy\le n.$$
Для каждой такой пары третье число \(z\) не может превышать
$$z_{\max}=n-1-x-y.$$
Значит, существенны только значения \(z\le z_{\max}\). Ограничение \(x\le y\) заранее убирает одну симметрию; позднее она восстанавливается отдельным множителем кратности.
Граничная проверка, используемая в реализациях, эквивалентна неравенству
$$z^2\ge 4(x+y+z+1)xy.$$
Перенесем смешанный член влево и дополним до квадрата:
$$z^2-4xyz\ge 4xy(x+y+1),$$
$$\left(z-2xy\right)^2\ge 4xy(x+1)(y+1).$$
Отсюда минимальное допустимое целое значение равно
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil.$$
Если \(z_{\min}>z_{\max}\), то пара \((x,y)\) не дает вклада.
Если отрезок \([z_{\min},z_{\max}]\) непуст, первоначальный подсчет дает
$$2\left(z_{\max}-z_{\min}+1\right),$$
потому что обычно каждому допустимому \(z\) соответствуют две симметричные конфигурации. Но есть один особый пограничный случай: когда
$$z_{\min}^2=4(x+y+z_{\min}+1)xy,$$
левая граница лежит ровно на линии симметрии, и удвоенный подсчет завышает результат на \(1\). Поэтому вводим
$$\varepsilon(x,y)=\begin{cases} 1,&z_{\min}^2=4(x+y+z_{\min}+1)xy,\\ 0,&\text{otherwise.} \end{cases}$$
Тогда точное локальное количество равно
$$c(x,y)=2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y).$$
Остаются два внешних множителя. Во-первых, если \(x\ne y\), перестановка \(x\) и \(y\) дает другую конфигурацию, а диагональный случай \(x=y\) должен считаться только один раз. Поэтому
$$\mu(x,y)=\begin{cases} 1,&x=y,\\ 2,&x\ne y. \end{cases}$$
Во-вторых, вся формула умножается еще на \(3\), что отражает три эквивалентных размещения в треугольной структуре задачи. Следовательно,
$$C(n)=3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\,c(x,y).$$
Объединяя кубический базовый член и исправленную сумму по парам, получаем
$$\Psi(n)=\frac{(n+18)(n-1)(n-2)}{6}+3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\left(2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y)\right),$$
где
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil,\qquad z_{\max}=n-1-x-y.$$
Именно эту величину реализации вычисляют до финального взятия по модулю \(10^9+7\).
Базовый член равен
$$B(10)=\frac{(10+18)(10-1)(10-2)}{6}=336.$$
В переборе пар нужно рассматривать только случаи с \(4xy\le 10\). Для \((x,y)=(1,1)\) получаем
$$z_{\min}=2+\left\lceil\sqrt{16}\right\rceil=6,\qquad z_{\max}=10-1-1-1=7.$$
Предварительный удвоенный счет дает
$$2(7-6+1)=4.$$
Но здесь выполняется
$$6^2=4(1+1+6+1)\cdot 1\cdot 1=36,$$
поэтому граничная поправка вычитает \(1\), и остается \(c(1,1)=3\). Так как \(x=y\), имеем \(\mu(1,1)=1\), значит вклад пары равен
$$3\cdot 1\cdot 3=9.$$
Следующая кандидатная пара \((1,2)\) уже не проходит, потому что
$$z_{\min}=4+\left\lceil\sqrt{48}\right\rceil=11>z_{\max}=6.$$
Итак,
$$\Psi(10)=336+9=345,$$
что совпадает с точным контрольным значением, используемым в реализации.
Реализация на C++ вычисляет префиксную сумму точно в 128-битной целочисленной арифметике и использует скорректированные целочисленные квадратные корни, чтобы значения floor и ceiling были математически точными. Она перебирает \(x\) при условии \(4x^2\le n\), затем перебирает \(y\ge x\) при \(4xy\le n\), находит допустимый интервал для \(z\), применяет одноточечную пограничную поправку при равенстве и добавляет взвешенный вклад в ответ.
Реализация на Java использует тот же перебор пар и ту же точную логику целочисленного квадратного корня, но всю арифметику ведет по модулю \(10^9+7\), чтобы кубический базовый член не переполнялся. Реализация на Python служит тонкой оболочкой над тем же алгоритмом на C++: при необходимости она компилирует программу, запускает ее и возвращает распарсенный численный результат.
Внешний цикл удовлетворяет \(x\le \sqrt{n/4}\). Для фиксированного \(x\) внутренний цикл проходит по
$$y=x,x+1,\dots,\left\lfloor\frac{n}{4x}\right\rfloor.$$
Поэтому число посещенных пар равно
$$\sum_{x\le \sqrt{n/4}}\left(\left\lfloor\frac{n}{4x}\right\rfloor-x+1\right)=O(n\log n).$$
Каждая пара обрабатывается за константное время, так что полное время работы равно \(O(n\log n)\), а дополнительная память равна \(O(1)\). На практике гиперболическое ограничение \(4xy\le n\) делает область перебора намного меньше, чем полный квадратичный просмотр.
تطلب المسألة 747 حساب دالة تراكمية \(\Psi(n)\) مرتبطة بتراكيب «البيتزا المثلثة»، والقيمة النهائية المطلوبة هي \(\Psi(10^8)\bmod (10^9+7)\). لا تقوم تطبيقات C++ وPython وJava بتوليد جميع التراكيب مباشرة، بل تعتمد على تفكيك دقيق إلى حد أساسي تكعيبي مغلق وحد تصحيحي مفهرس بأزواج صحيحة \((x,y)\).
الكمية التي تحسبها التطبيقات فعليا هي صيغة بادئة دقيقة من الشكل
$$\Psi(n)=B(n)+C(n),\qquad B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
يمثل كثير الحدود \(B(n)\) العائلة السهلة بعد تبسيطها جبريا. أما الجزء المهم فهو حد التصحيح \(C(n)\)، لأنه يعيد إدخال التراكيب المتبقية بواسطة مسح منظم لمعاملات صحيحة.
لكل \(n\) يبدأ الحساب من
$$B(n)=\frac{(n+18)(n-1)(n-2)}{6}.$$
هذا مجرد كثير حدود تكعيبي، لذلك يمكن تقييمه بزمن ثابت. بعد ذلك لا يبقى إلا إضافة الجزء غير البسيط الذي يعتمد على ثلاثة أعداد صحيحة موجبة تخضع لحد تربيعي.
ينظم حد التصحيح عبر الأزواج التي تحقق
$$1\le x\le y,\qquad 4xy\le n.$$
ولكل زوج من هذا النوع فإن العدد الثالث \(z\) لا يمكن أن يتجاوز
$$z_{\max}=n-1-x-y.$$
إذن لا نحتاج إلا إلى القيم التي تحقق \(z\le z_{\max}\). الشرط \(x\le y\) يزيل تماثلا واحدا مسبقا، ثم يعاد هذا التماثل لاحقا بعامل تعدد منفصل.
اختبار الحد المستعمل في التطبيقات يكافئ المتباينة
$$z^2\ge 4(x+y+z+1)xy.$$
بنقل الحد المختلط إلى الطرف الأيسر وإكمال المربع نحصل على
$$z^2-4xyz\ge 4xy(x+y+1),$$
$$\left(z-2xy\right)^2\ge 4xy(x+1)(y+1).$$
ومن ثم فإن أصغر عدد صحيح مقبول هو
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil.$$
إذا كان \(z_{\min}>z_{\max}\)، فهذا يعني أن الزوج \((x,y)\) لا يساهم بأي شيء.
إذا كان المجال \([z_{\min},z_{\max}]\) غير فارغ، فإن العد الأولي يعطي
$$2\left(z_{\max}-z_{\min}+1\right),$$
لأن كل قيمة مقبولة لـ \(z\) تمثل عادة تركيبين متناظرين. لكن هناك حالة حدية واحدة: عندما
$$z_{\min}^2=4(x+y+z_{\min}+1)xy,$$
يقع الطرف الأدنى تماما على حد التماثل، وعندها يكون العد المضاعف أكبر من الصحيح بمقدار \(1\). لذلك نعرف
$$\varepsilon(x,y)=\begin{cases} 1,&z_{\min}^2=4(x+y+z_{\min}+1)xy,\\ 0,&\text{otherwise.} \end{cases}$$
وعندئذ يكون العدد المحلي الدقيق
$$c(x,y)=2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y).$$
تبقى عاملتا تعدد خارجيتان. الأولى أن تبديل \(x\) و\(y\) عندما \(x\ne y\) يعطي تركيبا مختلفا، بينما حالة القطر \(x=y\) يجب أن تحسب مرة واحدة فقط. لذلك نضع
$$\mu(x,y)=\begin{cases} 1,&x=y,\\ 2,&x\ne y. \end{cases}$$
والثانية أن الصيغة تضرب أيضا في \(3\)، وهو ما يعكس ثلاث وضعيات متكافئة تعاملها المسألة على قدم المساواة داخل البنية المثلثة. لذلك يصبح
$$C(n)=3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\,c(x,y).$$
بجمع الحد الأساسي التكعيبي مع مجموع الأزواج المصحح نحصل على
$$\Psi(n)=\frac{(n+18)(n-1)(n-2)}{6}+3\sum_{\substack{1\le x\le y\\4xy\le n}}\mu(x,y)\left(2\left(z_{\max}-z_{\min}+1\right)-\varepsilon(x,y)\right),$$
حيث
$$z_{\min}=2xy+\left\lceil\sqrt{4xy(x+1)(y+1)}\right\rceil,\qquad z_{\max}=n-1-x-y.$$
وهذه هي الكمية التي تحسبها التطبيقات فعلا قبل أخذ الباقي modulo \(10^9+7\).
الحد الأساسي يساوي
$$B(10)=\frac{(10+18)(10-1)(10-2)}{6}=336.$$
ولا نحتاج في مسح الأزواج إلا إلى القيم التي تحقق \(4xy\le 10\). بالنسبة إلى \((x,y)=(1,1)\) نجد
$$z_{\min}=2+\left\lceil\sqrt{16}\right\rceil=6,\qquad z_{\max}=10-1-1-1=7.$$
إذن العد المضاعف الأولي هو
$$2(7-6+1)=4.$$
لكن بما أن
$$6^2=4(1+1+6+1)\cdot 1\cdot 1=36,$$
فإن تصحيح الحد يطرح \(1\)، فيبقى \(c(1,1)=3\). ولأن \(x=y\)، فإن عامل التماثل هو \(\mu(1,1)=1\)، وبالتالي تكون المساهمة
$$3\cdot 1\cdot 3=9.$$
أما الزوج المرشح التالي \((1,2)\) فيفشل مباشرة لأن
$$z_{\min}=4+\left\lceil\sqrt{48}\right\rceil=11>z_{\max}=6.$$
إذن
$$\Psi(10)=336+9=345,$$
وهو تماما مقدار التحقق الدقيق المستخدم في التطبيق.
تقوم نسخة C++ بحساب مجموع البادئة بدقة باستخدام أعداد صحيحة بعرض 128 بت، وتستعمل جذورا تربيعية صحيحة مصححة حتى تكون قيمتا floor وceiling صحيحتين تماما من الناحية الرياضية. فهي تمر على \(x\) ما دام \(4x^2\le n\)، ثم على \(y\ge x\) ما دام \(4xy\le n\)، وتحسب مجال \(z\) المسموح، وتطبق تصحيحا حديا من نقطة واحدة عند تحقق المساواة، ثم تضيف المساهمة الموزونة إلى الجواب.
أما نسخة Java فتستخدم تعداد الأزواج نفسه ومنطق الجذر التربيعي الصحيح نفسه، لكنها تجري الحسابات كلها modulo \(10^9+7\) كي لا يفيض الحد الأساسي التكعيبي. ونسخة Python ليست إعادة مستقلة للخوارزمية، بل غلاف خفيف حول الخوارزمية نفسها في C++: فهي تبني البرنامج عند الحاجة، وتشغله، ثم تستخرج الجواب العددي من المخرجات.
تخضع الحلقة الخارجية للشرط \(x\le \sqrt{n/4}\). ولـ \(x\) ثابت، تجري الحلقة الداخلية على
$$y=x,x+1,\dots,\left\lfloor\frac{n}{4x}\right\rfloor.$$
ومن ثم فإن عدد الأزواج المزارة يساوي
$$\sum_{x\le \sqrt{n/4}}\left(\left\lfloor\frac{n}{4x}\right\rfloor-x+1\right)=O(n\log n).$$
كل زوج يعالج في زمن ثابت، لذلك يكون الزمن الكلي \(O(n\log n)\) مع ذاكرة إضافية \(O(1)\). وعمليا يجعل القيد الزائدي \(4xy\le n\) مساحة المسح أصغر بكثير من بحث تربيعي كامل.