説明

毎回困るので

自然数 $N$ が与えられる。このとき商 ($\lfloor \frac N i \rfloor$) ($1 \leq i \leq N$) の値の種類数は $O(\sqrt N)$ 個で抑えられる。

特に $\lfloor \frac N i \rfloor = k$ となる最左の $i$ を $l$, 最右の $i$ を $r$ とする。このとき $[l, r]$ で $\frac N i$ の余りを並べると等差数列になっている。

計算量

  • $O(\sqrt N)$

実装例

  • quotient_range($N$):= 戻り値の各要素を {{$x$,$y$},$z$} とする。$x \leq i \leq y$ を満たす整数の商($\lfloor \frac N i \rfloor$) が $z$ であることを意味する。$x$ の昇順で返す。
template< typename T >
vector< pair< pair< T, T >, T > > quotient_range(T N) {
  T M;
  vector< pair< pair< T, T >, T > > ret;
  for(M = 1; M * M <= N; M++) {
    ret.emplace_back(make_pair(M, M), N / M);
  }
  for(T i = M; i >= 1; i--) {
    T L = N / (i + 1) + 1;
    T R = N / i;
    if(L <= R && ret.back().first.second < L) ret.emplace_back(make_pair(L, R), N / L);
  }
  return ret;
}

検証

AtCoder Beginner Contest 132 F - Small Products

int main() {
  int N, K;
  cin >> N >> K;
  auto range = quotient_range(N);

  vector< modint > dp(range.size());
  dp[0] = 1;
  for(int i = 0; i < K; i++) {
    reverse(begin(dp), end(dp));
    vector< modint > dp2(range.size());
    modint add = 0;
    for(int j = range.size() - 1; j >= 0; j--) {
      add += dp[j];
      dp2[j] = add * (range[j].first.second - range[j].first.first + 1);
    }
    dp.swap(dp2);
  }
  modint ret;
  for(auto &t : dp) ret += t;
  cout << ret << endl;
}