naoya_t@topcoder

SRM388 Div1 Easy: SmoothNumbers

過去問, 練習 | 11:59 |

最初は上(N)から攻めていたが下(1)からに変更。

class SmoothNumbers {
  int N_;
  vector<int> primes;
  vector<bool> memo;

  void sub(int n){
    tr(primes,it){
      int np = *it * n;
      if (np>N_) continue;
      if (!memo[np]) { sub(np); memo[np]=true; }
    }
  }
public:
  int countSmoothNumbers(int N, int k) {
    N_=N;
    int primes_[25] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                       31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
                       73, 79, 83, 89, 97 };
    memo.resize(N+1); fill(all(memo),false);
    memo[1]=true;
    rep(i,25) {
      int p=primes_[i]; 
      if(p<=k) primes.pb(p);
      else break;
    }
    sub(1);
    int cnt=0; for(int i=1;i<=N;i++) if(memo[i]) cnt++;
    return cnt;
  }
};