正整数矩阵是元素均为正整数的矩阵。

有些正整数矩阵可以有多种方式表达为另一个正整数矩阵的平方，下面是一个例子： $$\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.$$ 定义F(N)为迹小于N，且能用至少两种方式表示成另一个正整数矩阵平方的正整数矩阵的数量。

可以验证$F(50)=7, F(1000)=1019$。

求$F(10^7)$。

本题难度:

解答

尝试一些例子后可以方向这样的矩阵的两个特征值（显然互异）都是完全平方数。事实上若 $$\frac{1}{ad-bc}\begin{pmatrix} a & b \\ c & d \end{pmatrix}\begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}=\frac{1}{\lambda_1\lambda_2}\begin{pmatrix} ad\lambda_1-bc\lambda_2 & (\lambda_1-\lambda_2)ab \\ (\lambda_1-\lambda_2)cd & ad\lambda_2-bc\lambda_1 \end{pmatrix},$$ 是平方根矩阵的分解，那么考察主对角线以外的元素可以看出这两个平方根矩阵的大特征值必然相同，小特征值必然符号相反。

把上式中的$\lambda_1，\lambda_2$替换为$\lambda_1^2$, $\lambda_2^2$就是符合要求的矩阵，由这样的构造可以猜测两个平方根矩阵各自特征值的绝对值也都是完全平方数。

用u,v分别表示两个特征值的和与差，枚举u,v并根据上式检验整除性可得结果$145159332$。

注：因使用sympy计算约数数量以及math.lcm计算最小公倍数，以下代码为Python 3，代码中还打印了进度信息。

import math,sympy
N=10**7
M=math.isqrt(N)
tick=M//100

res=0
for u in range(1,M):
    v=u+2
    while v*v+u*u < 2*N:
        s,t,d=(v*v-u*u)//4,(v*v+u*u)//2,math.lcm(u,v)
        res+=sum(sympy.divisor_count(BC//(d*d)) for A in range(v-s,t,v) if s < A < t-s and (A-s)%u==0 and (BC:=A*(t-A)-s*s)>=0)
        v+=2   
    if u%tick==0:
        print(u//tick,"percent completed, current sum:",res)
    
print(res)