Project Euler 420

发表于 2026-02-13 分类于 Project Euler 阅读次数：本文字数： 4k 阅读时长 ≈ 4 分钟

Project Euler 420

题目

2x2 positive integer matrix

A positive integer matrix is a matrix whose elements are all positive integers.

Some positive integer matrices can be expressed as a square of a positive integer matrix in two different ways. Here is an example:

\[\begin{pmatrix} 40 & 12\\ 48 & 40 \end{pmatrix} = \begin{pmatrix} 2 & 3\\ 12 & 2 \end{pmatrix}^2 = \begin{pmatrix} 6 & 1\\ 4 & 6 \end{pmatrix}^2 \]

We define \(F(N)\) as the number of the \(2\times2\) positive integer matrices which have a trace less than \(N\) and which can be expressed as a square of a positive integer matrix in two different ways.

We can verify that \(F(50) = 7\) and \(F(1000) = 1019\).

Find \(F(10^7)\).

解决方案

1. 平方展开与必要不变量

设\(X=\begin{pmatrix}a&b\\c&d\end{pmatrix} (a,b,c,d\in\mathbb Z_{>0})\)，则令\(M=X^2=\begin{pmatrix}a^2+bc & b(a+d)\\c(a+d) & d^2+bc\end{pmatrix}.\)并令\(M=\begin{pmatrix}A&B\\C&D\end{pmatrix} (A,B,C,D\in\mathbb Z_{>0})\)。因此当 \(M=X^2\) 时，\(\operatorname{tr}(M)=T=A+D=a^2+d^2+2bc,\det(M)=(\det X)^2=(ad-bc)^2.\)令\(\Delta=\sqrt{\det(M)}\in\mathbb Z_{\ge 0}.\)若 \(M\) 有两种不同的平方根，则必有 \(\Delta>0\)（否则会退化成同一个解）。

对任意 \(2\times2\) 矩阵，特征多项式是\(\lambda^2-T\lambda+\det(M),\)由 Caylay-Camilton定理定理有\(M^2-TM+\det(M)I=0,\)也就是\(M^2=TM-\det(M)I.\)

因为任意高次 \(M^k\) 都能用上面的关系不断降幂，最终写成\(uM+vI\)的形式，所以我们可以直接设平方根也为\(X=\alpha M+\beta I.\)

先展开：\(X^2=(\alpha M+\beta I)^2=\alpha^2M^2+2\alpha\beta M+\beta^2I.\)代入 \(M^2=TM-\det(M)I\)，有：

\[ X^2=\alpha^2(TM-\det(M)I)+2\alpha\beta M+\beta^2I=\bigl(\alpha^2T+2\alpha\beta\bigr)M+\bigl(\beta^2-\alpha^2\det(M)\bigr)I. \]

我们要求 \[X^2=M\]，因此必须满足系数匹配：\(\alpha^2T+2\alpha\beta=1,\)\(\beta^2-\alpha^2\det(M)=0.\)

第二个方程给出\(\beta^2=\alpha^2\det(M)\Longrightarrow \beta=\pm \alpha\Delta.\)

代回第一个方程：\(\alpha^2T+2\alpha(\pm \alpha\Delta)=\alpha^2(T\pm 2\Delta)=1.\)因此\(\alpha=\dfrac{1}{\sqrt{T\pm 2\Delta}}.\)再由 \(\beta=\pm \alpha\Delta\) 得\(\beta=\dfrac{\pm \Delta}{\sqrt{T\pm 2\Delta}}.\)

于是平方根为\(X=\alpha M+\beta I=\dfrac{1}{\sqrt{T\pm 2\Delta}}M+\dfrac{\pm \Delta}{\sqrt{T\pm 2\Delta}}I=\dfrac{M\pm \Delta I}{\sqrt{T\pm 2\Delta}}.\)

这就推出了两种形式： \[ X_{+}=\frac{M+\Delta I}{\sqrt{T+2\Delta}}, X_{-}=\frac{M-\Delta I}{\sqrt{T-2\Delta}}. \]

如果 \(X\) 是平方根，那么\((-X)^2=X^2=M.\)所以每个 \(X_{+},X_{-}\) 都可以再乘一个整体负号，得到总共 4 个平方根：\(\pm X_{+}, \pm X_{-}.\)在题目里我们只关心元素全为正整数的平方根，所以最终只可能落在其中一部分。

因此若 \(M\) 同时存在两种不同的整数平方根，那么必须满足：\(\Delta\in\mathbb Z_{>0}\)；\(T+2\Delta\) 与 \(T-2\Delta\) 都是完全平方数。

于是存在整数 \(x_1<x_2\)，使得\(T-2\Delta=x_1^2, T+2\Delta=x_2^2.\)从而\(T=\dfrac{x_1^2+x_2^2}{2}, \Delta=\dfrac{x_2^2-x_1^2}{4}.\)要保证 \(T,\Delta\) 为整数，必须 \(x_1,x_2\) 同奇同偶；又因为 \(\Delta>0\)，所以 \(x_2>x_1\)。并且题目限制 \(T<N\)，等价于\(x_1^2+x_2^2<2N.\)

若 \(X_{+},X_{-}\) 都是整数矩阵，则它们的分母必须整除分子各项：

