UVa 11133 - Eigensequence

Accepted date: 2016-11-15
Run Time: 0.000
Ranking (as of 2016-11-15): 26 out of 402
Language: C++

/*
  UVa 11133 - Eigensequence

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11133_Eigensequence.cpp
*/

#include <cstdio>

const int an_max = 44;
int nr_ess[an_max + 1][an_max + 1];
  // nr_ess[i][j] is the number of eigensequences that start with i and end with j

int eigensequence(int a1, int an)
{
  int& nr = nr_ess[a1][an];
  if (nr == -1) {
    nr = 0;
    for (int i = 1; i <= an - a1; i++)
      if (!(a1 % i))
        nr += eigensequence(a1 + i, an);
  }
  return nr;
}

int main()
{
  while (true) {
    int a1, an;
    scanf("%d %d", &a1, &an);
    if (a1 >= an)
      break;
    for (int i = a1; i <= an; i++)
      for (int j = a1; j <= an; j++)
        nr_ess[i][j] = (i == j) ? 1 : ((i > j) ? 0 : -1);
    printf("%d %d %d\n", a1, an, eigensequence(a1, an));
  }
  return 0;
}