首先，看到\((\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;
}原文：https://www.cnblogs.com/fushao2yyj/p/9513721.html