We must count positive-integer matrices
$$A \in M_2(\mathbb{Z}_{>0})$$
with
$$\operatorname{tr}(A) \lt N$$
such that \(A\) has at least two distinct positive-integer square roots. In other words, there exist two different matrices \(B_1\) and \(B_2\) with positive integer entries for which
$$B_1^2 = A = B_2^2.$$
A direct search over all possible matrices is far too expensive when \(N = 10^7\), so the solution reorganizes the problem around the arithmetic structure shared by two different roots of the same matrix.
Let
$$B_1=\begin{pmatrix}a & b\\ c & d\end{pmatrix},\qquad B_2=\begin{pmatrix}e & f\\ g & h\end{pmatrix},$$
where all eight variables are positive integers and \(B_1 \ne B_2\). Squaring both matrices gives
$$B_1^2=\begin{pmatrix}a^2+bc & b(a+d)\\ c(a+d) & d^2+bc\end{pmatrix},$$
$$B_2^2=\begin{pmatrix}e^2+fg & f(e+h)\\ g(e+h) & h^2+fg\end{pmatrix}.$$
Because both squares are the same matrix \(A\), their corresponding entries must agree. Introduce the trace-like and difference-like quantities
$$t_1=a+d,\qquad t_2=e+h,\qquad r_1=a-d,\qquad r_2=e-h.$$
Then the off-diagonal entries satisfy
$$b\,t_1=f\,t_2=A_{12},\qquad c\,t_1=g\,t_2=A_{21},$$
and subtracting the two diagonal entries in each square gives
$$a^2-d^2=e^2-h^2 \iff r_1 t_1=r_2 t_2.$$
If \(t_1=t_2\), then the off-diagonal equalities force \(b=f\) and \(c=g\), and the relation \(r_1 t_1=r_2 t_2\) forces \(r_1=r_2\), hence \(a=e\) and \(d=h\). So distinct roots must have different trace sums. We may therefore assume
$$t_1 \lt t_2.$$
Write the ratio \(t_1:t_2\) in lowest terms:
$$t_1=qn,\qquad t_2=pn,\qquad p \gt q \ge 1,\qquad \gcd(p,q)=1,\qquad n\ge 1.$$
Now use \(r_1 t_1=r_2 t_2\). Since \(q r_1 = p r_2\) and \(p,q\) are coprime, there exists an integer \(m\) such that
$$r_1=pm,\qquad r_2=qm.$$
Therefore the diagonal entries of the two roots are completely determined by \(p,q,n,m\):
$$a=\frac{qn+pm}{2},\qquad d=\frac{qn-pm}{2},$$
$$e=\frac{pn+qm}{2},\qquad h=\frac{pn-qm}{2}.$$
The off-diagonal equalities show that both \(A_{12}\) and \(A_{21}\) are divisible by both \(qn\) and \(pn\). Since \(\gcd(p,q)=1\), they are divisible by \(pqn\). So we may write
$$A_{12}=pqn\,u,\qquad A_{21}=pqn\,v,\qquad u,v\in\mathbb{Z}_{>0}.$$
Substituting back gives the individual off-diagonal entries of the two roots:
$$b=pu,\qquad c=pv,\qquad f=qu,\qquad g=qv.$$
The entries \(a,d,e,h\) must be positive integers. Positivity gives
$$qn \gt p|m|,$$
or equivalently
$$|m| \lt \frac{qn}{p}.$$
Integrality imposes parity conditions, because each diagonal entry is a half-integer expression. We need \(qn \pm pm\) and \(pn \pm qm\) to be even. Since \(p\) and \(q\) are coprime, this reduces to two cases:
If \(p\) and \(q\) have opposite parity, then both \(n\) and \(m\) must be even.
If \(p\) and \(q\) are both odd, then \(m \equiv n \pmod{2}\).
These are exactly the parity filters used by the implementations when they enumerate valid values of \(m\).
Set
$$\ell=uv.$$
Now compare the upper-left entries of \(B_1^2\) and \(B_2^2\):
$$\frac{(qn+pm)^2}{4}+p^2\ell=\frac{(pn+qm)^2}{4}+q^2\ell.$$
After expanding and simplifying, the mixed terms cancel and we obtain
$$4\ell=n^2-m^2.$$
Hence
$$\boxed{\ell=\frac{n^2-m^2}{4}}.$$
Because \(u\) and \(v\) are positive, we need \(\ell \gt 0\), so automatically \(n^2 \gt m^2\). The same identity also makes the lower-right entries agree, so this single equation is the key Diophantine compatibility condition.
For fixed \(p,q,n,m\), the diagonal parts of both roots are fixed, and so is the common scale factor \(pqn\) in the off-diagonal entries of \(A\). The only remaining freedom is to factor \(\ell\) as
$$\ell=uv,\qquad u,v\in\mathbb{Z}_{>0}.$$
Each positive divisor \(u\mid \ell\) determines exactly one ordered pair
$$\left(u,\frac{\ell}{u}\right),$$
and therefore exactly one matrix \(A\). The number of such ordered factor pairs is the divisor function \(\tau(\ell)\). That is why every admissible quadruple \((p,q,n,m)\) contributes
$$\tau\!\left(\frac{n^2-m^2}{4}\right)$$
to the final count.
Using \(B_1\), we can compute the trace of \(A\):
$$\operatorname{tr}(A)=a^2+d^2+2bc.$$
Substitute \(a,d,b,c\) from the parameterization:
$$\operatorname{tr}(A)=\frac{q^2n^2+p^2m^2}{2}+2p^2\ell.$$
Now replace \(\ell\) by \(\frac{n^2-m^2}{4}\):
$$\operatorname{tr}(A)=\frac{q^2n^2+p^2m^2}{2}+\frac{p^2(n^2-m^2)}{2}=\frac{(p^2+q^2)n^2}{2}.$$
So the trace condition \(\operatorname{tr}(A)\lt N\) becomes
$$\frac{(p^2+q^2)n^2}{2} \lt N,$$
or
$$n \le \sqrt{\frac{2N-1}{p^2+q^2}}.$$
This gives the final counting formula:
$$F(N)=\sum_{\substack{p \gt q \ge 1\\ \gcd(p,q)=1}} \ \sum_{n=1}^{\left\lfloor\sqrt{\frac{2N-1}{p^2+q^2}}\right\rfloor} \ \sum_{m}\tau\!\left(\frac{n^2-m^2}{4}\right),$$
where \(m\) runs over the integers satisfying
$$|m| \lt \frac{qn}{p}$$
together with the parity conditions from the previous step. This is the exact formula used by the implementations.
Take
$$p=2,\qquad q=1,\qquad n=4,\qquad m=0.$$
Then
$$\ell=\frac{4^2-0^2}{4}=4,\qquad \operatorname{tr}(A)=\frac{(2^2+1^2)\cdot 4^2}{2}=40.$$
Since \(\tau(4)=3\), this single admissible quadruple contributes three matrices, corresponding to the factor pairs \((u,v)=(1,4),(2,2),(4,1)\). For \((u,v)=(1,4)\), the two roots are
$$\begin{pmatrix}2 & 2\\ 8 & 2\end{pmatrix},\qquad \begin{pmatrix}4 & 1\\ 4 & 4\end{pmatrix},$$
and both square to
$$\begin{pmatrix}20 & 8\\ 32 & 20\end{pmatrix}.$$
This example shows exactly how one admissible arithmetic state can generate several matrices through the divisors of \(\ell\).
The C++, Python, and Java implementations follow the same structure. They first derive an upper bound for \(\ell=\frac{n^2-m^2}{4}\). The smallest possible value of \(p^2+q^2\) is \(5\), attained at \((p,q)=(2,1)\), so \(n^2 \le \frac{2N-1}{5}\), and therefore \(\ell \le \frac{n^2}{4}\). With that bound in hand, the implementation precomputes \(\tau(x)\) for every needed \(x\) by a divisor sieve.
After the sieve, the program iterates over coprime pairs \((p,q)\) with \(p \gt q\), computes the admissible range of \(n\) from the trace bound, and then scans the valid values of \(m\) respecting the positivity and parity conditions. For each admissible state it evaluates \(\ell=(n^2-m^2)/4\) and adds \(\tau(\ell)\) to the total. The implementations also verify the reduction with small checkpoints; in particular, they confirm \(F(50)=7\) and \(F(1000)=1019\), and the C++ version cross-checks the formula against direct enumeration for a small bound.
The divisor sieve up to
$$\left\lfloor \frac{1}{4}\left\lfloor \sqrt{\frac{2N-1}{5}} \right\rfloor^2 \right\rfloor$$
uses \(O(L\log L)\) time and \(O(L)\) memory, where \(L\) denotes that bound. Since \(L\) is proportional to \(N\), this is effectively \(O(N\log N)\) time and \(O(N)\) memory for the preprocessing stage.
The arithmetic enumeration over \((p,q,n,m)\) is far smaller than a brute-force search over all positive roots. Its aggregate size is also \(O(N\log N)\), so the whole method remains practical for \(N=10^7\). The crucial gain is that the program never enumerates matrices \(A\) directly; it only enumerates reduced number-theoretic states that are known to produce at least two square roots.
Gesucht ist die Anzahl positiver ganzzahliger Matrizen
$$A \in M_2(\mathbb{Z}_{>0})$$
mit
$$\operatorname{tr}(A) \lt N,$$
die mindestens zwei verschiedene positive ganzzahlige Quadratwurzeln besitzen. Es sollen also zwei unterschiedliche Matrizen \(B_1\) und \(B_2\) mit positiven ganzen Einträgen existieren, so dass
$$B_1^2=A=B_2^2.$$
Ein direktes Durchmustern aller Kandidaten ist bei \(N=10^7\) aussichtslos. Die Lösung zählt daher nicht die Matrizen \(A\) selbst, sondern beschreibt zuerst die Struktur zweier verschiedener Quadratwurzeln derselben Matrix.
Seien
$$B_1=\begin{pmatrix}a & b\\ c & d\end{pmatrix},\qquad B_2=\begin{pmatrix}e & f\\ g & h\end{pmatrix}$$
zwei verschiedene positive ganzzahlige Quadratwurzeln derselben Matrix \(A\). Dann gilt
$$B_1^2=\begin{pmatrix}a^2+bc & b(a+d)\\ c(a+d) & d^2+bc\end{pmatrix},$$
$$B_2^2=\begin{pmatrix}e^2+fg & f(e+h)\\ g(e+h) & h^2+fg\end{pmatrix}.$$
Wir führen die Größen
$$t_1=a+d,\qquad t_2=e+h,\qquad r_1=a-d,\qquad r_2=e-h$$
ein. Aus den Nebendiagonalen folgt
$$b\,t_1=f\,t_2=A_{12},\qquad c\,t_1=g\,t_2=A_{21},$$
und aus der Differenz der Diagonaleinträge
$$a^2-d^2=e^2-h^2 \iff r_1 t_1=r_2 t_2.$$
Wäre \(t_1=t_2\), dann würden die Gleichungen sofort \(b=f\), \(c=g\), \(r_1=r_2\) und damit \(a=e\), \(d=h\) erzwingen. Also müssen verschiedene Wurzeln unterschiedliche Spurensummen haben. Ohne Beschränkung der Allgemeinheit setzen wir
$$t_1 \lt t_2.$$
Schreibe das Verhältnis \(t_1:t_2\) in vollständig gekürzter Form:
$$t_1=qn,\qquad t_2=pn,\qquad p \gt q \ge 1,\qquad \gcd(p,q)=1,\qquad n\ge 1.$$
Aus \(r_1 t_1=r_2 t_2\) folgt \(q r_1 = p r_2\). Wegen \(\gcd(p,q)=1\) gibt es ein ganzzahliges \(m\) mit
$$r_1=pm,\qquad r_2=qm.$$
Damit sind die Diagonaleinträge beider Wurzeln bereits festgelegt:
$$a=\frac{qn+pm}{2},\qquad d=\frac{qn-pm}{2},$$
$$e=\frac{pn+qm}{2},\qquad h=\frac{pn-qm}{2}.$$
Die Nebendiagonalen zeigen zugleich, dass \(A_{12}\) und \(A_{21}\) sowohl durch \(qn\) als auch durch \(pn\) teilbar sind. Da \(p\) und \(q\) teilerfremd sind, sind beide Einträge Vielfache von \(pqn\). Also schreiben wir
$$A_{12}=pqn\,u,\qquad A_{21}=pqn\,v,\qquad u,v\in\mathbb{Z}_{>0}.$$
Dann ergeben sich die Nebendiagonaleinträge der Wurzeln als
$$b=pu,\qquad c=pv,\qquad f=qu,\qquad g=qv.$$
Die Einträge \(a,d,e,h\) müssen positive ganze Zahlen sein. Aus der Positivität folgt
$$qn \gt p|m|,$$
also
$$|m| \lt \frac{qn}{p}.$$
Für die Ganzzahligkeit müssen \(qn \pm pm\) und \(pn \pm qm\) gerade sein. Wegen der Teilerfremdheit von \(p\) und \(q\) bleibt genau Folgendes übrig:
Haben \(p\) und \(q\) verschiedene Parität, dann müssen \(n\) und \(m\) beide gerade sein.
Sind \(p\) und \(q\) beide ungerade, dann gilt \(m \equiv n \pmod{2}\).
Genau diese beiden Fälle implementieren die Schleifen in den Programmen.
Setze
$$\ell=uv.$$
Vergleicht man die linken oberen Einträge von \(B_1^2\) und \(B_2^2\), erhält man
$$\frac{(qn+pm)^2}{4}+p^2\ell=\frac{(pn+qm)^2}{4}+q^2\ell.$$
Nach Ausmultiplizieren heben sich die gemischten Terme weg und es bleibt
$$4\ell=n^2-m^2.$$
Somit gilt
$$\boxed{\ell=\frac{n^2-m^2}{4}}.$$
Da \(u\) und \(v\) positiv sind, muss \(\ell \gt 0\) gelten. Dieselbe Gleichung sorgt automatisch auch für die Übereinstimmung des rechten unteren Eintrags. Das ist die zentrale diofantische Bedingung des Verfahrens.
Für feste Werte \(p,q,n,m\) sind die Diagonalen der beiden Wurzeln schon vollständig bestimmt, ebenso der gemeinsame Faktor \(pqn\) in den Nebendiagonalen von \(A\). Frei bleibt nur noch die Faktorisierung
$$\ell=uv,\qquad u,v\in\mathbb{Z}_{>0}.$$
Jeder positive Teiler \(u\mid \ell\) liefert genau das geordnete Paar
$$\left(u,\frac{\ell}{u}\right),$$
also genau eine Matrix \(A\). Die Anzahl solcher geordneten Faktorisierungen ist die Teilerfunktion \(\tau(\ell)\). Deshalb trägt jedes zulässige Tupel \((p,q,n,m)\) genau
$$\tau\!\left(\frac{n^2-m^2}{4}\right)$$
zum Gesamtergebnis bei.
Mit \(B_1\) berechnet man
$$\operatorname{tr}(A)=a^2+d^2+2bc.$$
Einsetzen der Parametrisierung ergibt
$$\operatorname{tr}(A)=\frac{q^2n^2+p^2m^2}{2}+2p^2\ell.$$
Setzt man \(\ell=\frac{n^2-m^2}{4}\) ein, so vereinfacht sich das zu
$$\operatorname{tr}(A)=\frac{(p^2+q^2)n^2}{2}.$$
Die Bedingung \(\operatorname{tr}(A)\lt N\) wird also zu
$$n \le \sqrt{\frac{2N-1}{p^2+q^2}}.$$
Damit lautet die endgültige Summenformel
$$F(N)=\sum_{\substack{p \gt q \ge 1\\ \gcd(p,q)=1}} \ \sum_{n=1}^{\left\lfloor\sqrt{\frac{2N-1}{p^2+q^2}}\right\rfloor} \ \sum_{m}\tau\!\left(\frac{n^2-m^2}{4}\right),$$
wobei \(m\) alle ganzen Zahlen mit
$$|m| \lt \frac{qn}{p}$$
und den Paritätsbedingungen aus dem vorherigen Schritt durchläuft. Genau diese Formel setzen die Implementierungen um.
Nehmen wir
$$p=2,\qquad q=1,\qquad n=4,\qquad m=0.$$
Dann ist
$$\ell=\frac{4^2-0^2}{4}=4,\qquad \operatorname{tr}(A)=\frac{(2^2+1^2)\cdot 4^2}{2}=40.$$
Wegen \(\tau(4)=3\) entstehen aus diesem einen zulässigen Viererparameter genau drei Matrizen, entsprechend den Faktorpaare \((u,v)=(1,4),(2,2),(4,1)\). Für \((u,v)=(1,4)\) erhält man die beiden Wurzeln
$$\begin{pmatrix}2 & 2\\ 8 & 2\end{pmatrix},\qquad \begin{pmatrix}4 & 1\\ 4 & 4\end{pmatrix},$$
und beide liefern dieselbe Matrix
$$\begin{pmatrix}20 & 8\\ 32 & 20\end{pmatrix}.$$
So wird sichtbar, warum die Divisoren von \(\ell\) direkt in die Zählung eingehen.
Die C++-, Python- und Java-Implementierungen benutzen denselben Aufbau. Zuerst wird eine obere Schranke für \(\ell=\frac{n^2-m^2}{4}\) hergeleitet. Der kleinste mögliche Wert von \(p^2+q^2\) ist \(5\) bei \((p,q)=(2,1)\), also gilt \(n^2 \le \frac{2N-1}{5}\) und damit \(\ell \le \frac{n^2}{4}\). Bis zu dieser Schranke wird \(\tau(x)\) per Teilersieb für alle benötigten \(x\) vorab berechnet.
Danach laufen die Programme über teilerfremde Paare \((p,q)\) mit \(p \gt q\), bestimmen die zulässigen \(n\) über die Spurenschranke und durchlaufen dann alle zulässigen \(m\), die Positivität und Parität erfüllen. Für jeden gültigen Zustand wird \(\ell=(n^2-m^2)/4\) berechnet und \(\tau(\ell)\) zum Ergebnis addiert. Zusätzlich prüfen die Implementierungen kleine Kontrollwerte; insbesondere gilt \(F(50)=7\) und \(F(1000)=1019\), und die C++-Version vergleicht die Formel für eine kleine Schranke auch mit direkter Enumeration.
Das Teilersieb bis
$$\left\lfloor \frac{1}{4}\left\lfloor \sqrt{\frac{2N-1}{5}} \right\rfloor^2 \right\rfloor$$
benötigt \(O(L\log L)\) Zeit und \(O(L)\) Speicher, wobei \(L\) diese Schranke bezeichnet. Da \(L\) proportional zu \(N\) ist, entspricht das effektiv \(O(N\log N)\) Zeit und \(O(N)\) Speicher im Vorverarbeitungsschritt.
Auch die eigentliche Enumeration über \((p,q,n,m)\) liegt insgesamt in derselben Größenordnung und ist sehr viel kleiner als ein naiver Suchraum über alle positiven Wurzeln. Der entscheidende Punkt ist, dass nicht Matrizen \(A\) selbst durchsucht werden, sondern nur arithmetische Zustände, die bereits garantiert zu mindestens zwei Quadratwurzeln führen.
Aranan şey,
$$A \in M_2(\mathbb{Z}_{>0})$$
olmak üzere
$$\operatorname{tr}(A) \lt N$$
koşulunu sağlayan ve en az iki farklı pozitif tamsayı karekökü bulunan tüm \(2\times2\) matrislerin sayısıdır. Yani pozitif tamsayılı ve birbirinden farklı iki matris \(B_1\) ve \(B_2\) için
$$B_1^2=A=B_2^2$$
olmalıdır. \(N=10^7\) için doğrudan tüm adayları taramak mümkün olmadığından çözüm, aynı matrise giden iki farklı karekökün ortak aritmetik yapısını sayar.
Şöyle yazalım:
$$B_1=\begin{pmatrix}a & b\\ c & d\end{pmatrix},\qquad B_2=\begin{pmatrix}e & f\\ g & h\end{pmatrix}.$$
Tüm değişkenler pozitif tamsayı ve \(B_1 \ne B_2\). Karelerini açarsak
$$B_1^2=\begin{pmatrix}a^2+bc & b(a+d)\\ c(a+d) & d^2+bc\end{pmatrix},$$
$$B_2^2=\begin{pmatrix}e^2+fg & f(e+h)\\ g(e+h) & h^2+fg\end{pmatrix}.$$
Aynı matrisi verdikleri için karşılık gelen girişler eşit olmalıdır. Bu yüzden
$$t_1=a+d,\qquad t_2=e+h,\qquad r_1=a-d,\qquad r_2=e-h$$
tanımlarını yapalım. O zaman köşegen dışı girişlerden
$$b\,t_1=f\,t_2=A_{12},\qquad c\,t_1=g\,t_2=A_{21},$$
ve köşegen girişlerinin farkından
$$a^2-d^2=e^2-h^2 \iff r_1 t_1=r_2 t_2$$
elde edilir. Eğer \(t_1=t_2\) olsaydı, ilk eşitlikler \(b=f\) ve \(c=g\), sonuncusu da \(r_1=r_2\) verirdi; dolayısıyla \(a=e\) ve \(d=h\) olur, yani kökler aynı çıkardı. Demek ki farklı kökler için
$$t_1 \lt t_2$$
varsayımı yapılabilir.
\(t_1:t_2\) oranını sade biçimde yazalım:
$$t_1=qn,\qquad t_2=pn,\qquad p \gt q \ge 1,\qquad \gcd(p,q)=1,\qquad n\ge 1.$$
\(r_1 t_1=r_2 t_2\) bağıntısından
$$q r_1 = p r_2$$
gelir. \(p\) ile \(q\) aralarında asal olduğundan bir \(m\in\mathbb{Z}\) için
$$r_1=pm,\qquad r_2=qm$$
yazabiliriz. Böylece köklerin köşegen girişleri tamamen belirlenir:
$$a=\frac{qn+pm}{2},\qquad d=\frac{qn-pm}{2},$$
$$e=\frac{pn+qm}{2},\qquad h=\frac{pn-qm}{2}.$$
Köşegen dışı girişler için de \(A_{12}\) ve \(A_{21}\), hem \(qn\)'e hem \(pn\)'e bölünür. \(\gcd(p,q)=1\) olduğundan bunlar \(pqn\)'in katıdır. Bu yüzden
$$A_{12}=pqn\,u,\qquad A_{21}=pqn\,v,\qquad u,v\in\mathbb{Z}_{>0}$$
şeklinde yazılır ve buradan
$$b=pu,\qquad c=pv,\qquad f=qu,\qquad g=qv$$
çıkar.
\(a,d,e,h\) hem pozitif hem de tamsayı olmalıdır. Pozitiflikten
$$qn \gt p|m|$$
yani
$$|m| \lt \frac{qn}{p}$$
elde edilir. Tamsayılık için \(qn \pm pm\) ve \(pn \pm qm\) ifadelerinin çift olması gerekir. \(p\) ile \(q\) aralarında asal olduğundan durum iki basit kurala iner:
\(p\) ile \(q\) farklı paritedeyse hem \(n\) hem de \(m\) çift olmalıdır.
\(p\) ile \(q\) ikisi de tekse \(m \equiv n \pmod{2}\) olmalıdır.
Uygulamadaki parite filtreleri tam olarak bu matematiksel koşulları kodlar.
Şimdi
$$\ell=uv$$
tanımını yapalım. \(B_1^2\) ile \(B_2^2\)'nin sol üst girişlerini eşitleyince
$$\frac{(qn+pm)^2}{4}+p^2\ell=\frac{(pn+qm)^2}{4}+q^2\ell$$
elde edilir. Açıp sadeleştirince çapraz terimler yok olur ve
$$4\ell=n^2-m^2$$
kalır. Dolayısıyla
$$\boxed{\ell=\frac{n^2-m^2}{4}}.$$
\(u\) ve \(v\) pozitif olduğundan \(\ell \gt 0\) gerekir. Aynı özdeşlik sağ alt girişin eşitliğini de otomatik olarak sağlar; dolayısıyla bu, problemin ana diofantik bağıntısıdır.
\(p,q,n,m\) sabitlenince köklerin köşegen girişleri ve \(A\)'nın köşegen dışı girişlerindeki ortak \(pqn\) ölçeği de sabitlenmiş olur. Geriye sadece
$$\ell=uv,\qquad u,v\in\mathbb{Z}_{>0}$$
şeklindeki çarpanlara ayırma kalır. \(\ell\)'nin her pozitif böleni \(u\), tek bir sıralı çift verir:
$$\left(u,\frac{\ell}{u}\right).$$
Bu da tek bir matris \(A\) üretir. Böyle sıralı çarpan çiftlerinin sayısı tam olarak \(\tau(\ell)\) olduğundan, her geçerli \((p,q,n,m)\) dörtlüsü toplam sayıya
$$\tau\!\left(\frac{n^2-m^2}{4}\right)$$
kadar katkı yapar.
\(B_1\) üzerinden izi hesaplayalım:
$$\operatorname{tr}(A)=a^2+d^2+2bc.$$
Parametrizasyonu yerleştirince
$$\operatorname{tr}(A)=\frac{q^2n^2+p^2m^2}{2}+2p^2\ell$$
olur. \(\ell=\frac{n^2-m^2}{4}\) yazınca sadeleşme gerçekleşir:
$$\operatorname{tr}(A)=\frac{(p^2+q^2)n^2}{2}.$$
Böylece \(\operatorname{tr}(A)\lt N\) koşulu
$$n \le \sqrt{\frac{2N-1}{p^2+q^2}}$$
şekline döner. Sonuç olarak sayım formülü
$$F(N)=\sum_{\substack{p \gt q \ge 1\\ \gcd(p,q)=1}} \ \sum_{n=1}^{\left\lfloor\sqrt{\frac{2N-1}{p^2+q^2}}\right\rfloor} \ \sum_{m}\tau\!\left(\frac{n^2-m^2}{4}\right)$$
olur. Burada \(m\),
$$|m| \lt \frac{qn}{p}$$
koşulunu ve bir önceki adımdaki parite şartlarını sağlayan tüm tamsayılar üzerinde dolaşır. Uygulamalar tam olarak bu formülü toplar.
Şunu alalım:
$$p=2,\qquad q=1,\qquad n=4,\qquad m=0.$$
O zaman
$$\ell=\frac{4^2-0^2}{4}=4,\qquad \operatorname{tr}(A)=\frac{(2^2+1^2)\cdot 4^2}{2}=40.$$
\(\tau(4)=3\) olduğu için bu tek aritmetik durum üç matris üretir; bunlar \((u,v)=(1,4),(2,2),(4,1)\) çiftlerine karşılık gelir. \((u,v)=(1,4)\) için iki kök
$$\begin{pmatrix}2 & 2\\ 8 & 2\end{pmatrix},\qquad \begin{pmatrix}4 & 1\\ 4 & 4\end{pmatrix}$$
olur ve ikisinin karesi de
$$\begin{pmatrix}20 & 8\\ 32 & 20\end{pmatrix}$$
matrisidir. Böylece \(\ell\)'nin bölenlerinin neden doğrudan katkı sayısını verdiği somut biçimde görülür.
C++, Python ve Java uygulamaları aynı mantığı izler. Önce \(\ell=\frac{n^2-m^2}{4}\) için güvenli bir üst sınır çıkarılır. \(p^2+q^2\)'nin alabileceği en küçük değer \((2,1)\) çifti için \(5\) olduğundan \(n^2 \le \frac{2N-1}{5}\) ve dolayısıyla \(\ell \le \frac{n^2}{4}\) olur. Ardından bu üst sınıra kadar tüm \(\tau(x)\) değerleri bir bölen eleği ile önceden hesaplanır.
Sonraki aşamada program, \(p \gt q\) ve \(\gcd(p,q)=1\) koşullarını sağlayan çiftleri gezer; iz sınırından uygun \(n\) aralığını bulur; sonra da pozitiflik ve parite kurallarını sağlayan \(m\) değerlerini dolaşır. Her geçerli durumda \(\ell=(n^2-m^2)/4\) hesaplanır ve \(\tau(\ell)\) toplamına eklenir. Uygulamalar ayrıca küçük kontrol değerlerini de doğrular; özellikle \(F(50)=7\) ve \(F(1000)=1019\) eşitlikleri sağlanır, C++ sürümü ise küçük bir sınırda formülü doğrudan kaba kuvvet sayımıyla da karşılaştırır.
Şu sınıra kadar yapılan bölen eleği
$$\left\lfloor \frac{1}{4}\left\lfloor \sqrt{\frac{2N-1}{5}} \right\rfloor^2 \right\rfloor$$
için \(O(L\log L)\) zaman ve \(O(L)\) bellek gerekir; burada \(L\) bu sınırı temsil eder. \(L\), \(N\) ile doğrusal mertebede büyüdüğü için ön işlem etkili olarak \(O(N\log N)\) zaman ve \(O(N)\) bellektir.
\((p,q,n,m)\) durumlarının taranması da toplamda aynı mertebede kalır ve tüm pozitif kökleri doğrudan denemekten çok daha küçüktür. Kritik kazanç şudur: program matrisleri doğrudan üretmez, yalnızca en az iki karekök verdiği zaten bilinen sayı kuramsal durumları sayar.
Debemos contar las matrices de enteros positivos
$$A \in M_2(\mathbb{Z}_{>0})$$
que cumplen
$$\operatorname{tr}(A) \lt N$$
y que tienen al menos dos raíces cuadradas distintas con entradas enteras positivas. Es decir, existen dos matrices diferentes \(B_1\) y \(B_2\) tales que
$$B_1^2=A=B_2^2.$$
Una búsqueda directa sobre todas las matrices posibles es inviable para \(N=10^7\), así que la solución se apoya en la estructura aritmética común a dos raíces distintas de una misma matriz.
Sean
$$B_1=\begin{pmatrix}a & b\\ c & d\end{pmatrix},\qquad B_2=\begin{pmatrix}e & f\\ g & h\end{pmatrix}$$
dos raíces cuadradas distintas con entradas positivas. Al elevar al cuadrado obtenemos
$$B_1^2=\begin{pmatrix}a^2+bc & b(a+d)\\ c(a+d) & d^2+bc\end{pmatrix},$$
$$B_2^2=\begin{pmatrix}e^2+fg & f(e+h)\\ g(e+h) & h^2+fg\end{pmatrix}.$$
Como ambas dan la misma matriz \(A\), sus entradas correspondientes deben coincidir. Introducimos
$$t_1=a+d,\qquad t_2=e+h,\qquad r_1=a-d,\qquad r_2=e-h.$$
Entonces las entradas fuera de la diagonal satisfacen
$$b\,t_1=f\,t_2=A_{12},\qquad c\,t_1=g\,t_2=A_{21},$$
y la diferencia de las entradas diagonales produce
$$a^2-d^2=e^2-h^2 \iff r_1 t_1=r_2 t_2.$$
Si ocurriera \(t_1=t_2\), las igualdades anteriores forzarían \(b=f\), \(c=g\), \(r_1=r_2\) y por tanto \(a=e\), \(d=h\). Eso contradice que las raíces sean distintas. Por lo tanto podemos suponer
$$t_1 \lt t_2.$$
Escribimos la razón \(t_1:t_2\) en términos primitivos:
$$t_1=qn,\qquad t_2=pn,\qquad p \gt q \ge 1,\qquad \gcd(p,q)=1,\qquad n\ge 1.$$
De \(r_1 t_1=r_2 t_2\) se deduce
$$q r_1 = p r_2.$$
Como \(p\) y \(q\) son coprimos, existe un entero \(m\) tal que
$$r_1=pm,\qquad r_2=qm.$$
Así, las entradas diagonales de ambas raíces quedan fijadas por \(p,q,n,m\):
$$a=\frac{qn+pm}{2},\qquad d=\frac{qn-pm}{2},$$
$$e=\frac{pn+qm}{2},\qquad h=\frac{pn-qm}{2}.$$
Las ecuaciones de las entradas fuera de la diagonal muestran además que \(A_{12}\) y \(A_{21}\) son divisibles tanto por \(qn\) como por \(pn\). Como \(\gcd(p,q)=1\), ambos son múltiplos de \(pqn\). Escribimos entonces
$$A_{12}=pqn\,u,\qquad A_{21}=pqn\,v,\qquad u,v\in\mathbb{Z}_{>0},$$
y de ahí
$$b=pu,\qquad c=pv,\qquad f=qu,\qquad g=qv.$$
Las entradas \(a,d,e,h\) deben ser enteros positivos. La positividad exige
$$qn \gt p|m|,$$
es decir,
$$|m| \lt \frac{qn}{p}.$$
La integridad impone condiciones de paridad, porque cada entrada diagonal es una semisuma. Necesitamos que \(qn \pm pm\) y \(pn \pm qm\) sean pares. Dado que \(p\) y \(q\) son coprimos, esto se reduce a dos casos:
Si \(p\) y \(q\) tienen distinta paridad, entonces \(n\) y \(m\) deben ser ambos pares.
Si \(p\) y \(q\) son ambos impares, entonces \(m \equiv n \pmod{2}\).
Estas son exactamente las reglas de paridad que siguen las implementaciones.
Definimos
$$\ell=uv.$$
Al igualar las entradas superiores izquierdas de \(B_1^2\) y \(B_2^2\), obtenemos
$$\frac{(qn+pm)^2}{4}+p^2\ell=\frac{(pn+qm)^2}{4}+q^2\ell.$$
Al expandir y simplificar, los términos cruzados se cancelan y queda
$$4\ell=n^2-m^2.$$
Por tanto,
$$\boxed{\ell=\frac{n^2-m^2}{4}}.$$
Como \(u\) y \(v\) son positivos, se necesita \(\ell \gt 0\). La misma identidad hace coincidir automáticamente la entrada inferior derecha, de modo que esta ecuación es la compatibilidad diofántica central del método.
Una vez fijados \(p,q,n,m\), las partes diagonales de las dos raíces ya están determinadas, y también el factor común \(pqn\) de las entradas fuera de la diagonal de \(A\). La única libertad restante es factorizar
$$\ell=uv,\qquad u,v\in\mathbb{Z}_{>0}.$$
Cada divisor positivo \(u\mid \ell\) determina exactamente el par ordenado
$$\left(u,\frac{\ell}{u}\right),$$
y por tanto exactamente una matriz \(A\). El número de esos pares ordenados es la función divisor \(\tau(\ell)\). Por eso cada cuádrupla admisible \((p,q,n,m)\) aporta
$$\tau\!\left(\frac{n^2-m^2}{4}\right)$$
al conteo final.
Usando \(B_1\), la traza de \(A\) vale
$$\operatorname{tr}(A)=a^2+d^2+2bc.$$
Sustituyendo la parametrización,
$$\operatorname{tr}(A)=\frac{q^2n^2+p^2m^2}{2}+2p^2\ell.$$
Al reemplazar \(\ell\) por \(\frac{n^2-m^2}{4}\), se simplifica a
$$\operatorname{tr}(A)=\frac{(p^2+q^2)n^2}{2}.$$
La condición \(\operatorname{tr}(A)\lt N\) se convierte entonces en
$$n \le \sqrt{\frac{2N-1}{p^2+q^2}}.$$
La suma final es
$$F(N)=\sum_{\substack{p \gt q \ge 1\\ \gcd(p,q)=1}} \ \sum_{n=1}^{\left\lfloor\sqrt{\frac{2N-1}{p^2+q^2}}\right\rfloor} \ \sum_{m}\tau\!\left(\frac{n^2-m^2}{4}\right),$$
donde \(m\) recorre los enteros que cumplen
$$|m| \lt \frac{qn}{p}$$
y además las restricciones de paridad del paso anterior. Esta es exactamente la fórmula utilizada por la implementación.
Tomemos
$$p=2,\qquad q=1,\qquad n=4,\qquad m=0.$$
Entonces
$$\ell=\frac{4^2-0^2}{4}=4,\qquad \operatorname{tr}(A)=\frac{(2^2+1^2)\cdot 4^2}{2}=40.$$
Como \(\tau(4)=3\), esta única cuádrupla admisible produce tres matrices, correspondientes a \((u,v)=(1,4),(2,2),(4,1)\). Para \((u,v)=(1,4)\), las dos raíces son
$$\begin{pmatrix}2 & 2\\ 8 & 2\end{pmatrix},\qquad \begin{pmatrix}4 & 1\\ 4 & 4\end{pmatrix},$$
y ambas elevadas al cuadrado dan
$$\begin{pmatrix}20 & 8\\ 32 & 20\end{pmatrix}.$$
Así se ve claramente cómo los divisores de \(\ell\) se traducen directamente en matrices distintas.
Las implementaciones en C++, Python y Java siguen la misma idea. Primero calculan una cota superior segura para \(\ell=\frac{n^2-m^2}{4}\). El menor valor posible de \(p^2+q^2\) es \(5\), alcanzado por \((p,q)=(2,1)\), así que \(n^2 \le \frac{2N-1}{5}\) y por tanto \(\ell \le \frac{n^2}{4}\). Con esa cota, se precomputan todos los valores \(\tau(x)\) necesarios mediante una criba de divisores.
Después, el programa recorre los pares coprimos \((p,q)\) con \(p \gt q\), obtiene el rango válido de \(n\) a partir de la cota de la traza y luego avanza sobre los valores admisibles de \(m\) respetando positividad y paridad. Para cada estado válido calcula \(\ell=(n^2-m^2)/4\) y suma \(\tau(\ell)\). Las implementaciones también verifican puntos de control pequeños; en particular, comprueban \(F(50)=7\) y \(F(1000)=1019\), y la versión en C++ compara además la fórmula con una enumeración directa para un límite pequeño.
La criba de divisores hasta
$$\left\lfloor \frac{1}{4}\left\lfloor \sqrt{\frac{2N-1}{5}} \right\rfloor^2 \right\rfloor$$
requiere \(O(L\log L)\) tiempo y \(O(L)\) memoria, donde \(L\) representa esa cota. Como \(L\) es proporcional a \(N\), el preprocesamiento es en la práctica \(O(N\log N)\) en tiempo y \(O(N)\) en memoria.
La enumeración aritmética sobre \((p,q,n,m)\) queda en el mismo orden global y es muchísimo menor que un brute force sobre todas las raíces positivas posibles. La mejora clave es que nunca se enumeran directamente las matrices \(A\), sino solo los estados numéricos reducidos que ya garantizan la existencia de dos raíces cuadradas distintas.
我们要统计满足
$$A \in M_2(\mathbb{Z}_{>0})$$
并且
$$\operatorname{tr}(A) \lt N$$
的正整数 \(2\times2\) 矩阵 \(A\)，其中 \(A\) 至少拥有两个不同的正整数矩阵平方根。也就是说，存在两个不同的 正整数矩阵 \(B_1,B_2\)，使得
$$B_1^2=A=B_2^2.$$
当 \(N=10^7\) 时，直接枚举所有矩阵完全不可行，所以解法的核心是分析“同一个矩阵拥有两个不同平方根”这一事实所 强加的数论结构。
设
$$B_1=\begin{pmatrix}a & b\\ c & d\end{pmatrix},\qquad B_2=\begin{pmatrix}e & f\\ g & h\end{pmatrix},$$
其中八个变量都是正整数，且 \(B_1 \ne B_2\)。平方后有
$$B_1^2=\begin{pmatrix}a^2+bc & b(a+d)\\ c(a+d) & d^2+bc\end{pmatrix},$$
$$B_2^2=\begin{pmatrix}e^2+fg & f(e+h)\\ g(e+h) & h^2+fg\end{pmatrix}.$$
因为两者都等于同一个 \(A\)，对应位置的元素必须相等。定义
$$t_1=a+d,\qquad t_2=e+h,\qquad r_1=a-d,\qquad r_2=e-h.$$
于是非对角元素满足
$$b\,t_1=f\,t_2=A_{12},\qquad c\,t_1=g\,t_2=A_{21},$$
而对角元素之差给出
$$a^2-d^2=e^2-h^2 \iff r_1 t_1=r_2 t_2.$$
如果 \(t_1=t_2\)，那么上式会进一步推出 \(b=f\)、\(c=g\)、\(r_1=r_2\)，从而 \(a=e\)、\(d=h\)，也就是两 个平方根其实相同。这与“不同平方根”矛盾。因此必有
$$t_1 \lt t_2.$$
将 \(t_1:t_2\) 写成最简比：
$$t_1=qn,\qquad t_2=pn,\qquad p \gt q \ge 1,\qquad \gcd(p,q)=1,\qquad n\ge 1.$$
由 \(r_1 t_1=r_2 t_2\) 得到
$$q r_1 = p r_2.$$
因为 \(p,q\) 互素，所以存在整数 \(m\)，使得
$$r_1=pm,\qquad r_2=qm.$$
这样，两个平方根的对角元素完全由 \(p,q,n,m\) 决定：
$$a=\frac{qn+pm}{2},\qquad d=\frac{qn-pm}{2},$$
$$e=\frac{pn+qm}{2},\qquad h=\frac{pn-qm}{2}.$$
再看非对角元素。由于 \(A_{12}\) 与 \(A_{21}\) 同时被 \(qn\) 和 \(pn\) 整除，而 \(\gcd(p,q)=1\)，它们必然 都是 \(pqn\) 的倍数。于是可写成
$$A_{12}=pqn\,u,\qquad A_{21}=pqn\,v,\qquad u,v\in\mathbb{Z}_{>0}.$$
代回去便得到
$$b=pu,\qquad c=pv,\qquad f=qu,\qquad g=qv.$$
\(a,d,e,h\) 必须是正整数。正性要求
$$qn \gt p|m|,$$
也就是
$$|m| \lt \frac{qn}{p}.$$
整数性则要求 \(qn \pm pm\) 与 \(pn \pm qm\) 都为偶数。由于 \(p,q\) 互素，这一条件可以简化为两个情形：
如果 \(p,q\) 一奇一偶，那么 \(n\) 和 \(m\) 都必须是偶数。
如果 \(p,q\) 都是奇数，那么 \(m \equiv n \pmod{2}\)。
实现中的奇偶筛选正是对这两个规则的直接编码。
记
$$\ell=uv.$$
比较 \(B_1^2\) 与 \(B_2^2\) 左上角元素，得到
$$\frac{(qn+pm)^2}{4}+p^2\ell=\frac{(pn+qm)^2}{4}+q^2\ell.$$
展开并整理后，交叉项会抵消，最终得到
$$4\ell=n^2-m^2.$$
因此
$$\boxed{\ell=\frac{n^2-m^2}{4}}.$$
由于 \(u,v\) 都是正整数，所以必须有 \(\ell \gt 0\)。同一关系也会自动保证右下角元素相等，因此这是整个问题 最关键的丢番图约束。
一旦 \(p,q,n,m\) 固定，两个平方根的对角部分就固定了，矩阵 \(A\) 的非对角元素中共同的比例因子 \(pqn\) 也固 定了。剩下唯一的自由度就是把 \(\ell\) 分解为
$$\ell=uv,\qquad u,v\in\mathbb{Z}_{>0}.$$
对每一个正约数 \(u\mid \ell\)，都对应唯一的有序因子对
$$\left(u,\frac{\ell}{u}\right),$$
也就对应唯一一个矩阵 \(A\)。这类有序因子对的个数恰好就是约数函数 \(\tau(\ell)\)。所以每个可行的 \((p,q,n,m)\) 都贡献
$$\tau\!\left(\frac{n^2-m^2}{4}\right).$$
利用 \(B_1\) 可以计算 \(A\) 的迹：
$$\operatorname{tr}(A)=a^2+d^2+2bc.$$
代入参数化表达式，有
$$\operatorname{tr}(A)=\frac{q^2n^2+p^2m^2}{2}+2p^2\ell.$$
再用 \(\ell=\frac{n^2-m^2}{4}\) 化简，得到
$$\operatorname{tr}(A)=\frac{(p^2+q^2)n^2}{2}.$$
于是条件 \(\operatorname{tr}(A)\lt N\) 等价于
$$n \le \sqrt{\frac{2N-1}{p^2+q^2}}.$$
最终计数公式就是
$$F(N)=\sum_{\substack{p \gt q \ge 1\\ \gcd(p,q)=1}} \ \sum_{n=1}^{\left\lfloor\sqrt{\frac{2N-1}{p^2+q^2}}\right\rfloor} \ \sum_{m}\tau\!\left(\frac{n^2-m^2}{4}\right),$$
其中 \(m\) 遍历所有满足
$$|m| \lt \frac{qn}{p}$$
并同时满足上一步奇偶条件的整数。这正是实现中所累加的公式。
取
$$p=2,\qquad q=1,\qquad n=4,\qquad m=0.$$
则
$$\ell=\frac{4^2-0^2}{4}=4,\qquad \operatorname{tr}(A)=\frac{(2^2+1^2)\cdot 4^2}{2}=40.$$
因为 \(\tau(4)=3\)，这一个可行状态就会产生三个矩阵，对应的因子对为 \((u,v)=(1,4),(2,2),(4,1)\)。当 \((u,v)=(1,4)\) 时，两个平方根是
$$\begin{pmatrix}2 & 2\\ 8 & 2\end{pmatrix},\qquad \begin{pmatrix}4 & 1\\ 4 & 4\end{pmatrix},$$
它们平方后都得到
$$\begin{pmatrix}20 & 8\\ 32 & 20\end{pmatrix}.$$
这个例子清楚展示了：为什么 \(\ell\) 的约数个数正好等于这一状态贡献的矩阵个数。
C++、Python 和 Java 三个实现遵循完全相同的流程。首先根据 \(\ell=\frac{n^2-m^2}{4}\) 推出一个安全上界。因为 \(p^2+q^2\) 的最小值出现在 \((p,q)=(2,1)\)，为 \(5\)， 所以 \(n^2 \le \frac{2N-1}{5}\)，从而 \(\ell \le \frac{n^2}{4}\)。有了这个界以后，程序先用约数筛法预计算所 需的全部 \(\tau(x)\)。
然后程序枚举所有互素且满足 \(p \gt q\) 的 \((p,q)\)，由迹约束得到 \(n\) 的上界，再根据正性和奇偶性约束枚举 合法的 \(m\)。每遇到一个可行状态，就计算 \(\ell=(n^2-m^2)/4\)，并把 \(\tau(\ell)\) 加入答案。实现还会检查 小规模校验点；其中 \(F(50)=7\)、\(F(1000)=1019\)，而 C++ 版本还会在较小范围上把公式结果与直接枚举进行比对。
约数筛需要预计算到
$$\left\lfloor \frac{1}{4}\left\lfloor \sqrt{\frac{2N-1}{5}} \right\rfloor^2 \right\rfloor.$$
若记该上界为 \(L\)，那么筛法时间复杂度为 \(O(L\log L)\)，空间复杂度为 \(O(L)\)。由于 \(L\) 与 \(N\) 成正比， 预处理阶段可以看作 \(O(N\log N)\) 时间和 \(O(N)\) 空间。
对 \((p,q,n,m)\) 的枚举总体上也处于同一数量级，但相比直接暴力枚举所有正整数平方根已经小得多。关键改进在于： 程序并不直接扫描矩阵 \(A\)，而是只遍历那些已经保证会产生两个不同平方根的简化数论状态。
Нужно посчитать все положительные целочисленные матрицы
$$A \in M_2(\mathbb{Z}_{>0})$$
такие, что
$$\operatorname{tr}(A) \lt N,$$
и при этом у \(A\) есть как минимум два различных положительных целочисленных квадратных корня. То есть существуют две разные матрицы \(B_1\) и \(B_2\) с положительными целыми элементами, для которых
$$B_1^2=A=B_2^2.$$
Для \(N=10^7\) прямой перебор невозможен, поэтому решение строится не вокруг самих матриц \(A\), а вокруг арифметических ограничений, возникающих из существования двух разных корней одной и той же матрицы.
Пусть
$$B_1=\begin{pmatrix}a & b\\ c & d\end{pmatrix},\qquad B_2=\begin{pmatrix}e & f\\ g & h\end{pmatrix},$$
где все восемь переменных положительны и \(B_1 \ne B_2\). Тогда
$$B_1^2=\begin{pmatrix}a^2+bc & b(a+d)\\ c(a+d) & d^2+bc\end{pmatrix},$$
$$B_2^2=\begin{pmatrix}e^2+fg & f(e+h)\\ g(e+h) & h^2+fg\end{pmatrix}.$$
Поскольку обе матрицы равны одному и тому же \(A\), соответствующие элементы обязаны совпадать. Введем обозначения
$$t_1=a+d,\qquad t_2=e+h,\qquad r_1=a-d,\qquad r_2=e-h.$$
Тогда для внедиагональных элементов имеем
$$b\,t_1=f\,t_2=A_{12},\qquad c\,t_1=g\,t_2=A_{21},$$
а разность диагональных элементов дает
$$a^2-d^2=e^2-h^2 \iff r_1 t_1=r_2 t_2.$$
Если бы \(t_1=t_2\), то первые равенства дали бы \(b=f\) и \(c=g\), а второе равенство дало бы \(r_1=r_2\), откуда следовало бы \(a=e\) и \(d=h\). Значит, различные корни обязаны иметь разные суммы диагональных элементов. Можно считать, что
$$t_1 \lt t_2.$$
Запишем отношение \(t_1:t_2\) в приведенном виде:
$$t_1=qn,\qquad t_2=pn,\qquad p \gt q \ge 1,\qquad \gcd(p,q)=1,\qquad n\ge 1.$$
Из соотношения \(r_1 t_1=r_2 t_2\) получаем
$$q r_1 = p r_2.$$
Так как \(p\) и \(q\) взаимно просты, существует целое \(m\), такое что
$$r_1=pm,\qquad r_2=qm.$$
Следовательно, диагональные элементы обоих корней выражаются через \(p,q,n,m\):
$$a=\frac{qn+pm}{2},\qquad d=\frac{qn-pm}{2},$$
$$e=\frac{pn+qm}{2},\qquad h=\frac{pn-qm}{2}.$$
Равенства для внедиагональных элементов показывают также, что \(A_{12}\) и \(A_{21}\) делятся и на \(qn\), и на \(pn\). Поскольку \(\gcd(p,q)=1\), оба элемента кратны \(pqn\). Поэтому можно написать
$$A_{12}=pqn\,u,\qquad A_{21}=pqn\,v,\qquad u,v\in\mathbb{Z}_{>0},$$
и тогда
$$b=pu,\qquad c=pv,\qquad f=qu,\qquad g=qv.$$
Числа \(a,d,e,h\) должны быть положительными целыми. Из положительности следует
$$qn \gt p|m|,$$
то есть
$$|m| \lt \frac{qn}{p}.$$
Целочисленность требует, чтобы \(qn \pm pm\) и \(pn \pm qm\) были четными. Так как \(p\) и \(q\) взаимно просты, это сводится к двум случаям:
Если \(p\) и \(q\) разной четности, то и \(n\), и \(m\) должны быть четными.
Если \(p\) и \(q\) оба нечетные, то \(m \equiv n \pmod{2}\).
Именно эти фильтры четности используются в реализации.
Обозначим
$$\ell=uv.$$
Сравним левые верхние элементы матриц \(B_1^2\) и \(B_2^2\):
$$\frac{(qn+pm)^2}{4}+p^2\ell=\frac{(pn+qm)^2}{4}+q^2\ell.$$
После раскрытия скобок смешанные члены сокращаются, и остается
$$4\ell=n^2-m^2.$$
Следовательно,
$$\boxed{\ell=\frac{n^2-m^2}{4}}.$$
Так как \(u\) и \(v\) положительны, необходимо \(\ell \gt 0\). Та же самая формула автоматически обеспечивает совпадение правых нижних элементов, поэтому это и есть главное диофантово условие задачи.
После фиксации \(p,q,n,m\) диагональные части обоих корней уже определены, как и общий множитель \(pqn\) в внедиагональных элементах матрицы \(A\). Остается только разложить \(\ell\) в виде
$$\ell=uv,\qquad u,v\in\mathbb{Z}_{>0}.$$
Каждый положительный делитель \(u\mid \ell\) задает единственную упорядоченную пару
$$\left(u,\frac{\ell}{u}\right),$$
а значит, и единственную матрицу \(A\). Число таких упорядоченных пар равно функции числа делителей \(\tau(\ell)\). Поэтому каждая допустимая четверка \((p,q,n,m)\) вносит вклад
$$\tau\!\left(\frac{n^2-m^2}{4}\right).$$
Используя \(B_1\), вычислим след:
$$\operatorname{tr}(A)=a^2+d^2+2bc.$$
Подстановка параметризации дает
$$\operatorname{tr}(A)=\frac{q^2n^2+p^2m^2}{2}+2p^2\ell.$$
После замены \(\ell=\frac{n^2-m^2}{4}\) получаем простое выражение
$$\operatorname{tr}(A)=\frac{(p^2+q^2)n^2}{2}.$$
Значит, условие \(\operatorname{tr}(A)\lt N\) равносильно
$$n \le \sqrt{\frac{2N-1}{p^2+q^2}}.$$
Итоговая формула подсчета имеет вид
$$F(N)=\sum_{\substack{p \gt q \ge 1\\ \gcd(p,q)=1}} \ \sum_{n=1}^{\left\lfloor\sqrt{\frac{2N-1}{p^2+q^2}}\right\rfloor} \ \sum_{m}\tau\!\left(\frac{n^2-m^2}{4}\right),$$
где \(m\) пробегает все целые числа, удовлетворяющие
$$|m| \lt \frac{qn}{p}$$
и условиям четности из предыдущего шага. Именно эту сумму и вычисляют реализации.
Возьмем
$$p=2,\qquad q=1,\qquad n=4,\qquad m=0.$$
Тогда
$$\ell=\frac{4^2-0^2}{4}=4,\qquad \operatorname{tr}(A)=\frac{(2^2+1^2)\cdot 4^2}{2}=40.$$
Так как \(\tau(4)=3\), эта одна допустимая конфигурация порождает три матрицы, соответствующие \((u,v)=(1,4),(2,2),(4,1)\). Для \((u,v)=(1,4)\) два корня имеют вид
$$\begin{pmatrix}2 & 2\\ 8 & 2\end{pmatrix},\qquad \begin{pmatrix}4 & 1\\ 4 & 4\end{pmatrix},$$
и обе матрицы при возведении в квадрат дают
$$\begin{pmatrix}20 & 8\\ 32 & 20\end{pmatrix}.$$
Этот пример наглядно показывает, почему количество делителей \(\ell\) напрямую равно количеству порождаемых матриц.
Реализации на C++, Python и Java устроены одинаково. Сначала выводится верхняя граница для \(\ell=\frac{n^2-m^2}{4}\). Минимальное возможное значение \(p^2+q^2\) равно \(5\) и достигается при \((p,q)=(2,1)\), поэтому \(n^2 \le \frac{2N-1}{5}\), а значит, \(\ell \le \frac{n^2}{4}\). До этой границы заранее вычисляются все значения \(\tau(x)\) с помощью решета делителей.
После этого программа перебирает взаимно простые пары \((p,q)\) с \(p \gt q\), находит допустимый диапазон для \(n\) из ограничения на след и затем перебирает все допустимые значения \(m\), удовлетворяющие условиям положительности и четности. Для каждого допустимого состояния вычисляется \(\ell=(n^2-m^2)/4\), и к ответу добавляется \(\tau(\ell)\). Реализации также проверяют малые контрольные значения: в частности, \(F(50)=7\) и \(F(1000)=1019\), а версия на C++ дополнительно сверяет формулу с прямым перебором на небольшом ограничении.
Решето делителей строится до значения
$$\left\lfloor \frac{1}{4}\left\lfloor \sqrt{\frac{2N-1}{5}} \right\rfloor^2 \right\rfloor.$$
Если обозначить эту границу через \(L\), то его стоимость равна \(O(L\log L)\) по времени и \(O(L)\) по памяти. Так как \(L\) пропорционально \(N\), стадия предвычисления фактически имеет сложность \(O(N\log N)\) по времени и \(O(N)\) по памяти.
Перебор арифметических состояний \((p,q,n,m)\) имеет тот же порядок в сумме и несравнимо меньше наивного перебора всех положительных квадратных корней. Главный выигрыш состоит в том, что программа не перебирает матрицы \(A\) напрямую, а работает только с сокращенными числовыми параметрами, которые уже гарантируют существование двух различных корней.
نريد عدّ جميع المصفوفات الصحيحة الموجبة
$$A \in M_2(\mathbb{Z}_{>0})$$
التي تحقق
$$\operatorname{tr}(A) \lt N$$
ولها على الأقل جذران تربيعيان مختلفان من المصفوفات الصحيحة الموجبة. أي توجد مصفوفتان مختلفتان \(B_1\) و\(B_2\) بحيث
$$B_1^2=A=B_2^2.$$
البحث المباشر في جميع المصفوفات مستحيل عملياً عندما يكون \(N=10^7\)، لذلك تعتمد الفكرة على تحليل البنية العددية التي تفرضها حقيقة أن للمصفوفة نفسها جذرين مختلفين.
لنكتب
$$B_1=\begin{pmatrix}a & b\\ c & d\end{pmatrix},\qquad B_2=\begin{pmatrix}e & f\\ g & h\end{pmatrix},$$
حيث جميع القيم موجبة وصحيحة، ومع \(B_1 \ne B_2\). عند التربيع نحصل على
$$B_1^2=\begin{pmatrix}a^2+bc & b(a+d)\\ c(a+d) & d^2+bc\end{pmatrix},$$
$$B_2^2=\begin{pmatrix}e^2+fg & f(e+h)\\ g(e+h) & h^2+fg\end{pmatrix}.$$
وبما أن الناتجين متساويان، فلا بد أن تتساوى العناصر المناظرة. نعرّف
$$t_1=a+d,\qquad t_2=e+h,\qquad r_1=a-d,\qquad r_2=e-h.$$
من العناصر خارج القطر نحصل على
$$b\,t_1=f\,t_2=A_{12},\qquad c\,t_1=g\,t_2=A_{21},$$
ومن فرق العنصرين القطريين نحصل على
$$a^2-d^2=e^2-h^2 \iff r_1 t_1=r_2 t_2.$$
ولو كان \(t_1=t_2\)، لفرضت المساوات السابقة \(b=f\) و\(c=g\) و\(r_1=r_2\)، ومن ثم \(a=e\) و\(d=h\)، أي إن الجذرين سيكونان متماثلين. لذلك يمكن افتراض
$$t_1 \lt t_2.$$
نكتب النسبة \(t_1:t_2\) في أبسط صورة:
$$t_1=qn,\qquad t_2=pn,\qquad p \gt q \ge 1,\qquad \gcd(p,q)=1,\qquad n\ge 1.$$
ومن العلاقة \(r_1 t_1=r_2 t_2\) نحصل على
$$q r_1 = p r_2.$$
وبما أن \(p\) و\(q\) أوليان فيما بينهما، فهناك عدد صحيح \(m\) بحيث
$$r_1=pm,\qquad r_2=qm.$$
لذلك تصبح العناصر القطرية للجذرين
$$a=\frac{qn+pm}{2},\qquad d=\frac{qn-pm}{2},$$
$$e=\frac{pn+qm}{2},\qquad h=\frac{pn-qm}{2}.$$
أما من العلاقات خارج القطر فنرى أن \(A_{12}\) و\(A_{21}\) قابلان للقسمة على \(qn\) وعلى \(pn\) معاً، ومع \(\gcd(p,q)=1\) فهذا يعني أنهما من مضاعفات \(pqn\). لذا نكتب
$$A_{12}=pqn\,u,\qquad A_{21}=pqn\,v,\qquad u,v\in\mathbb{Z}_{>0},$$
ومنها
$$b=pu,\qquad c=pv,\qquad f=qu,\qquad g=qv.$$
يجب أن تكون \(a,d,e,h\) أعداداً صحيحة موجبة. من شرط الإيجابية نحصل على
$$qn \gt p|m|,$$
أي
$$|m| \lt \frac{qn}{p}.$$
أما شرط الصحيحة فيفرض أن يكون كل من \(qn \pm pm\) و\(pn \pm qm\) زوجياً. وبسبب أولية \(p\) و\(q\) فيما بينهما، ينحصر الأمر في حالتين:
إذا كان \(p\) و\(q\) مختلفي الزوجية، فيجب أن يكون كل من \(n\) و\(m\) زوجياً.
إذا كان \(p\) و\(q\) فرديين، فيجب أن يكون \(m \equiv n \pmod{2}\).
وهذه هي بالضبط المرشحات التي تستخدمها التطبيقات عند تعداد القيم الممكنة لـ \(m\).
لنضع
$$\ell=uv.$$
بمقارنة العنصر العلوي الأيسر في \(B_1^2\) و\(B_2^2\) نحصل على
$$\frac{(qn+pm)^2}{4}+p^2\ell=\frac{(pn+qm)^2}{4}+q^2\ell.$$
وبعد التوسيع والاختزال تختفي الحدود المختلطة ويبقى
$$4\ell=n^2-m^2.$$
إذن
$$\boxed{\ell=\frac{n^2-m^2}{4}}.$$
وبما أن \(u\) و\(v\) موجبان، فلا بد أن يكون \(\ell \gt 0\). كما أن العلاقة نفسها تضمن تلقائياً تساوي العنصر السفلي الأيمن، لذا فهي الشرط الديوفانتي الأساسي في الحل.
عندما تثبت القيم \(p,q,n,m\)، تصبح الأجزاء القطرية في الجذرين محددة بالكامل، كما يثبت العامل المشترك \(pqn\) في العناصر خارج القطر للمصفوفة \(A\). الحرية الوحيدة الباقية هي تفكيك \(\ell\) على صورة
$$\ell=uv,\qquad u,v\in\mathbb{Z}_{>0}.$$
كل قاسم موجب \(u\mid \ell\) يحدد زوجاً مرتباً وحيداً
$$\left(u,\frac{\ell}{u}\right),$$
ومن ثم يحدد مصفوفة \(A\) واحدة. وعدد هذه الأزواج المرتبة هو دالة عدد القواسم \(\tau(\ell)\). لذلك فإن كل رباعية صالحة \((p,q,n,m)\) تضيف إلى الناتج
$$\tau\!\left(\frac{n^2-m^2}{4}\right).$$
باستخدام \(B_1\) نحسب أثر \(A\):
$$\operatorname{tr}(A)=a^2+d^2+2bc.$$
وبعد التعويض نحصل على
$$\operatorname{tr}(A)=\frac{q^2n^2+p^2m^2}{2}+2p^2\ell.$$
ثم نستبدل \(\ell\) بالقيمة \(\frac{n^2-m^2}{4}\) فنصل إلى
$$\operatorname{tr}(A)=\frac{(p^2+q^2)n^2}{2}.$$
وبالتالي فإن الشرط \(\operatorname{tr}(A)\lt N\) يكافئ
$$n \le \sqrt{\frac{2N-1}{p^2+q^2}}.$$
ومن هنا تكون صيغة العد النهائية
$$F(N)=\sum_{\substack{p \gt q \ge 1\\ \gcd(p,q)=1}} \ \sum_{n=1}^{\left\lfloor\sqrt{\frac{2N-1}{p^2+q^2}}\right\rfloor} \ \sum_{m}\tau\!\left(\frac{n^2-m^2}{4}\right),$$
حيث يدور \(m\) على جميع الأعداد الصحيحة التي تحقق
$$|m| \lt \frac{qn}{p}$$
إلى جانب شروط الزوجية السابقة. وهذه هي الصيغة نفسها التي تجمعها التطبيقات.
خذ
$$p=2,\qquad q=1,\qquad n=4,\qquad m=0.$$
فنحصل على
$$\ell=\frac{4^2-0^2}{4}=4,\qquad \operatorname{tr}(A)=\frac{(2^2+1^2)\cdot 4^2}{2}=40.$$
وبما أن \(\tau(4)=3\)، فإن هذه الحالة الواحدة تنتج ثلاث مصفوفات تقابل أزواج العوامل \((u,v)=(1,4),(2,2),(4,1)\). وعندما \((u,v)=(1,4)\)، يكون الجذران
$$\begin{pmatrix}2 & 2\\ 8 & 2\end{pmatrix},\qquad \begin{pmatrix}4 & 1\\ 4 & 4\end{pmatrix},$$
وكلاهما يعطي بعد التربيع
$$\begin{pmatrix}20 & 8\\ 32 & 20\end{pmatrix}.$$
وهذا يوضح عملياً لماذا يساوي عدد قواسم \(\ell\) عدد المصفوفات الناتجة عن الحالة نفسها.
تنفذ نسخ C++ وPython وJava المنطق نفسه. في البداية تستخرج حداً أعلى آمناً للقيمة \(\ell=\frac{n^2-m^2}{4}\). أصغر قيمة ممكنة لـ \(p^2+q^2\) هي \(5\) عند \((p,q)=(2,1)\)، ولذلك \(n^2 \le \frac{2N-1}{5}\) ومن ثم \(\ell \le \frac{n^2}{4}\). بعد ذلك تُحسب قيم \(\tau(x)\) المطلوبة مسبقاً بواسطة منخل للقواسم.
ثم تمر التطبيقات على جميع الأزواج الأولية فيما بينها \((p,q)\) مع \(p \gt q\)، وتحسب المدى المسموح لـ \(n\) من حد الأثر، ثم تعدد قيم \(m\) التي تحقق الإيجابية والزوجية. عند كل حالة صالحة تُحسب \(\ell=(n^2-m^2)/4\) وتُضاف \(\tau(\ell)\) إلى المجموع. كما تُجرى اختبارات تحقق صغيرة؛ وعلى وجه الخصوص يتم التأكد من أن \(F(50)=7\) وأن \(F(1000)=1019\)، بينما تقارن نسخة C++ الصيغة أيضاً بعدّ مباشر عند حد صغير.
منخل القواسم يُبنى حتى الحد
$$\left\lfloor \frac{1}{4}\left\lfloor \sqrt{\frac{2N-1}{5}} \right\rfloor^2 \right\rfloor.$$
إذا رمزنا لهذا الحد بـ \(L\)، فزمن المنخل هو \(O(L\log L)\) والذاكرة \(O(L)\). وبما أن \(L\) يتناسب خطياً مع \(N\)، فإن مرحلة التهيئة تعادل عملياً \(O(N\log N)\) زمناً و\(O(N)\) ذاكرة.
أما تعداد الحالات \((p,q,n,m)\) فيبقى في المرتبة نفسها إجمالاً، لكنه أصغر بكثير من البحث الخام في جميع الجذور المربعة الموجبة الممكنة. الفكرة الحاسمة هي أن البرنامج لا يعدّ المصفوفات \(A\) مباشرة، بل يعدّ الحالات العددية المختزلة التي تضمن سلفاً وجود جذرين تربيعيين مختلفين.