蠻力不適用於此矩陣

Question

在2X2矩陣中，我們如何找到矩陣的數量，使得軌跡爲N，行列式爲正，所有條目也爲正數。因此，如果矩陣是如此d = N-a並且行列式爲正，那麼我們如何有效地計算對（a，b）的數量，使得a * b < = n其中n的範圍從1到N-1？

Answer 1

假設我們具有矩陣m={{a,b},{c,d}}，那麼我們有：

• trace(m) = N => a+d = N => d = N - a
• det(m) >= 0 => a*d - b*c >= 0 => a*(N-a) >= b*c

因此，對於任意的而非固定的a < N我們可以計算d=N-a，q:=a*(N-a)和僅具有約束還剩下b*c <= q。

現在，如果元素可以是實數，您可以通過選擇b > 0和計算c = q/b來獲得無限的解決方案。

如果元素應該是整數，則必須找到(b,c)這樣的b*c <= q。你會發現所有的解決方案如下：

• 選擇0 < b <= q
• 計算cmax=floor(q/b)（其中地板向下取整）
• 所有對(b,1), ..., (b,cmax)是可能的解決

總數：

for(int a=1; a<N; a++) { 
    int q = a*(N-a); 
    for(int b=1; b<=q; b++) { 
     int cmax = floor(q/b); 
     for(int c=1; c<=cmax; c++) { 
      std::cout << "(a,b,c,d)=" << a << "," << b << "," << c << "," << N-a << std::endl; 
     } 
    } 
}