唉,不会线性代数了,做了三个小时。
为了求行列式,显然要先把 \(A\) 消成上三角矩阵,记作 \(A'\)。我们显然可以在操作 \(A\) 的时候求出将 \(A\) 消成 \(A'\) 的操作矩阵 \(M\),则我们可以构造 \(A'=B'C'\),再将 \(B'\) 乘上 \(M^{-1}\) 就可以得到原来的 \(B\)。
判掉 \(A\) 的行列式不是完全平方的情况,记 \(\det(A)=k^2\),则我们需要构造 \(\det(B')=k\)。\(\det (C)\) 不用特别管,因为 \(B\) 的限制满足了根据 \(\det(BC)=\det(B)\det(C)\) 就会自动满足 \(C\) 的限制。
这样直接构造还是很难构造,我们考虑让 \(B,C\) 都是上三角矩阵,这样就比较容易。令 \(B_{n,n}=\gcd(n,A_{n,n}),C_{n,n}=\frac{A_{n,n}}{B_{n,n}}\),然后递归构造 \(n-1\) 阶行列式为 \(\frac{k}{B_{n,n}}\) 的矩阵。
构造出来之后考虑 \(i\) 从大到小依次确定 \(B_{i,n}\) 和 \(C_{i,n}\) 的取值,直接模拟矩阵乘法会得到一个不定方程形如 \(B_{i,n}C_{n,n}+C_{i,n}B_{i,i}=w\),我们需要找到一组解。
直接 exgcd 可以处理 \(\gcd(B_{i,i},C_{n,n})\mid w\) 的情况,但是可以发现,\(\gcd(B_{i,i},C_{n,n})=1\)。假设其有约数 \(p\)。\(p\mid B_{i,i}\) 说明 \(p\mid \frac{k}{\gcd(k,A_{n,n})}\),而 \(p\mid C_{n,n}\) 说明 \(p\not\mid \frac{k}{\gcd(k,A_{n,n})}\),矛盾,因此其没有最大公约数。
时间复杂度 \(O(Tn^3)\),但是值域会比较大。
标签:Determinants,gcd,矩阵,det,mid,构造,frac,Matrices,QOJ From: https://www.cnblogs.com/275307894a/p/18261364