UVa 10655 - Contemplation! Algebra

Accepted date: 2015-12-11
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;
}