Description

B 君有两个好朋友, 他们叫宁宁和冉冉. 有一天, 冉冉遇到了一个有趣的题目: 输入 \(b, d, n\), 求:

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

Input

一行三个整数 \(b, d, n\);

Output

一行一个数表示模 \(7528443412579576937\) 之后的结果.

Sample Input

1 5 9

Sample Output

76

Data Range

对于所有的数据, 满足:\(0 \lt b^2 \leq d \lt (b+1)^2 \leq 10^{18}, n \leq 10^{18}\);

同时所有数据满足:\(b \bmod 2 = 1, d \bmod 4 = 1\)

Explanation

应该是一道构造数列的题目, 构造完毕以后用矩阵快速幂优化即可~

顺便吐槽一下不开 unsigned long long 见祖宗这件事还是头一次遇到......

神犇题解 (传送门:http://blog.csdn.net/popoqqq/article/details/45148309)

构造数列 \(a_n = b \cdot a_{n-1} + \frac{d-b^2}{4} \cdot a_{n-2}\);

其中 \(a_0 = 2, a_1 = b\)

然后我们求出这个数列的通项公式, 得到 \((\frac{b+\sqrt{d}}{2})^n = a_n - (\frac{b-\sqrt{d}}{2})^n\)

由于 \(b \bmod 2 = 1, d \bmod 4 = 1\), 因此 \(\frac{d-b^2}{4}\) 一定是个正整数, 故我们可以利用矩阵乘法来求出这个数列的第 \(n\) 项

然后对于 80% 的数据 \(b_2 \leq d \lt (b+1)^2\), 对于 20% 的数据 \(b = 1, d = 5\), 因此 \(\frac{b-\sqrt{d}}{2} \in (-1, 0]\)

进一步可以用矩阵乘法瞎搞即可.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef unsigned long long lli;
const lli modr = 7528443412579576937ull;

lli fast_mul(lli a, lli b)
{
    lli res = 0;
    for (a %= modr; b > 0; b >>= 1, a = (a + a) % modr)
        if (b & 1) res = (res + a) % modr;
    return res;
}

class matrix
{
public:
    lli dat[2][2];
    matrix(void)
    {
        dat[0][0] = dat[0][1] = 0ll;
        dat[1][0] = dat[1][1] = 0ll;
        return ;
    }
    matrix(lli v)
    {
        dat[0][0] = dat[1][1] = v;
        dat[0][1] = dat[1][0] = 0ll;
        return ;
    }
    matrix(lli a, lli b, lli c, lli d)
    {
        dat[0][0] = a; dat[0][1] = b;
        dat[1][0] = c; dat[1][1] = d;
        return ;
    }
};

matrix operator * (matrix a, matrix b)
{
    matrix c;
    c.dat[0][0] = (fast_mul(a.dat[0][0], b.dat[0][0]) + fast_mul(a.dat[0][1], b.dat[1][0])) % modr;
    c.dat[0][1] = (fast_mul(a.dat[0][0], b.dat[0][1]) + fast_mul(a.dat[0][1], b.dat[1][1])) % modr;
    c.dat[1][0] = (fast_mul(a.dat[1][0], b.dat[0][0]) + fast_mul(a.dat[1][1], b.dat[1][0])) % modr;
    c.dat[1][1] = (fast_mul(a.dat[1][0], b.dat[0][1]) + fast_mul(a.dat[1][1], b.dat[1][1])) % modr;
    return c;
}

matrix operator ^ (matrix a, lli b)
{
    matrix res = 1;
    for (; b > 0; b >>= 1, a = a * a)
        if (b & 1) res = res * a;
    return res;
}

lli b, d, n;

int main(int argc, char** argv)
{
    scanf("%lld%lld%lld", &b, &d, &n);
    lli A = b, B = (d - b * b) / 4;
    matrix wrk(0, 1, B, A);
    matrix mat(2, 0, b, 0);
    lli F = 0;
    if (b * b != d && n % 2 == 0)
        F = 1;
    lli res = ((wrk ^ n) * mat).dat[0][0] - F;
    res = res + modr % modr;
    printf("%lld\n", res);
    return 0;
}