Run Time: 0.000
Ranking (as of 2015-12-14): 130 out of 467
Language: C++
/* UVa 10655 - Contemplation! Algebra To build using Visual Studio 2012: cl -EHsc -O2 UVa_10655_Contemplation_Algebra.cpp */ #include <cstdio> /* f(n) = a^n + b^n, then: f(0) = 1 f(1) = a + b f(n) = (a + b) * f(n - 1) - a * b * f(n - 2) (n >= 2) */ long long power(long long b, int e) { if (e == 0) return 1; long long p = power(b, e / 2); p *= p; if (e % 2) p *= b; return p; } int main() { while (true) { int p, q, n; if (scanf("%d %d %d", &p, &q, &n) == 2) break; long long v0 = 2, v1 = p, v; if (n == 0) v = v0; else if (n == 1) v = v1; else { if (p == 0 && q == 0) v = 0; else if (p == 0) { // f(n) = - a * b * f(n - 2) if (n % 2) v = v1 * power(-q, n / 2); else v = v0 * power(-q, n / 2); } else if (q == 0) // f(n) = (a + b) * f(n - 1) v = v1 * power(p, n - 1); else if (p == 2 && q == 1) // f(n) = f(0) v = v0; else { for (int i = 2; i <= n; i++) { v = p * v1 - q * v0; #ifdef DEBUG printf("%lld %lld %lld\n", v, v1, v0); #endif v0 = v1, v1 = v; } } } printf("%lld\n", v); } return 0; }
No comments:
Post a Comment