10-30模拟赛 | Egrecho47's Blog

「GCD」

题目描述

我们定义 $f(x)$ = gcd（ $x$ 除 $1$ 之外的所有因子）即 $x$ 除 $1$ 外所有因子的 gcd 询问

f(a) + f(a+1) + \cdots + f(b)

题解

只有形如 $p^k$ 的 $f$ 值才为 $p$ ，其他都是 $1$ 。线性筛一遍解决。

// Tags:
#include <cstdio>

const int N = 1e7 + 5;
int a, b, cnt, pri[N / 10], val[N];
bool vis[N];

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("T1.in", "r", stdin);
  freopen("T1.out", "w", stdout);
#endif
#endif

  scanf("%d%d", &a, &b);
  for (int i = 2; i <= b; ++i) {
    if (!vis[i]) {
      pri[++cnt] = i;
      long long tmp = i;
      while (tmp <= b) {
        val[tmp] = i;
        tmp *= i;
      }
    }
    for (int j = 1; j <= cnt && pri[j] * i <= b; ++j) {
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
    }
  }
  long long ans = 0;
  for (int i = a; i <= b; ++i) {
    ans += val[i] ? val[i] : 1;
  }
  printf("%lld", ans);
  return 0;
}

「小 A 的同学图」

题目描述

有 $n$ 个点，有 $m$ 条双向道路，每条边都有一个困难程度 $w_i$ 。每个点都有一个类型 $c_i$ 。多次从 $x$ 出发，每次出发后都会得到一个愉悦值 $v$ ，为在经过的边权不超过限制时能到达的点的不同种类数个数。每出发一次后限制也会增加 $1$ 。每次询问给出 $l_i, r_i$ 初始限制为 $li$ ，当限制大于 $r_i$ 时结束。求获得的愉悦值之和。

题解

我貌似用了个没人用的方法。。。

一看边权有限制，直接想到Kruskal重构树。用bitset维护每个点能到达的种类数，在树上用倍增向上跳就好了。

// Tags:
#include <algorithm>
#include <bitset>
#include <cstdio>

typedef long long ll;
const int N = 5e5 + 5, K = 6e2 + 5, BIT = 21;
int n, m, q, x, opt, M, tot, f[N << 1], fa[BIT][N << 1], val[N << 1];
std::bitset<K> bit[N << 1];
ll ans, sum[BIT][N << 1], trash;
int e_cnt, heads[N << 1];

int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

struct Edge {
  int nxt, v, w;
  Edge() {}
  Edge(int u, int v, int w) : nxt(u), v(v), w(w) {}
  inline bool operator<(const Edge &rhs) const { return w < rhs.w; }
} e[N], g[N << 1];

inline void add(int u, int v) {
  g[++e_cnt].v = v, g[e_cnt].nxt = heads[u], heads[u] = e_cnt;
}

inline void jump(int &u, int v, ll &res) {
  for (int i = BIT - 1; ~i; --i) {
    if (val[fa[i][u]] <= v) {
      res += sum[i][u];
      u = fa[i][u];
    }
  }
}

void solve(int u) {
  for (int i = heads[u], v; i; i = g[i].nxt) {
    solve(v = g[i].v);
    sum[0][v] = bit[v].count() * (val[u] - val[v]);
  }
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("T2.in", "r", stdin);
  freopen("T2.out", "w", stdout);
#endif
#endif

  scanf("%d%d%d%d%d", &n, &m, &q, &x, &opt);
  tot = n;
  if (opt) { scanf("%d", &M); }
  for (int i = 1, c; i <= n; ++i) {
    scanf("%d", &c);
    bit[i].set(c);
  }
  for (int i = 1, u, v, w; i <= m; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    e[i] = Edge(u, v, w);
  }
  for (register int i = 1, end = n << 1; i <= end; ++i) f[i] = i;
  std::sort(e + 1, e + m + 1);
  for (int i = 1, u, v; i <= m; ++i) {
    if ((u = find(e[i].nxt)) != (v = find(e[i].v))) {
      bit[++tot] |= bit[u];
      bit[tot] |= bit[v];
      val[tot] = e[i].w;
      add(tot, u), add(tot, v);
      fa[0][u] = tot, fa[0][v] = tot;
      fa[0][tot] = tot;
      f[u] = f[v] = tot;
    }
  }

  solve(tot);

  for (int i = 1, end = n << 1; i < BIT; ++i)
    for (int j = 1; j <= end; ++j) {
      sum[i][j] = sum[i - 1][j] + sum[i - 1][fa[i - 1][j]];
      fa[i][j] = fa[i - 1][fa[i - 1][j]];
    }

  for (int i = 1, l, r; i <= q; ++i) {
    scanf("%d%d", &l, &r);
    if (opt) {
      l = (l ^ ans) % M + 1;
      r = (r ^ ans) % M + 1;
      if (l > r) std::swap(l, r);
    }
    ans = 0;
    int cur = x;
    jump(cur, l, trash);
    if (r < val[fa[0][cur]]) {
      ans += (r - l + 1) * bit[cur].count();
    } else {
      ans += (val[fa[0][cur]] - l) * bit[cur].count();
      jump(cur, val[fa[0][cur]], trash);
      jump(cur, r, ans);
      ans += (r - val[cur] + 1) * bit[cur].count();
    }
    printf("%lld\n", ans);
  }
  return 0;
}

「前缀」

题目描述

咕咕咕中