「VUSC」Math Game 题解

enucai · 2023-01-06 17:20:22 · 题解

upd 2023.1.25 修改了一处代码错误。

Analysis

令 f(x) 表示最小的满足 y^k=x 的 y 值。

考虑在没有任何删点操作时，所有 f(x) 值相同的 x 在同一个连通块内。

考虑如果删点后，在询问一个值 x 时，我们可以先找到一个最小的还存在的满足 y^k=x 的 y，那么答案就是还存在的 y^k 的数的个数。

如果我们能快速找到 y，那么这样的个数是可以暴力统计的，因为所有这样的数只有 \log n 个，我们可以枚举所有这样的数，并对被删除的数用 set 记录，每个数在 set 查询是否存在即可，单次复杂度是 O(\log n\log q)。

考虑如何找这个 y。不难发现 y 一定是 f^k(x)，所以只要知道 f(x)，那么这个 y 也是能快速找到的。

于是考虑如何快速 f(x)。设 f^k(x)=x，对 k 的大小分类讨论。

• 对于 k=2，可以在计算时直接 check x 是否是完全平方数。

• 对于 k=3，一种方法是直接计算 x^{1/3}，但是这样误差会很大。所以直接预处理出 [1,10^6] 所有数的三次方，然后每次询问 lower_bound。

• 对所有 \ge4 的 k，由于这样的 (f(x),x) 数对非常少，个数大约是 \sum\limits_{i\ge 4}\lfloor n^{1/i}\rfloor，我们可以枚举 f(x)，然后用 map 记录对于每个 x 的最小的值。

总之，单次求 f(x) 容易做到 O(\log n)，且常数很小。

综上，我们在 O(q\log n\log q) 的复杂度内在线完成了这道题，常数很小。注意查询要特判 x=1 的情况。

本题还有离线的并查集解法，此处不再赘述。

Code

const int N = 1000010;
const int V = 1000000;

ll n, val[N];
int q;
set<ll> s;
map<ll, ll> mp;

ll check(ll x) {
  int pos = lower_bound(val + 1, val + V + 1, x) - val;
  if (val[pos] == x) return pos;
  else return -1;
}

ll find(ll x) {
  if (mp.find(x) != mp.end()) return mp[x];
  else if (check(x) != -1) return check(x);
  else if ((ll)sqrtl(x) * (ll)sqrtl(x) == x) return sqrtl(x);
  else return x;
}

int calc(ll x, ll y) {
  int res = 0;
  while (x != 1) res++, x /= y;
  return res;
}

int main() {
  n = read<ll>(), q = read();
  rep (i, 1, V) val[i] = 1ll * i * i * i;
  rep (i, 2, 32000) {
    ll val = i;
    while (val <= n) {
      if (!mp.count(val)) mp[val] = i;
      if (n / val < i) break;
      val *= i;
    }
  }
  rep (i, 1, q) {
    int op = read();
    ll x = read<ll>();
    if (op == 1) {
      if (x == 1) {
        write(1), pc(10);
        continue;
      }
      map<ll, int> mp;
      ll y = find(x);
      int k = calc(x, y);
      ll tmp = 1;
      rep (i, 1, k) {
        tmp *= y;
        if (k % i == 0 && s.find(tmp) == s.end()) mp[tmp] = 1;
      }
      ll z = x, cur = 1;
      rep (i, 1, k) {
        cur *= y;
        if (k % i == 0 && s.find(cur) == s.end())
          z = min(z, cur);
      }
      y = z;
      while (y <= n) {
        if (s.find(y) == s.end()) mp[y] = 1;
        if (n / y < z) break;
        y *= z;
      }
      write(SZ(mp)), pc(10);
    } else {
      s.insert(x);
    }
  }
}