据说这两场加起来只要170= =而这是最简单的题目了QAQ
看到$(\frac {b + \sqrt {d} } {2} )^n$，第一反应是共轭根式$(\frac {b - \sqrt {d} } {2} )^n$
首先有$(\frac {b + \sqrt {d} } {2} )^n + (\frac {b - \sqrt {d} } {2} )^n$为整数
由高中课本知识可知，上式其实是一个三项递推数列的通项公式，而数列的递推式非常简单
$$f[x] = b * f[x - 1] - \frac{b^2 - d} {4} * f[x - 2]$$
其中$f[0] = 2, f[1] = b$，这样子直接矩阵乘法就好啦~
再看$A = (\frac {b - \sqrt {d} } {2} )^n \in [-1, 1]$
然后。。。然后发现bzoj上题面错了QAQ，实际上是"对于20%的数据$b=1,d=5$"
故$A > 0$当且仅当$d \not= b^2$且$n$为偶数，此时要将$f[n]$减掉$1$，否则不用减
/**************************************************************
Problem: 4002
User: rausen
Language: C++
Result: Accepted
Time:48 ms
Memory:1272 kb
****************************************************************/ #include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm> using namespace std;
typedef unsigned long long ll;
const ll mod = 7528443412579576937ull; template <class T> T sqr(T x) {
return x * x;
} template <class T> T mul(T x, T y) {
static T res;
if (x < y) swap(x, y);
res = ;
while (y) {
if (y & ) res = (res + x) % mod;
x = (x << ) % mod, y >>= ;
}
return res;
} ll b, d, n; struct mat {
ll x[][]; inline void clear() {
memset(x, , sizeof(x));
}
inline void one() {
memset(x, , sizeof(x));
x[][] = x[][] = ;
}
inline void pre() {
this -> clear();
x[][] = , x[][] = (d - sqr(b)) >> , x[][] = , x[][] = b;
} inline ll* operator [] (int i) {
return x[i];
} inline mat operator * (const mat &p) const {
static mat res;
static int i, j, k;
for (res.clear(), i = ; i <= ; ++i)
for (j = ; j <= ; ++j)
for (k = ; k <= ; ++k)
res[i][j] = (res[i][j] + mul(x[i][k], p.x[k][j])) % mod;
return res;
}
inline mat& operator *= (const mat &p) {
return *this = *this * p;
}
} a; inline mat pow(const mat &p, ll y) {
static mat x, res;
res.one(), x = p;
while (y) {
if (y & ) res *= x;
x *= x, y >>= ;
}
return res;
} int main() {
cin >> b >> d >> n;
a.pre();
a = pow(a, n);
cout << (((a[][] << ) % mod + mul(b, a[][]) - (d != sqr(b) && !(n & ))) % mod + mod) % mod << endl;
return ;
}