洛谷

首先，看到\((\frac{(b+\sqrt{d})}{2})^n\)，很快能够想到一元二次方程的解\(\frac{-b\pm\sqrt{\Delta}}{2a}\)。

所以可以推出，\(\frac{(b+\sqrt{d})}{2}\)和\(\frac{(b-\sqrt{d})}{2}\)是\(x^2-bx+\frac{b^2-d}{4}\)的解。

方程移项得：\(x^2=b^2+\frac{d-b^2}{4}\)。

所以设\(f[i]=(\frac{b+\sqrt{d}}{2})^i+(\frac{b-\sqrt{d}}{2})^i\)。

数据范围已经提示b mod 2=1,d mod 4=1，所以f[i]肯定整数。

所以可以列出递推式：\(f[i]=bf[i-1]+\frac{d-b^2}{4}f[i-2]\)。

然后草稿纸上画一画可得：f[0]=2,，f[1]=b。

注意模数7528443412579576937巨大，乘的时候要用慢速乘或快速乘。

这时候我们考虑如何从f[n]推出ans。

由题易得：\(b^2<d<(b+1)^2\)，所以有两种情况：

第1种：n为奇数。\(-1<(\frac{b-\sqrt{d}}{2})^n<0\)。

第2种：n为偶数。\(0\leq(\frac{b-\sqrt{d}}{2})^n<1\)。

所以当\(b^2!=d\)，且n为偶数时，答案为f[n]-1，否则就是f[n]。

最后只要把上面递推式转化成矩阵，再快速幂就A了。

code：

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const ull m=7528443412579576937;

ull b,d,n,p,f[3]={0,2},t[3][3]={

{0,0,0},

{0,0,0},

{0,1,0}

};

ull ans;

ull suan(ull x,ull y)

{

    ull d=0;

    while (y) {

        if (y&1) d=(d%m+x%m)%m;

        x=(x%m+x%m)%m,y>>=1;

    }

    return d%m;

}

void fuyan()

{

    ull d[3];

    memcpy(d,f,sizeof(d));

    memset(f,0,sizeof(f));

    for (int i=1;i<=2;++i)

        for (int j=1;j<=2;++j)

            f[i]=(f[i]%m+suan(d[j]%m,t[j][i]%m))%m;

}

void yuzhouzhou()

{

    ull d[3][3];

    memcpy(d,t,sizeof(d));

    memset(t,0,sizeof(t));

    for (int i=1;i<=2;++i)

        for (int j=1;j<=2;++j)

            for (int k=1;k<=2;++k)

                t[i][j]=(t[i][j]%m+suan(d[i][k]%m,d[k][j]%m))%m;

}

int main()

{

    cin>>b>>d>>n;

    p=n;

    f[2]=b;

    t[1][2]=(d-b*b)/4;

    t[2][2]=b;

    if (n==0) cout<<"1";

    else {

        --n;

        while (n) {

            if (n&1) fuyan();

            yuzhouzhou();n>>=1;

        }

        ans=f[2];

        if (b*b!=d&&p%2==0) --ans;

        if (ans<0) ans+=m;

        cout<<ans;

    }

    return 0;

}