[ECNU] EOJ Monthly 2021.9 Sponsored by TuSimple A. Amazing Discovery
https://acm.ecnu.edu.cn/contest/448/problem/A/
\[a + k\sqrt b \Rightarrow (a+k\sqrt b) \cdot (A+K\sqrt b)= aA+kKb+(aK+kA)\sqrt b \]
#include
using namespace std;
typedef long long ll;
ll a, b, n;
const int mod = 998244353;
namespace nekko {
struct owo {
ll a, k;
// a + ksqrt b -> (a+ksb)*(A+Ksb)= aA+kKb+(aK+kA)sb
} I = { 1, 0 };
owo mul(owo a, owo b) {
return (owo) { (a.a * b.a % mod + a.k * b.k % mod * :: b % mod) % mod, (a.a * b.k % mod + a.k * b.a % mod) % mod };
}
owo pw(owo a, ll b) {
owo res = I;
for( ; b ; b >>= 1, a = mul(a, a)) {
if(b & 1) {
res = mul(res, a);
}
}
return res;
}
void main() {
cin >> a >> b >> n;
owo p = (owo) {a, 1}; p = mul(p, p); p = mul(p, I);
ll S = pw((owo) {a, 1}, n).a + pw((owo) {a, -1}, n).a;
cout << (S % mod + mod) % mod << endl;
}
}
int main() {
nekko :: main();
}