SRM413 Div2 Hard

1000

memo[ n ] = n番目の数

view plainprint?

1. const int N = 2000 * 2000;  
2. lli memo[N];  
3.   
4. lli A(lli n, lli p, lli q)  
5. {  
6.   if (n < N) {  
7.     lli &ret = memo[n];  
8.     if (ret != -1) return ret;  
9.     return ret = A(n / p, p, q) + A(n / q, p, q);  
10.   }  
11.   return A(n / p, p, q) + A(n / q, p, q);  
12. }  
13.   
14. class InfiniteSequence {  
15. public:  
16.   long long calc(long long n, int p, int q)  
17.   {  
18.     fill(memo, memo + N, -1);  
19.     memo[0] = 1;  
20.     return A(n, p, q);  
21.   }  
22. };  

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);
  }
};