## 【UVA-10655】Contemplation! Algebra【矩阵快速幂】

【UVA-10655】Contemplation! Algebra【矩阵快速幂】

Solution:

$$(a + b)(a + b) – 2ab = a^2 + b^2$$

$$(a^2 + b^2)(a + b) – (a + b)ab = a^3 + b^3$$

$$(a^3 + b^3)(a + b) – (a^2 + b^2)ab = a^4 + b^4$$

……

$$(^{a^n + b^n}_{a^{n – 1} + b^{n – 1}}) = (^{a + b}_1$$      $$^{-ab}_0) ^{n – 1}(^{a + b}_{2})$$

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
const int LIM = 2;
struct Matrix {
LL v[LIM][LIM];
Matrix operator * (const Matrix & m) const {
Matrix ret = {0};
for (int i = 0; i < LIM; i++) {
for (int k = 0; k < LIM; k++) {
if (v[i][k])
for (int j = 0; j < LIM; j++) {
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]);
}
}
}
return ret;
}
};
// p = a + b, q = ab
LL p, q, n;
Matrix base;

void build() {
base.v[0][0] = p;
base.v[0][1] = -q;
base.v[1][0] = 1;
base.v[1][1] = 0;
}

Matrix fastPow(LL p, Matrix m) {
Matrix ret = {0};
for(int i = 0; i < LIM; i++) ret.v[i][i] = 1;
while (p) {
if (p & 1) ret = ret * m;
if (p) m = m * m;
p >>= 1;
}
return ret;
}

int main() {
while (scanf("%lld%lld%lld", &p, &q, &n) == 3 && (p || q || n)) {
if (n == 0) printf("2\n");
else if (n == 1) printf("%lld\n", p);
else {
build();
Matrix trans = fastPow(n - 1, base);
printf("%lld\n", trans.v[0][0] * p + trans.v[0][1] * 2);
}
}
return 0;
}