[Q] https://atcoder.jp/contests/arc068/tasks/arc068_c

解説AC。
級数の項数は、思ったより少ないという感覚が迷子。

M=100000

100000 / 1 +
100000 / 2 +
100000 / 3 +
...
100000 / 100000 = 1166750

項数の総和は、1166750。
たったの！

1. dを1からMまで走査する。

2. 級数の項の総数は、せいぜい100*10000くらいとわかっているので、それ全探索。
3. 重複してカウントアップしたくないのが、一番の問題。

4. クエリの幅に注目する。R-L+1 >= dなら、鳩ノ巣原理っぽい考えで、絶対にdの倍数が踏むはず。幅がd以上のクエリは1回と見込めばいい。
5. クエリは幅(D)の小さい順にソートして、d未満のものだけBITに収納していけばいい。

実装

template <ll BT>
struct Bit {
 ll dat[BT + 10]{};

 void add(ll i, ll x) {
   ++i;
   for (; i < BT; i += i & -i) dat[i] += x;
 }
 ll sum(ll i) {
   ++i;
   ll res = 0;
   for (; i > 0; i -= i & -i) res += dat[i];
   return res;
 }
 ll rangesum(ll L, ll R) {  // ??
   return sum(R) - sum(L - 1);
 }
};

// --------------------------------------------------

ll N, M;
int main() {
 cincout();

 cin >> N >> M;
 vector<tuple<ll, ll, ll>> V(N);
 rep(i, N) {
   auto &[d, L, R] = V[i];
   cin >> L >> R;
   d = R - L + 1;
 }
 sort(all(V));

 Bit<100010> bits;
 ll pos = 0;
 ll add = N;

 // 1
 cout << N << endl;
 for (ll d = 2; d <= M; ++d) {
   while (pos < N) {
     auto &[D, L, R] = V[pos];
     if (D >= d) break;
     --add;
     bits.add(L, 1);
     bits.add(R + 1, -1);
     ++pos;
   }
   ll ret = add;
   for (ll i = d; i <= M; i += d) {
     ret += bits.sum(i);
   }
   cout << ret << endl;
 }
}

https://atcoder.jp/contests/arc068/submissions/30949184