SRM413 Div2 Hard

1000

memo[ n ] = n番目の数

const int N = 2000 * 2000;
lli memo[N];

lli A(lli n, lli p, lli q)
{
  if (n < N) {
    lli &ret = memo[n];
    if (ret != -1) return ret;
    return ret = A(n / p, p, q) + A(n / q, p, q);
  }
  return A(n / p, p, q) + A(n / q, p, q);
}

class InfiniteSequence {
public:
  long long calc(long long n, int p, int q)
  {
    fill(memo, memo + N, -1);
    memo[0] = 1;
    return A(n, p, q);
  }
};