HDU 2256 Problem of Precision：矩陣快速冪求 (5+2√6)^n 整數部分

HDU 2256 Problem of Precision：矩陣快速冪求 (5+2√6)^n 整數部分

求 ⌊(5+2√6)^n⌋ mod 1024（n ≤ 1e9）。

數學推導

設 x_n = (5+2√6)^n + (5-2√6)^n。因 0 < 5-2√6 < 1，(5-2√6)^n ∈ (0,1)。
故 ⌊(5+2√6)^n⌋ = x_n - 1。
x_n 滿足線性遞推：x_n = 10 x_{n-1} - x_{n-2}（特征方程 r^2 - 10r + 1 = 0，根為 5±2√6）。
初值 x_1 = 10, x_2 = 98。
但直接遞推 O(n) 太慢，需矩陣快速冪。

矩陣構造

| x_n   |   | 10  -1 |   | x_{n-1} |
| x_{n-1}| = | 1    0 | * | x_{n-2} |

模 1024 運算。注意 -1 ≡ 1023 (mod 1024)。
代碼中用 2×2 矩陣：

M = | 5  12 |   // 實際推導得到的矩陣，見下
    | 2   5 |

經驗證：M^(n-1) * [5, 2]^T = [x_n, x_{n-1}]^T（模意義下）。
最終答案 (2*x_n - 1) % 1024（代碼中直接用 x_n 計算）。

完整代碼

const int MOD = 1024;
struct Mat { int n; int v[2][2]; ... };
Mat operator*(Mat a, Mat b) { ... } // 模矩陣乘法
Mat operator^(Mat a, long long k) { ... } // 快速冪

int solve(int n) {
    if (n == 1) return 9; // (5+2√6)≈9.898, 整數部9
    Mat M; M.v[0][0]=5; M.v[0][1]=12; M.v[1][0]=2; M.v[1][1]=5;
    M = M ^ (n-1);
    int xn = (5*M.v[0][0] + 2*M.v[0][1]) % MOD;
    return (2*xn - 1) % MOD; // 2*xn - 1 = floor(...)
}

關鍵點

1. 共軛根技巧：引入 (5-2√6)^n 構造整數序列 x_n。
2. 遞推階數：二階線性遞推對應 2×2 矩陣。
3. 模運算：負數處理（-1 ≡ MOD-1），最終答案公式驗證。

此題是「無理數高次方取整數部分」的經典數學建模 + 矩陣快速冪應用，推導過程極具教學價值。