HDU 4565 So Easy!：共軛根技巧 + 矩陣快速冪求模數列

問題描述

給定整數 a, b, n, m，求 S_n = (a + √b)^n + (a - √b)^n (mod m)。其中 n ≤ 10^18，m ≤ 10^9。

數學轉換：共軛根構造遞推

設 α = a + √b, β = a - √b。則 α + β = 2a, αβ = a^2 - b。
S_n = α^n + β^n 滿足二階線性遞推：

S_0 = 2
S_1 = 2a
S_n = (α+β) S_{n-1} - αβ S_{n-2} = 2a S_{n-1} - (a^2-b) S_{n-2}

寫成矩陣形式：

[ S_n   ]   [ 2a   -(a^2-b) ] [ S_{n-1} ]
[ S_{n-1} ] = [  1       0    ] [ S_{n-2} ]

即 M = [[2a, b-a^2], [1, 0]]，則 [S_n, S_{n-1}]^T = M^{n-1} * [S_1, S_0]^T（n≥2）。

矩陣快速冪取模

2×2 矩陣乘法 O(1)，快速冪 O(log n)。注意 b-a^2 可能為負，取模時加 m 再模。

特殊情況處理

• n=1：輸出 S_1 = 2a mod m。
• n=2：S_2 = (2a)^2 - 2(a^2-b) = 2a^2+2b，或直接用公式 ceil((a+√b)^2) 取模（代碼中用 double 近似再 ceil，風險較大，建議用遞推公式）。

完整代碼

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct Mat {
    int64 a[2][2];
    Mat(int64 d=0) { a[0][0]=a[1][1]=d; a[0][1]=a[1][0]=0; }
    Mat operator*(const Mat& o) const {
        Mat r;
        r.a[0][0] = (a[0][0]*o.a[0][0] + a[0][1]*o.a[1][0]) % mod;
        r.a[0][1] = (a[0][0]*o.a[0][1] + a[0][1]*o.a[1][1]) % mod;
        r.a[1][0] = (a[1][0]*o.a[0][0] + a[1][1]*o.a[1][0]) % mod;
        r.a[1][1] = (a[1][0]*o.a[0][1] + a[1][1]*o.a[1][1]) % mod;
        return r;
    }
};
int64 mod;

Mat mpow(Mat base, int64 exp) {
    Mat res(1); // identity
    while (exp) {
        if (exp & 1) res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64 a, b, n;
    while (cin >> a >> b >> n >> mod) {
        if (n == 1) { cout << (2*a % mod + mod) % mod << "\n"; continue; }
        if (n == 2) { 
            int64 s2 = (2*a*a % mod + 2*b % mod) % mod;
            cout << (s2 % mod + mod) % mod << "\n"; continue; 
        }
        Mat M;
        M.a[0][0] = (2*a) % mod;
        M.a[0][1] = (b - a*a) % mod;
        M.a[1][0] = 1;
        M.a[1][1] = 0;
        Mat R = mpow(M, n-2);
        int64 S1 = (2*a) % mod;
        int64 S0 = 2 % mod;
        int64 Sn = (R.a[0][0]*S1 + R.a[0][1]*S0) % mod;
        cout << (Sn + mod) % mod << "\n";
    }
    return 0;
}

關鍵點總結

1. 共軛根消根號：利用 α, β 為方程 x^2 - 2a x + (a^2-b)=0 的根，構造整數遞推。
2. 矩陣快速冪：將二階遞推提升為矩陣乘冪，O(log n) 求巨大 n 項。
3. 模運算細節：負數模加 mod 保證非負；n=1,2 直接用初值避免矩陣冪 0 次邊界。
4. 精度陷阱：原代碼用 double 近似 S_2，大數時會誤差；純整數遞推更穩健。

複雜度

• 每測試用例 O(log n) 矩陣乘法，極快。

本題是「特徵根/共軛根 + 矩陣快速冪」解決含根號線性遞推的經典範例，展示了如何將無理數問題轉化為整數模運算。