提出 #65380696

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
template <typename T>
using vc = vector<T>;

#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

// solution 1. SegTree.

void solve() {
  ll N = 1 << 22;
  vc<int> dat(N + N);
  vc<bool> exist(N);
  auto upd = [&](int i) -> void { dat[i] = dat[2 * i] + dat[2 * i + 1]; };
  auto rm_single = [&](int i) -> void {
    exist[i] = 0;
    i += N;
    dat[i] = 0;
    while (i > 1) i /= 2, upd(i);
  };
  auto rm_mul = [&](int a) -> void {
    if (a >= N || !exist[a]) return;
    for (int i = a; i < N; i += a) {
      if (exist[i]) rm_single(i);
    }
  };
  auto find = [&](int k) -> int {
    // (1+k)-th element. (配列の [k]と同じ)
    auto rec = [&](auto& rec, int idx, int l, int r) -> int {
      if (r - l == 1) return l;
      int m = (l + r) / 2;
      int a = 2 * idx + 0, b = 2 * idx + 1;
      if (k < dat[a]) return rec(rec, a, l, m);
      k -= dat[a];
      return rec(rec, b, m, r);
    };
    return rec(rec, 1, 0, N);
  };

  // initialize
  FOR(i, 1, N) dat[N + i] = 1, exist[i] = 1;
  FOR_R(i, 1, N) upd(i);

  ll Q;
  cin >> Q;
  FOR(Q) {
    int a, b;
    cin >> a >> b;
    rm_mul(a);
    int ans = find(b - 1);
    cout << ans << "\n";
  }
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve();
}

提出情報

ジャッジ結果