自动搬运

查看原文

来自洛谷，原作者为

	enucai Remake.

搬运于2025-08-24 22:44:03，当前版本为作者最后更新于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);
    }
  }
}