问题分析

给定 $b, d, n$，要求计算：

$$\left\lfloor \left( \frac{b + \sqrt{d}}{2} \right)^n \right\rfloor \bmod 7528443412579576937 $$

其中 $0 < b^2 \leq d < (b+1)^2 \leq 10^{18}$，$n \leq 10^{18}$。

关键数学观察

1. 共轭表达式

设：

$$x = \frac{b + \sqrt{d}}{2}, \quad y = \frac{b - \sqrt{d}}{2} $$

则 $x$ 和 $y$ 是二次方程 $t^2 - bt + \frac{b^2 - d}{4} = 0$ 的根。

2. 整数序列构造

定义序列：

$$a_n = x^n + y^n$$

可以证明 $a_n$ 是整数序列，满足递推关系：

$$a_n = b \cdot a_{n-1} + \frac{d - b^2}{4} \cdot a_{n-2} $$

初始条件：

$$a_0 = 2, \quad a_1 = b$$

3. 与目标表达式的关系

由于 $|y| < 1$（由 $d < (b+1)^2$ 保证），我们有：

当 $n$ 为偶数时：$y^n > 0$，所以 $\lfloor x^n \rfloor = a_n - 1$ 当 $n$ 为奇数时：$y^n < 0$，所以 $\lfloor x^n \rfloor = a_n$

特殊情况：当 $b^2 = d$ 时，$y = 0$，此时 $\lfloor x^n \rfloor = a_n$

算法实现

矩阵快速幂

使用矩阵快速幂计算 $a_n$：

$$\begin{bmatrix} a_n \\ a_{n-1} \end{bmatrix} = \begin{bmatrix} b & \frac{d-b^2}{4} \\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} a_1 \\ a_0 \end{bmatrix} $$

代码解析

typedef __int128 i128;  // 用于中间计算，避免溢出
const LL MOD = 7528443412579576937;

矩阵定义和快速幂实现：

struct Matrix {
    LL a[2][2];
    Matrix operator *(Matrix b) {
        Matrix res;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    res.a[i][j] = (res.a[i][j] + (i128)a[i][k] * b.a[k][j]) % MOD;
        return res;
    }
    Matrix operator ^(LL b) {
        // 快速幂实现
    }
};

主计算逻辑：

LL b, d, n;
scanf("%lld%lld%lld", &b, &d, &n);

if (n == 0) {
    printf("1\n");
    return 0;
}

// 构建转移矩阵
Matrix C;
C.a[0][0] = b;
C.a[0][1] = (d - b * b) / 4;
C.a[1][0] = 1;
C.a[1][1] = 0;

// 初始向量 [a1, a0] = [b, 2]
Matrix A;
A.a[0][0] = b;
A.a[0][1] = 2;

// 计算 a_n
Matrix result = A * (C ^ (n - 1));
LL an = result.a[0][0];

// 调整结果
LL answer;
if (n % 2 == 0 && b * b != d) {
    answer = (an - 1 + MOD) % MOD;
} else {
    answer = an;
}

printf("%lld\n", answer);

复杂度分析

时间复杂度：$O(\log n)$，主要来自矩阵快速幂 空间复杂度：$O(1)$，只使用固定大小的矩阵

样例验证

输入：$b = 1, d = 5, n = 9$

计算过程： $x = \frac{1 + \sqrt{5}}{2}$（黄金比例） $a_9$ 是卢卡斯序列的第9项 最终结果：$76$

模运算技巧

模数 $7528443412579576937$ 是一个质数，在计算中使用 __int128 来避免中间结果溢出。

总结

本题通过将无理数幂次问题转化为整数序列问题，利用矩阵快速幂在 $O(\log n)$ 时间内求解。关键在于发现 $x^n + y^n$ 是整数序列这一性质，以及正确处理取整函数的边界情况。