We want to count how many integers \(n \lt 10^6\) have exactly ten representations of the form
$$x^2-y^2-z^2=n,$$
where \(x\), \(y\), and \(z\) are positive integers in arithmetic progression. Because the three numbers are consecutive terms of one progression, they are not independent: once the middle term and the common difference are known, the triple is fixed.
The key step is to convert the quadratic expression into a constrained factorization of \(n\). After that, the problem becomes a sieve over admissible factor pairs rather than a search over triples.
The implementations are built around one exact reformulation: every valid triple corresponds to one ordered factor pair \((u,v)\) of \(n\) satisfying a congruence condition and a positivity bound.
If \(x\), \(y\), and \(z\) are in arithmetic progression, we may write
$$x=a+d,\qquad y=a,\qquad z=a-d,$$
with integers \(a \ge 1\) and \(d \ge 1\). The positivity of \(z\) forces \(a>d\).
Substituting into the expression gives
$$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a).$$
So every solution is encoded by two positive integers: the middle term \(a\) and the quantity \(4d-a\).
Define
$$u=a,\qquad v=4d-a.$$
Then the formula becomes simply
$$n=uv.$$
This already explains why the code counts products instead of recomputing quadratic expressions. The arithmetic progression condition has not disappeared; it has been packed into restrictions on \((u,v)\).
Since \(u+v=a+(4d-a)=4d\), we obtain the congruence
$$u+v\equiv 0 \pmod 4.$$
Also, \(z=a-d>0\) means \(d<a\). Rewriting \(d=(u+v)/4\), this becomes
$$\frac{u+v}{4}<u \qquad\Longleftrightarrow\qquad v<3u.$$
Therefore every valid solution yields an ordered factor pair \((u,v)\) such that
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
The correspondence is not just one-way. Suppose \(u\) and \(v\) are positive integers satisfying
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
Set
$$a=u,\qquad d=\frac{u+v}{4}.$$
The congruence ensures that \(d\) is an integer. Then
$$z=a-d=u-\frac{u+v}{4}=\frac{3u-v}{4}>0,$$
so the triple is positive, and
$$x=a+d,\qquad y=a,\qquad z=a-d$$
is indeed an arithmetic progression. Finally,
$$a(4d-a)=u\bigl((u+v)-u\bigr)=uv=n.$$
Hence the number of representations of \(n\) is exactly the number of ordered factor pairs \((u,v)\) with those two conditions. This is the real counting object used by the implementations.
The positive factor pairs of \(27\) are
$$ (1,27),\ (3,9),\ (9,3),\ (27,1). $$
Now apply the two filters.
The congruence \(u+v\equiv 0 \pmod 4\) keeps all four pairs, because each sum is \(28\) or \(12\). The inequality \(v<3u\) removes \((1,27)\) and \((3,9)\), leaving
$$ (9,3)\quad\text{and}\quad(27,1). $$
These correspond to
$$a=9,\ d=3 \Rightarrow (x,y,z)=(12,9,6),$$
and
$$a=27,\ d=7 \Rightarrow (x,y,z)=(34,27,20).$$
Indeed, both give \(x^2-y^2-z^2=27\). So \(27\) has exactly two valid representations.
For a fixed search bound \(N\), we only care about products \(uv<N\). Once \(u\) is fixed, the admissible values of \(v\) must satisfy three conditions at once:
$$v\equiv -u \pmod 4,$$
$$1\le v\le \left\lfloor\frac{N-1}{u}\right\rfloor,$$
$$v\le 3u-1.$$
So for each \(u\), the companion factors \(v\) form one arithmetic progression with step \(4\), starting from the smallest positive value congruent to \(-u\) modulo \(4\), and ending at
$$\min\left(3u-1,\left\lfloor\frac{N-1}{u}\right\rfloor\right).$$
Each admissible pair contributes one representation to the counter of \(n=uv\). After processing all \(u\), the answer is the number of entries whose counter equals \(10\).
The C++, Python, and Java implementations allocate an array of counters indexed by \(n\). They sweep the first factor through all positive values below the limit. For each such value, they compute the largest possible companion factor allowed by the product bound \(uv<10^6\) and by the positivity condition \(v<3u\).
Next, the implementation finds the first positive companion factor in the correct congruence class \(v\equiv -u\pmod 4\). From there it advances by steps of \(4\), so every visited companion factor automatically satisfies the divisibility condition \(u+v\equiv 0\pmod 4\). Each visited pair updates the counter for the product \(uv\).
Once the sieve is complete, the remaining task is a single scan through the counter array. Every index whose counter is exactly \(10\) contributes to the final total.
The three implementations follow the same mathematics and the same iteration pattern. One of them also includes a small built-in checkpoint: for the smaller bound \(n \lt 10000\), the number of targets is \(45\), which is a useful sanity test before solving the full problem.
Let \(N\) be the upper bound, here \(N=10^6\). For a fixed first factor \(u\), the number of tested companion factors is proportional to
$$1+\frac{1}{4}\min\left(3u,\frac{N}{u}\right).$$
Summing over all \(u\) gives an \(O(N\log N)\) sieve. Intuitively, small values of \(u\) are limited by the product condition \(uv<N\), while large values of \(u\) are limited by the linear bound \(v<3u\); the harmonic part of the sum is what produces the logarithm.
The memory usage is \(O(N)\), because the dominant data structure is the counter array for \(0\) through \(N-1\). No large auxiliary tables are needed.
Gesucht ist die Anzahl der ganzen Zahlen \(n \lt 10^6\), die genau zehn Darstellungen der Form
$$x^2-y^2-z^2=n$$
besitzen, wobei \(x\), \(y\) und \(z\) positive ganze Zahlen in arithmetischer Progression sind. Da die drei Zahlen auf einer einzigen Progression liegen, wird das Problem vollständig durch den Mittelwert und die gemeinsame Differenz bestimmt.
Der entscheidende Schritt besteht darin, den quadratischen Ausdruck in eine Faktorisierungsaufgabe mit Nebenbedingungen umzuschreiben. Danach zählt man keine Tripel mehr direkt, sondern zulässige Faktorpaare.
Die Implementierungen beruhen auf einer exakten Umformulierung: Jede gültige Lösung entspricht genau einem geordneten Faktorpaar \((u,v)\) von \(n\), das eine Kongruenzbedingung und eine Positivitätsbedingung erfüllt.
Weil \(x\), \(y\) und \(z\) in arithmetischer Progression liegen, schreiben wir
$$x=a+d,\qquad y=a,\qquad z=a-d,$$
mit ganzen Zahlen \(a \ge 1\) und \(d \ge 1\). Aus \(z>0\) folgt sofort \(a>d\).
Einsetzen in den Ausdruck liefert
$$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a).$$
Jede Lösung wird also durch den Mittelterm \(a\) und die Größe \(4d-a\) beschrieben.
Setze
$$u=a,\qquad v=4d-a.$$
Dann vereinfacht sich die Formel zu
$$n=uv.$$
Genau deshalb zählen die Programme Produkte, statt den quadratischen Ausdruck jedes Mal neu auszurechnen. Die Bedingung „arithmetische Progression“ steckt nun vollständig in Bedingungen an \((u,v)\).
Weil \(u+v=a+(4d-a)=4d\) gilt, folgt die Kongruenz
$$u+v\equiv 0 \pmod 4.$$
Außerdem ist \(z=a-d>0\), also \(d<a\). Mit \(d=(u+v)/4\) wird daraus
$$\frac{u+v}{4}<u \qquad\Longleftrightarrow\qquad v<3u.$$
Jede gültige Lösung erzeugt also ein geordnetes Faktorpaar \((u,v)\) mit
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
Die Zuordnung funktioniert auch rückwärts. Seien \(u\) und \(v\) positive ganze Zahlen mit
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
Definiere
$$a=u,\qquad d=\frac{u+v}{4}.$$
Wegen der Kongruenz ist \(d\) ganzzahlig. Dann gilt
$$z=a-d=u-\frac{u+v}{4}=\frac{3u-v}{4}>0,$$
also ist das Tripel positiv, und
$$x=a+d,\qquad y=a,\qquad z=a-d$$
bildet tatsächlich eine arithmetische Progression. Außerdem folgt
$$a(4d-a)=u\bigl((u+v)-u\bigr)=uv=n.$$
Damit ist die Anzahl der Darstellungen von \(n\) exakt die Anzahl geordneter Faktorpaare \((u,v)\) mit diesen beiden Bedingungen. Genau dieses Objekt zählen die Implementierungen.
Die positiven Faktorpaare von \(27\) sind
$$ (1,27),\ (3,9),\ (9,3),\ (27,1). $$
Nun werden die beiden Filter angewandt.
Die Kongruenz \(u+v\equiv 0 \pmod 4\) lässt alle vier Paare zu, denn die Summen sind \(28\) beziehungsweise \(12\). Die Ungleichung \(v<3u\) eliminiert \((1,27)\) und \((3,9)\), übrig bleiben
$$ (9,3)\quad\text{und}\quad(27,1). $$
Daraus erhält man
$$a=9,\ d=3 \Rightarrow (x,y,z)=(12,9,6),$$
und
$$a=27,\ d=7 \Rightarrow (x,y,z)=(34,27,20).$$
Beide Tripel erfüllen \(x^2-y^2-z^2=27\). Also besitzt \(27\) genau zwei gültige Darstellungen.
Für eine feste Schranke \(N\) interessieren nur Produkte \(uv<N\). Ist \(u\) fest, dann müssen die zulässigen Werte von \(v\) gleichzeitig drei Bedingungen erfüllen:
$$v\equiv -u \pmod 4,$$
$$1\le v\le \left\lfloor\frac{N-1}{u}\right\rfloor,$$
$$v\le 3u-1.$$
Für jedes \(u\) bilden die möglichen Werte von \(v\) daher genau eine arithmetische Progression mit Schrittweite \(4\). Sie beginnt beim kleinsten positiven Wert mit der richtigen Restklasse und endet bei
$$\min\left(3u-1,\left\lfloor\frac{N-1}{u}\right\rfloor\right).$$
Jedes zulässige Paar liefert genau eine Darstellung für \(n=uv\). Nach der Verarbeitung aller \(u\) ist die gesuchte Antwort die Anzahl der Werte mit Zähler gleich \(10\).
Die C++-, Python- und Java-Implementierungen legen ein Zählerarray an, dessen Index direkt dem Wert \(n\) entspricht. Dann durchlaufen sie den ersten Faktor von \(1\) bis knapp unter die Schranke. Für jeden solchen Wert wird die größte zulässige zweite Zahl bestimmt, einmal aus der Produktbedingung \(uv<10^6\) und einmal aus der Positivitätsbedingung \(v<3u\).
Anschließend wird der kleinste positive zweite Faktor in der richtigen Restklasse \(v\equiv -u\pmod 4\) gefunden. Von dort aus geht die Schleife in Schritten von \(4\) weiter, sodass jede besuchte Zahl automatisch die Kongruenz \(u+v\equiv 0\pmod 4\) erfüllt. Für jedes solcher Paare wird der Zähler des Produkts \(uv\) erhöht.
Nach dem Siebdurchlauf bleibt nur noch ein linearer Scan über das Zählerarray. Jeder Index, dessen Zähler genau \(10\) ist, trägt eins zur Endsumme bei.
Alle drei Implementierungen verwenden dieselbe Mathematik und dasselbe Iterationsmuster. Eine davon enthält zusätzlich einen kleinen eingebauten Kontrolltest: Für die kleinere Schranke \(n \lt 10000\) ist die Anzahl der Treffer \(45\).
Sei \(N\) die obere Schranke, hier also \(N=10^6\). Für festen ersten Faktor \(u\) ist die Zahl der geprüften zweiten Faktoren proportional zu
$$1+\frac{1}{4}\min\left(3u,\frac{N}{u}\right).$$
Über alle \(u\) summiert ergibt das ein Sieb der Größe \(O(N\log N)\). Anschaulich werden kleine Werte von \(u\) durch die Produktbedingung \(uv<N\) begrenzt, große Werte von \(u\) dagegen durch die lineare Schranke \(v<3u\); der harmonische Anteil der Summe erzeugt den Logarithmus.
Der Speicherverbrauch ist \(O(N)\), weil die dominante Datenstruktur das Zählerarray für \(0\) bis \(N-1\) ist. Große Hilfstabellen sind nicht nötig.
Amaç,
$$x^2-y^2-z^2=n$$
denklemine tam olarak on farklı gösterimi olan \(n \lt 10^6\) değerlerinin sayısını bulmaktır. Burada \(x\), \(y\) ve \(z\) pozitif tam sayılardır ve aynı aritmetik dizinin ardışık üç terimini oluştururlar. Bu yüzden üç değişken serbest değildir; orta terim ile ortak fark bilindiğinde tüm üçlü belirlenir.
Çözümün temel fikri, ikinci dereceden ifadeyi kısıtlı bir çarpan çiftine dönüştürmektir. Böylece problem, üçlü aramak yerine uygun çarpan çiftlerini eleyen bir sayma problemine dönüşür.
Uygulamalar tek bir kesin yeniden yazıma dayanır: Her geçerli çözüm, \(n\)'nin sıralı bir \((u,v)\) çarpan çiftine bire bir karşılık gelir ve bu çiftin hem modüler hem de pozitiflikten gelen bir eşitsizlik koşulunu sağlaması gerekir.
\(x\), \(y\) ve \(z\) aritmetik dizide olduğundan
$$x=a+d,\qquad y=a,\qquad z=a-d,$$
yazabiliriz. Burada \(a \ge 1\) ve \(d \ge 1\) tam sayıdır. \(z>0\) koşulu doğrudan \(a>d\) verir.
Bunu denkleme koyarsak
$$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a)$$
elde edilir. Demek ki her çözüm, orta terim \(a\) ile \(4d-a\) miktarı üzerinden kodlanabilir.
Şimdi
$$u=a,\qquad v=4d-a$$
tanımlarını yapalım. O zaman formül
$$n=uv$$
şeklini alır. Kodların doğrudan çarpım saymasının nedeni budur; aritmetik dizi koşulu kaybolmaz, sadece \((u,v)\) üzerinde koşullara dönüşür.
\(u+v=a+(4d-a)=4d\) olduğundan
$$u+v\equiv 0 \pmod 4$$
olur. Ayrıca \(z=a-d>0\) olduğu için \(d<a\) gerekir. \(d=(u+v)/4\) yazınca bu kez
$$\frac{u+v}{4}<u \qquad\Longleftrightarrow\qquad v<3u$$
elde edilir. Sonuç olarak her geçerli çözüm şu özellikleri sağlayan sıralı bir çarpan çiftine karşılık gelir:
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
Dönüşüm ters yönde de çalışır. Pozitif \(u\) ve \(v\) için
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u$$
olsun. O zaman
$$a=u,\qquad d=\frac{u+v}{4}$$
olarak tanımlayabiliriz. Kongruens koşulu sayesinde \(d\) tam sayıdır. Dahası,
$$z=a-d=u-\frac{u+v}{4}=\frac{3u-v}{4}>0$$
olur; yani üçlü gerçekten pozitiftir. Böylece
$$x=a+d,\qquad y=a,\qquad z=a-d$$
bir aritmetik dizi verir ve ayrıca
$$a(4d-a)=u\bigl((u+v)-u\bigr)=uv=n$$
eşitliği sağlanır. Dolayısıyla \(n\)'nin gösterim sayısı, tam olarak bu koşulları sağlayan sıralı çarpan çiftlerinin sayısıdır. Yerel çözümlerin saydığı nesne budur.
\(27\)'nin pozitif çarpan çiftleri
$$ (1,27),\ (3,9),\ (9,3),\ (27,1) $$
şeklindedir. Şimdi iki filtremizi uygulayalım.
\(u+v\equiv 0 \pmod 4\) koşulu dördünü de bırakır; çünkü toplamlar \(28\) ve \(12\)'dir. Fakat \(v<3u\) eşitsizliği \((1,27)\) ile \((3,9)\) çiftlerini eler. Geriye
$$ (9,3)\quad\text{ve}\quad(27,1) $$
kalır. Bunlar sırasıyla
$$a=9,\ d=3 \Rightarrow (x,y,z)=(12,9,6),$$
ve
$$a=27,\ d=7 \Rightarrow (x,y,z)=(34,27,20)$$
üçlülerini verir. Her iki durumda da \(x^2-y^2-z^2=27\) olur. Yani \(27\) için tam iki geçerli gösterim vardır.
Sınırı \(N\) ile gösterelim. İlgilendiğimiz tek şey \(uv<N\) olan çarpımlardır. \(u\) sabitlenince \(v\) için aynı anda üç koşul gerekir:
$$v\equiv -u \pmod 4,$$
$$1\le v\le \left\lfloor\frac{N-1}{u}\right\rfloor,$$
$$v\le 3u-1.$$
Demek ki her \(u\) için geçerli \(v\) değerleri, adımı \(4\) olan tek bir aritmetik ilerlemedir. Başlangıç noktası doğru artık sınıfındaki en küçük pozitif değerdir; bitiş noktası ise
$$\min\left(3u-1,\left\lfloor\frac{N-1}{u}\right\rfloor\right)$$
olur. Her uygun çift, \(n=uv\) için sayacı bir artırır. Tüm \(u\) değerleri işlendiğinde cevap, sayacı tam \(10\) olan girişlerin sayısıdır.
C++, Python ve Java uygulamaları, her \(n\) için temsil sayısını tutan bir sayaç dizisi oluşturur. Daha sonra ilk çarpan, sınırın altındaki tüm pozitif değerler boyunca dolaştırılır. Her adımda ikinci çarpanın üst sınırı hem \(uv<10^6\) koşulundan hem de \(v<3u\) koşulundan hesaplanır.
Ardından doğru artık sınıfında olan ilk pozitif ikinci çarpan bulunur; yani \(v\equiv -u\pmod 4\). Döngü buradan sonra \(4\)'er artar. Böylece ziyaret edilen her ikinci çarpan otomatik olarak \(u+v\equiv 0\pmod 4\) koşulunu sağlar. Ziyaret edilen her çift için ilgili çarpımın sayacı artırılır.
Elek tamamlandıktan sonra yapılacak iş, sayaç dizisini bir kez taramaktır. Sayacı tam \(10\) olan her indeks son toplamı bir artırır.
Üç uygulama da aynı matematiği ve aynı tarama düzenini kullanır. Bunlardan biri ayrıca küçük bir yerleşik doğrulama içerir: \(n \lt 10000\) için hedef değerlerin sayısı \(45\) olmalıdır.
\(N\) üst sınır olsun; burada \(N=10^6\). Sabit bir \(u\) için denenmiş ikinci çarpan sayısı yaklaşık olarak
$$1+\frac{1}{4}\min\left(3u,\frac{N}{u}\right)$$
kadardır. Bunu tüm \(u\) değerleri için topladığımızda toplam maliyet \(O(N\log N)\) olur. Küçük \(u\) değerlerinde baskın kısıt çarpım sınırıdır; büyük \(u\) değerlerinde ise doğrusal sınır \(v<3u\) öne çıkar. Logaritma, bu iki bölgeyi toplarken ortaya çıkan harmonik terimden gelir.
Bellek kullanımı \(O(N)\)'dir; çünkü baskın yapı, \(0\) ile \(N-1\) arasındaki tüm değerler için tutulan sayaç dizisidir. Büyük ek tablolar gerekmez.
Se pide contar cuántos enteros \(n \lt 10^6\) tienen exactamente diez representaciones de la forma
$$x^2-y^2-z^2=n,$$
donde \(x\), \(y\) y \(z\) son enteros positivos en progresión aritmética. Como los tres términos pertenecen a una sola progresión, el triple queda determinado por el término central y la diferencia común.
La idea decisiva es transformar la expresión cuadrática en un problema de factorización con restricciones. Una vez hecho eso, ya no se buscan ternas directamente: se cuentan pares de factores admisibles.
Las implementaciones se apoyan en una reformulación exacta: cada solución válida corresponde a un par ordenado \((u,v)\) de factores de \(n\) que satisface una condición de congruencia y una desigualdad procedente de la positividad.
Si \(x\), \(y\) y \(z\) están en progresión aritmética, podemos escribir
$$x=a+d,\qquad y=a,\qquad z=a-d,$$
con enteros \(a \ge 1\) y \(d \ge 1\). La condición \(z>0\) obliga a que \(a>d\).
Sustituyendo en la expresión obtenemos
$$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a).$$
Así, toda solución queda codificada por el término central \(a\) y por la cantidad \(4d-a\).
Definimos
$$u=a,\qquad v=4d-a.$$
Entonces la fórmula se reduce a
$$n=uv.$$
Por eso el código cuenta productos en lugar de recalcular la expresión cuadrática. La condición de progresión aritmética no desaparece; queda incorporada en restricciones sobre \((u,v)\).
Como \(u+v=a+(4d-a)=4d\), se obtiene la congruencia
$$u+v\equiv 0 \pmod 4.$$
Además, \(z=a-d>0\) implica \(d<a\). Escribiendo \(d=(u+v)/4\), esto se transforma en
$$\frac{u+v}{4}<u \qquad\Longleftrightarrow\qquad v<3u.$$
Por tanto, toda solución válida produce un par ordenado \((u,v)\) con
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
La correspondencia funciona en sentido inverso. Supongamos que \(u\) y \(v\) son enteros positivos tales que
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
Definimos
$$a=u,\qquad d=\frac{u+v}{4}.$$
La congruencia garantiza que \(d\) es entero. Entonces
$$z=a-d=u-\frac{u+v}{4}=\frac{3u-v}{4}>0,$$
de modo que la terna es positiva, y
$$x=a+d,\qquad y=a,\qquad z=a-d$$
forma de verdad una progresión aritmética. Además,
$$a(4d-a)=u\bigl((u+v)-u\bigr)=uv=n.$$
En consecuencia, el número de representaciones de \(n\) es exactamente el número de pares ordenados \((u,v)\) que cumplen esas condiciones. Ese es el objeto real que cuentan las implementaciones.
Los pares positivos de factores de \(27\) son
$$ (1,27),\ (3,9),\ (9,3),\ (27,1). $$
Ahora aplicamos los dos filtros.
La congruencia \(u+v\equiv 0 \pmod 4\) deja pasar a los cuatro pares, porque las sumas son \(28\) y \(12\). La desigualdad \(v<3u\) elimina \((1,27)\) y \((3,9)\), así que permanecen
$$ (9,3)\quad\text{y}\quad(27,1). $$
Estos pares producen
$$a=9,\ d=3 \Rightarrow (x,y,z)=(12,9,6),$$
y
$$a=27,\ d=7 \Rightarrow (x,y,z)=(34,27,20).$$
Ambas ternas satisfacen \(x^2-y^2-z^2=27\). Por tanto, \(27\) tiene exactamente dos representaciones válidas.
Para una cota \(N\), solo importan los productos \(uv<N\). Fijado \(u\), los valores admisibles de \(v\) deben satisfacer simultáneamente
$$v\equiv -u \pmod 4,$$
$$1\le v\le \left\lfloor\frac{N-1}{u}\right\rfloor,$$
$$v\le 3u-1.$$
Así, para cada \(u\), los posibles valores de \(v\) forman una sola progresión aritmética de paso \(4\). Comienza en el menor valor positivo con la clase residual correcta y termina en
$$\min\left(3u-1,\left\lfloor\frac{N-1}{u}\right\rfloor\right).$$
Cada par admisible aporta una representación al contador de \(n=uv\). Después de procesar todos los valores de \(u\), la respuesta es el número de entradas cuyo contador vale \(10\).
Las implementaciones en C++, Python y Java reservan un arreglo de contadores indexado por \(n\). Luego recorren el primer factor desde \(1\) hasta justo por debajo del límite. Para cada valor calculan el mayor segundo factor permitido por la restricción del producto \(uv<10^6\) y por la restricción de positividad \(v<3u\).
Después, la implementación localiza el primer segundo factor positivo en la clase residual correcta \(v\equiv -u\pmod 4\). A partir de ahí avanza de \(4\) en \(4\), así que cada valor visitado satisface automáticamente \(u+v\equiv 0\pmod 4\). Cada par visitado incrementa el contador del producto \(uv\).
Una vez terminado el tamiz, solo queda recorrer una vez el arreglo de contadores. Cada índice cuyo contador es exactamente \(10\) contribuye uno al total final.
Las tres implementaciones siguen la misma matemática y el mismo patrón de iteración. Una de ellas además incorpora una comprobación pequeña: para la cota \(n \lt 10000\), el número correcto de objetivos es \(45\).
Sea \(N\) la cota superior; aquí \(N=10^6\). Para un primer factor fijo \(u\), el número de segundos factores probados es proporcional a
$$1+\frac{1}{4}\min\left(3u,\frac{N}{u}\right).$$
Al sumar sobre todos los valores de \(u\), se obtiene un tamiz de complejidad \(O(N\log N)\). Intuitivamente, los valores pequeños de \(u\) quedan limitados por la condición \(uv<N\), mientras que los grandes quedan limitados por la cota lineal \(v<3u\); la parte armónica de la suma es la que produce el logaritmo.
El uso de memoria es \(O(N)\), porque la estructura dominante es el arreglo de contadores para los valores \(0\) a \(N-1\). No hacen falta tablas auxiliares grandes.
我们要求出有多少个整数 \(n \lt 10^6\) 恰好有十种表示方式满足
$$x^2-y^2-z^2=n,$$
其中 \(x\)、\(y\)、\(z\) 是处于同一等差数列中的正整数。由于三者必须是同一个等差数列里的连续三项，这个三元组并不是任意独立变化的；一旦知道中项和公差，整个三元组就唯一确定了。
真正有效的做法不是直接枚举三元组，而是把这个二次表达式改写成一个带约束的因子分解问题。这样以后，问题就从“找所有三元组”转变成“统计满足条件的有序因子对”。
三份实现都建立在同一个精确等价变形之上：每一个合法解，都与 \(n\) 的一个有序因子对 \((u,v)\) 一一对应，而这个因子对必须同时满足一个模 \(4\) 的同余条件和一个来自正性要求的不等式条件。
如果 \(x\)、\(y\)、\(z\) 在等差数列中，那么可以写成
$$x=a+d,\qquad y=a,\qquad z=a-d,$$
其中 \(a \ge 1\)、\(d \ge 1\) 都是整数。由于 \(z\) 必须为正，所以立刻得到 \(a>d\)。
把这个表示代入原式，得到
$$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a).$$
这说明每个解本质上都由两个对象决定：中项 \(a\) 和量 \(4d-a\)。
定义
$$u=a,\qquad v=4d-a.$$
那么公式就变成了非常简单的形式
$$n=uv.$$
这正是代码按乘积计数而不是反复展开平方项的原因。等差数列的结构并没有消失，而是被压缩进了 \((u,v)\) 所必须满足的条件里。
因为 \(u+v=a+(4d-a)=4d\)，所以必有
$$u+v\equiv 0 \pmod 4.$$
另一方面，\(z=a-d>0\) 意味着 \(d<a\)。把 \(d=(u+v)/4\) 代回去，就得到
$$\frac{u+v}{4}<u \qquad\Longleftrightarrow\qquad v<3u.$$
因此，每个合法解都会产生一个满足下列条件的有序因子对：
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
这个对应关系不仅是必要条件，而且是充分条件。设 \(u\)、\(v\) 是正整数，并满足
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
定义
$$a=u,\qquad d=\frac{u+v}{4}.$$
由于 \(u+v\equiv 0 \pmod 4\)，所以 \(d\) 一定是整数。此时
$$z=a-d=u-\frac{u+v}{4}=\frac{3u-v}{4}>0,$$
因此得到的三元组确实全部为正，并且
$$x=a+d,\qquad y=a,\qquad z=a-d$$
显然构成等差数列。再看原表达式：
$$a(4d-a)=u\bigl((u+v)-u\bigr)=uv=n.$$
所以，\(n\) 的表示个数，恰好等于满足上述两条约束的有序因子对 \((u,v)\) 的个数。这就是实现真正统计的数学对象。
\(27\) 的正因子有序对为
$$ (1,27),\ (3,9),\ (9,3),\ (27,1). $$
现在依次套用两层筛选。
同余条件 \(u+v\equiv 0 \pmod 4\) 对这四对都成立，因为它们的和分别是 \(28\) 或 \(12\)。接着检查不等式 \(v<3u\)，\((1,27)\) 和 \((3,9)\) 会被排除，于是只剩下
$$ (9,3)\quad\text{和}\quad(27,1). $$
它们分别对应
$$a=9,\ d=3 \Rightarrow (x,y,z)=(12,9,6),$$
以及
$$a=27,\ d=7 \Rightarrow (x,y,z)=(34,27,20).$$
这两个三元组都满足 \(x^2-y^2-z^2=27\)。因此，\(27\) 恰好有两种合法表示。
设上界为 \(N\)。我们只关心那些满足 \(uv<N\) 的乘积。固定 \(u\) 之后，可行的 \(v\) 必须同时满足三条条件：
$$v\equiv -u \pmod 4,$$
$$1\le v\le \left\lfloor\frac{N-1}{u}\right\rfloor,$$
$$v\le 3u-1.$$
这意味着，对每一个固定的 \(u\)，所有合法的 \(v\) 正好构成一个公差为 \(4\) 的等差序列。它从满足正确余数类的最小正整数开始，到
$$\min\left(3u-1,\left\lfloor\frac{N-1}{u}\right\rfloor\right)$$
为止。每找到一个这样的因子对，就给乘积 \(n=uv\) 的计数加一。全部处理完以后，只要统计计数恰好等于 \(10\) 的那些 \(n\) 即可。
C++、Python 和 Java 的实现都会先建立一个按 \(n\) 索引的计数数组。然后枚举第一个因子，从 \(1\) 一直到小于上界的所有正整数。对于每个这样的值，程序会先算出第二个因子的上限：一方面它必须满足乘积约束 \(uv<10^6\)，另一方面还必须满足正性所带来的 \(v<3u\) 约束。
接下来，实现会找到满足同余类 \(v\equiv -u\pmod 4\) 的最小正整数 \(v\)。之后每次把 \(v\) 增加 \(4\)，因此遍历到的每个值都会自动满足 \(u+v\equiv 0\pmod 4\)。每访问到一个合法因子对，就把对应乘积 \(uv\) 的计数加一。
筛法结束以后，剩下的工作只是线性扫描整个计数数组。凡是计数恰好为 \(10\) 的下标，都对答案贡献 \(1\)。
三份实现采用的是完全相同的数学结构和迭代方式。其中一份实现还带有一个小型内建校验：在较小范围 \(n \lt 10000\) 下，满足条件的数应该有 \(45\) 个，这可以作为求解正式范围之前的快速自检。
令上界为 \(N\)，这里 \(N=10^6\)。对一个固定的第一因子 \(u\)，被测试的第二因子个数与
$$1+\frac{1}{4}\min\left(3u,\frac{N}{u}\right)$$
成正比。把它对所有 \(u\) 求和，就得到总时间复杂度 \(O(N\log N)\)。直观地说，小的 \(u\) 主要受乘积上界 \(uv<N\) 限制，而大的 \(u\) 则主要受线性约束 \(v<3u\) 限制；求和时出现的调和项正是对数因子的来源。
空间复杂度是 \(O(N)\)，因为最主要的数据结构就是保存 \(0\) 到 \(N-1\) 所有计数的数组，不需要额外的大型辅助表。
Нужно определить, сколько целых чисел \(n \lt 10^6\) имеют ровно десять представлений вида
$$x^2-y^2-z^2=n,$$
где \(x\), \(y\) и \(z\) являются положительными целыми числами, образующими арифметическую прогрессию. Поскольку это три последовательных члена одной прогрессии, задача фактически определяется средним членом и общей разностью.
Ключевой ход состоит в том, чтобы превратить квадратное выражение в задачу о разложении на множители с дополнительными условиями. После этого уже не нужно перебирать тройки напрямую: достаточно считать допустимые упорядоченные пары множителей.
Все реализации используют одно точное преобразование: каждому допустимому решению соответствует ровно одна упорядоченная пара множителей \((u,v)\) числа \(n\), удовлетворяющая условию сравнения по модулю \(4\) и неравенству, вытекающему из положительности.
Если \(x\), \(y\) и \(z\) находятся в арифметической прогрессии, можно записать
$$x=a+d,\qquad y=a,\qquad z=a-d,$$
где \(a \ge 1\) и \(d \ge 1\) - целые числа. Условие \(z>0\) сразу дает \(a>d\).
Подстановка в исходное выражение дает
$$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a).$$
Значит, каждое решение кодируется средним членом \(a\) и величиной \(4d-a\).
Введем обозначения
$$u=a,\qquad v=4d-a.$$
Тогда формула упрощается до
$$n=uv.$$
Именно поэтому код считает произведения, а не разворачивает квадратное выражение заново. Условие арифметической прогрессии никуда не исчезает; оно превращается в ограничения на \((u,v)\).
Поскольку \(u+v=a+(4d-a)=4d\), получаем
$$u+v\equiv 0 \pmod 4.$$
Кроме того, из \(z=a-d>0\) следует \(d<a\). Если подставить \(d=(u+v)/4\), получаем
$$\frac{u+v}{4}<u \qquad\Longleftrightarrow\qquad v<3u.$$
Следовательно, каждое допустимое решение порождает упорядоченную пару множителей \((u,v)\), для которой верно
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
Соответствие работает и в обратную сторону. Пусть \(u\) и \(v\) - положительные целые числа, удовлетворяющие
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
Положим
$$a=u,\qquad d=\frac{u+v}{4}.$$
Из условия сравнения по модулю следует, что \(d\) - целое число. Тогда
$$z=a-d=u-\frac{u+v}{4}=\frac{3u-v}{4}>0,$$
значит, тройка действительно положительна, и
$$x=a+d,\qquad y=a,\qquad z=a-d$$
образует арифметическую прогрессию. Наконец,
$$a(4d-a)=u\bigl((u+v)-u\bigr)=uv=n.$$
Итак, число представлений \(n\) в точности равно числу упорядоченных пар \((u,v)\), удовлетворяющих этим условиям. Именно этот объект и подсчитывают реализации.
Положительные пары множителей числа \(27\) таковы:
$$ (1,27),\ (3,9),\ (9,3),\ (27,1). $$
Теперь применим два фильтра.
Сравнение \(u+v\equiv 0 \pmod 4\) выполняется для всех четырех пар, потому что суммы равны \(28\) или \(12\). Неравенство \(v<3u\) отбрасывает \((1,27)\) и \((3,9)\), поэтому остаются
$$ (9,3)\quad\text{и}\quad(27,1). $$
Они дают
$$a=9,\ d=3 \Rightarrow (x,y,z)=(12,9,6),$$
и
$$a=27,\ d=7 \Rightarrow (x,y,z)=(34,27,20).$$
Обе тройки удовлетворяют равенству \(x^2-y^2-z^2=27\). Значит, у числа \(27\) ровно два допустимых представления.
Пусть \(N\) - верхняя граница. Нас интересуют только произведения \(uv<N\). Если \(u\) фиксировано, то допустимые значения \(v\) должны одновременно удовлетворять трем условиям:
$$v\equiv -u \pmod 4,$$
$$1\le v\le \left\lfloor\frac{N-1}{u}\right\rfloor,$$
$$v\le 3u-1.$$
Следовательно, для каждого \(u\) все возможные значения \(v\) образуют одну арифметическую прогрессию с шагом \(4\). Она начинается с наименьшего положительного числа в нужном классе вычетов и заканчивается на
$$\min\left(3u-1,\left\lfloor\frac{N-1}{u}\right\rfloor\right).$$
Каждая допустимая пара добавляет одно представление к счетчику числа \(n=uv\). После обработки всех значений \(u\) ответом будет количество индексов, у которых счетчик равен \(10\).
Реализации на C++, Python и Java создают массив счетчиков, индексированный по значению \(n\). Затем они перебирают первый множитель от \(1\) до границы. Для каждого значения вычисляется максимально возможный второй множитель, одновременно удовлетворяющий ограничению на произведение \(uv<10^6\) и ограничению положительности \(v<3u\).
После этого реализация находит наименьший положительный второй множитель в нужном классе вычетов \(v\equiv -u\pmod 4\). Далее цикл идет с шагом \(4\), так что каждое посещенное значение автоматически удовлетворяет условию \(u+v\equiv 0\pmod 4\). Для каждой такой пары увеличивается счетчик произведения \(uv\).
Когда сито построено, остается один линейный проход по массиву счетчиков. Каждый индекс, у которого счетчик равен ровно \(10\), добавляет единицу к итоговому количеству.
Все три реализации используют одну и ту же математику и один и тот же шаблон перебора. В одной из них также есть небольшой встроенный контроль: для границы \(n \lt 10000\) правильное число подходящих значений равно \(45\).
Обозначим верхнюю границу через \(N\); здесь \(N=10^6\). Для фиксированного первого множителя \(u\) число проверяемых вторых множителей пропорционально величине
$$1+\frac{1}{4}\min\left(3u,\frac{N}{u}\right).$$
Суммирование по всем \(u\) дает общую сложность \(O(N\log N)\). Интуитивно малые значения \(u\) ограничиваются условием \(uv<N\), а большие - линейным ограничением \(v<3u\); логарифм возникает из гармонической части этой суммы.
Потребление памяти равно \(O(N)\), потому что основной структурой данных является массив счетчиков для значений от \(0\) до \(N-1\). Крупных вспомогательных таблиц не требуется.
المطلوب هو عدّ قيم \(n \lt 10^6\) التي تملك بالضبط عشرة تمثيلات من الصورة
$$x^2-y^2-z^2=n,$$
بحيث تكون \(x\) و\(y\) و\(z\) أعدادًا صحيحة موجبة تقع في متتالية حسابية. وبما أن هذه الأعداد هي ثلاث حدود متتالية في متتالية واحدة، فإن الثلاثي يتحدد بالكامل إذا عرفنا الحد الأوسط والفرق المشترك.
الفكرة الحاسمة ليست في تعداد كل الثلاثيات مباشرة، بل في تحويل التعبير التربيعي إلى مسألة تحليل إلى عوامل مع شروط إضافية. بعد هذا التحويل يصبح المطلوب هو عدّ أزواج العوامل المرتبة التي تحقق الشروط.
تعتمد جميع التطبيقات على إعادة صياغة دقيقة واحدة: كل حل صالح يقابل زوجًا مرتبًا \((u,v)\) من عوامل \(n\)، ويجب أن يحقق هذا الزوج شرط توافق بترديد \(4\) بالإضافة إلى متراجحة ناتجة عن شرط الإيجابية.
إذا كانت \(x\) و\(y\) و\(z\) في متتالية حسابية، فيمكن كتابتها على الصورة
$$x=a+d,\qquad y=a,\qquad z=a-d,$$
حيث \(a \ge 1\) و\(d \ge 1\) عددان صحيحان. ومن الشرط \(z>0\) نحصل فورًا على \(a>d\).
بالتعويض في التعبير الأصلي نحصل على
$$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a).$$
وهكذا يصبح كل حل ممثلًا بحدين طبيعيين: الحد الأوسط \(a\) والكمية \(4d-a\).
لنعرّف
$$u=a,\qquad v=4d-a.$$
عندئذ تختزل الصيغة إلى
$$n=uv.$$
ولهذا السبب تعدّ الشيفرات القيم على مستوى حاصل الضرب بدل إعادة توسيع الحدود التربيعية في كل مرة. شرط المتتالية الحسابية لم يختف، بل انتقل إلى قيود مفروضة على \((u,v)\).
بما أن \(u+v=a+(4d-a)=4d\)، فهذا يعطي
$$u+v\equiv 0 \pmod 4.$$
كذلك فإن \(z=a-d>0\) يعني \(d<a\). وباستخدام \(d=(u+v)/4\) نحصل على
$$\frac{u+v}{4}<u \qquad\Longleftrightarrow\qquad v<3u.$$
إذن كل حل صالح يولد زوجًا مرتبًا من العوامل يحقق
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u.$$
هذا الارتباط يعمل بالعكس كذلك. إذا كان \(u\) و\(v\) عددين صحيحين موجبين ويحققان
$$uv=n,\qquad u+v\equiv 0 \pmod 4,\qquad v<3u,$$
فنعرّف
$$a=u,\qquad d=\frac{u+v}{4}.$$
شرط التوافق يضمن أن \(d\) عدد صحيح. ثم نجد أن
$$z=a-d=u-\frac{u+v}{4}=\frac{3u-v}{4}>0,$$
ومن ثم يكون الثلاثي موجبًا فعلًا، كما أن
$$x=a+d,\qquad y=a,\qquad z=a-d$$
يشكل متتالية حسابية. وأخيرًا
$$a(4d-a)=u\bigl((u+v)-u\bigr)=uv=n.$$
وبالتالي فإن عدد تمثيلات \(n\) يساوي تمامًا عدد أزواج العوامل المرتبة \((u,v)\) التي تحقق هذه الشروط. وهذا هو الكائن الرياضي الحقيقي الذي تعدّه التطبيقات.
أزواج العوامل الموجبة المرتبة للعدد \(27\) هي
$$ (1,27),\ (3,9),\ (9,3),\ (27,1). $$
نطبق الآن المرشحين الأساسيين.
الشرط \(u+v\equiv 0 \pmod 4\) يتحقق في الأزواج الأربعة كلها لأن المجاميع هي \(28\) أو \(12\). أما المتراجحة \(v<3u\) فتستبعد الزوجين \((1,27)\) و\((3,9)\)، فلا يبقى إلا
$$ (9,3),\ (27,1). $$
وهما يقابِلان
$$a=9,\ d=3 \Rightarrow (x,y,z)=(12,9,6),$$
و
$$a=27,\ d=7 \Rightarrow (x,y,z)=(34,27,20).$$
وكلا الثلاثيين يحقق \(x^2-y^2-z^2=27\). إذن للعدد \(27\) تمثيلان صالحان بالضبط.
لنرمز إلى الحد الأعلى بـ \(N\). نحن نهتم فقط بالجداءات التي تحقق \(uv<N\). وعند تثبيت \(u\)، يجب أن يحقق \(v\) الشروط الثلاثة التالية معًا:
$$v\equiv -u \pmod 4,$$
$$1\le v\le \left\lfloor\frac{N-1}{u}\right\rfloor,$$
$$v\le 3u-1.$$
وهذا يعني أن القيم المسموح بها لـ \(v\) من أجل كل \(u\) تشكل متتالية حسابية واحدة فرقها \(4\). تبدأ من أصغر قيمة موجبة في فئة الباقي الصحيحة، وتنتهي عند
$$\min\left(3u-1,\left\lfloor\frac{N-1}{u}\right\rfloor\right).$$
كل زوج صالح يضيف تمثيلًا واحدًا إلى عدّاد القيمة \(n=uv\). وبعد إنهاء جميع قيم \(u\)، تكون الإجابة هي عدد القيم التي أصبح عدّادها مساويًا تمامًا لـ \(10\).
تقوم تطبيقات C++ وPython وJava بإنشاء مصفوفة عدادات مفهرسة بالقيمة \(n\). بعد ذلك تمر على العامل الأول من \(1\) حتى أقل من الحد الأعلى. ولكل قيمة تحسب أكبر عامل ثانٍ ممكن وفق قيد الجداء \(uv<10^6\) وقيد الإيجابية \(v<3u\).
ثم تبحث التنفيذات عن أصغر عامل ثانٍ موجب يحقق فئة الباقي الصحيحة \(v\equiv -u\pmod 4\). وبعد ذلك تتحرك بخطوة مقدارها \(4\)، ولذلك فإن كل قيمة يتم الوصول إليها تحقق تلقائيًا الشرط \(u+v\equiv 0\pmod 4\). وكل زوج تتم زيارته يزيد عدّاد الجداء \(uv\) بمقدار واحد.
بعد انتهاء المنخل، لا يبقى إلا مسح خطي لمصفوفة العدادات. كل موضع يكون عدّاده مساويًا تمامًا لـ \(10\) يضيف واحدًا إلى الناتج النهائي.
التطبيقات الثلاثة تستخدم الرياضيات نفسها ونمط التكرار نفسه. وأحدها يحتوي كذلك على فحص صغير مدمج: عندما يكون الحد \(n \lt 10000\)، يجب أن يكون عدد القيم المستهدفة هو \(45\).
ليكن \(N\) هو الحد الأعلى، وهنا \(N=10^6\). بالنسبة إلى عامل أول ثابت \(u\)، فإن عدد العوامل الثانية التي يتم اختبارها يتناسب مع
$$1+\frac{1}{4}\min\left(3u,\frac{N}{u}\right).$$
وبجمع ذلك على جميع قيم \(u\) نحصل على تعقيد زمني من الرتبة \(O(N\log N)\). بصورة حدسية، تكون القيم الصغيرة لـ \(u\) مقيدة بشرط الجداء \(uv<N\)، بينما تكون القيم الكبيرة مقيدة أكثر بالحد الخطي \(v<3u\)، والجزء التوافقي من هذا الجمع هو الذي ينتج عامل اللوغاريتم.
أما الذاكرة المستعملة فهي \(O(N)\)، لأن البنية الأساسية المسيطرة هي مصفوفة العدادات للقيم من \(0\) إلى \(N-1\)، ولا توجد حاجة إلى جداول مساعدة كبيرة.