\(x_2=\sqrt{T+2\Delta}\) 必须整除 \(A+\Delta,B,C,D+\Delta\)；
\(x_1=\sqrt{T-2\Delta}\) 必须整除 \(A-\Delta,B,C,D-\Delta\)。

特别地，\(x_1\mid B,x_1\mid C, x_2\mid B,x_2\mid C.\)因此\(\operatorname{lcm}(x_1,x_2)\mid B, \operatorname{lcm}(x_1,x_2)\mid C.\)

令\(g=\gcd(x_1,x_2), x_1=gX_1,x_2=gX_2,\gcd(X_1,X_2)=1.\)则 \(L=\operatorname{lcm}(x_1,x_2)=gX_1X_2.\)写\(B=Lu, C=Lv,\)其中\(u,v\in\mathbb Z_{>0}.\)

利用\(\Delta^2=\det(M)=AD-BC\)得到\(BC=AD-\Delta^2.\)再令\(S=A-D,\)则\(A=\dfrac{T+S}{2}, D=\dfrac{T-S}{2},\)从而\(AD=\dfrac{T^2-S^2}{4}.\)于是\(BC=\dfrac{T^2-S^2}{4}-\Delta^2.\)

另一方面，由\(T=\dfrac{x_1^2+x_2^2}{2}, \Delta=\dfrac{x_2^2-x_1^2}{4}\)可直接化简出一个关键恒等式：\(T^2-4\Delta^2=x_1^2x_2^2.\)因此\(BC=\dfrac{x_1^2x_2^2-S^2}{4}.\)

在满足“两个平方根都为整数”的情况下，\(S\) 会被强制成\(S=Lk=gX_1X_2k,\)其中 \(k\) 与 \(g\) 同奇偶，且 \(|k|<g\)。代入上式并除以 \(L^2=(gX_1X_2)^2\) 得到\(uv=\dfrac{BC}{L^2}=\dfrac{g^2-k^2}{4}.\)

因此对固定的 \((x_1,x_2,g,k)\)，合法的 \((u,v)\) 数量就是\(\tau\left(\dfrac{g^2-k^2}{4}\right),\)其中 \(\tau(n)\) 是正约数个数函数（因为 \(uv\) 固定，\(u\) 取任意正因子即可唯一决定 \(v\)）。

需要注意的是，当 \(k\ne 0\) 时，\(S=Lk\) 与 \(S=-Lk\) 对应把 \((A,D)\) 交换，会得到不同的矩阵，并且两者的 \((B,C)\) 计数完全相同，所以贡献需要乘 \(2\)。当 \(k=0\) 时有 \(A=D\)，交换不产生新矩阵，所以不乘 \(2\)。

为了让两个平方根都为正整数矩阵，需要\(A>\Delta, D>\Delta,\)这会化成一个简单不等式约束：\(g\cdot x_1>k\cdot x_2.\)此外 \(k<g\) 也保证\(\dfrac{g^2-k^2}{4}>0.\)

最终，我们直接枚举所有可能的 \((x_1,x_2)\)：

\(x_1<x_2\)；
同奇同偶（用步长 \(2\) 保证）；
\(x_1^2+x_2^2<2N\)。

对每对 \((x_1,x_2)\)：

计算 \(g=\gcd(x_1,x_2)\)；
枚举 \(k\in{1,2,\dots,g-1}\) 且 \(k\equiv g\pmod 2\)；
若 \(g x_1>k x_2\)，累加\(2\cdot \tau\left(\dfrac{g^2-k^2}{4}\right).\)
若 \(g\) 为偶数，额外加入 \(k=0\) 情况：\(\tau\left(\dfrac{g^2}{4}\right).\)
代码

from tools import gcd, int_sqrt
from typing import List

N = 10 ** 7

def divisor_count_table(n: int) -> List[int]:
    spf = [0] * (n + 1)
    exp = [0] * (n + 1)
    tau = [0] * (n + 1)
    tau[1] = 1
    primes = []
    for i in range(2, n + 1):
        if spf[i] == 0:
            spf[i] = i
            exp[i] = 1
            tau[i] = 2
            primes.append(i)
        for p in primes:
            x = i * p
            if x > n:
                break
            spf[x] = p
            if p == spf[i]:
                exp[x] = exp[i] + 1
                tau[x] = tau[i] // (exp[i] + 1) * (exp[x] + 1)
                break
            else:
                exp[x] = 1
                tau[x] = tau[i] * 2
    return tau


def F(N: int) -> int:
    lim = N // 10 + 5
    tau = divisor_count_table(lim)

    ans = 0
    r1 = int_sqrt(N - 1)
    for x1 in range(1, r1 + 1):
        x1sq = x1 * x1
        for x2 in range(x1 + 2, int_sqrt(2 * N - x1sq - 1) + 1, 2):
            g = gcd(x1, x2)
            k0 = 2 - (g & 1)
            gg = g * g
            for k in range(k0, g, 2):
                if g * x1 <= k * x2:
                    break
                t = (gg - k * k) // 4
                ans += 2 * tau[t]
            if (g & 1) == 0:
                ans += tau[gg // 4]
    return ans


if __name__ == "__main__":
    print(F(N))

Project Euler 420

题目

2x2 positive integer matrix

解决方案

1. 平方展开与必要不变量

代码