LibreOJ 6076 「2017 山东一轮集训 Day6」三元组

发表于 | 分类于

Description

给定正整数\(a,b,c\)，求： \[ \sum_{i = 1}^a\sum_{j = 1}^b\sum_{k = 1}^c [i\perp j][i\perp k][j\perp k] \] \(a,b,c\leq 5\times 10^5\)。

Solution

下面钦点\(a\leq b\leq c\)。 \[ \begin{aligned} \quad&\sum_{i = 1}^a\sum_{j = 1}^b\sum_{k = 1}^c [i\perp j][j\perp k][i\perp k]\\ =&\sum_{i = 1}^a\sum_{j = 1,j\perp i}^b\sum_{k = 1,k\perp i}^c [j\perp k]\\ =&\sum_{i = 1}^a\sum_{j = 1,j\perp i}^b\sum_{k = 1,k\perp i}^c \sum_{d | j, d | k}\mu(d)\\ =&\sum_{i = 1}^a\sum_{d = 1, d\perp i}^b \mu(d)S_i(\lfloor\frac{b}{d}\rfloor)S_i(\lfloor\frac{c}{d}\rfloor) \end{aligned} \] 其中\(S_a(n)\)表示\([1, n]\)中和\(a\)互质的正整数数量。

后面那一块很显然可以整除分块罢……然后接下来我们需要考虑处理\([1, n]\)中和\(a\)互质的数的\(\mu\)和\(1\)的和，这个东西很显然可以用洲阁筛/Min_25筛的思想。考虑将\(i\)质因数分解为，其质因子有\(p_1, p_2,\ldots, p_k\)。定义状态\(f_i(n)\)表示\([1, n]\)中和前\(i\)个质因子互质的\(\mu\)的和，类似的用\(g_i(n)\)表示\(1\)的和。那么转移很显然是： \[ f_i(n) = f_{i - 1}(n) + f_i(\lfloor\frac{n}{p_i}\rfloor)\\ g_i(n) = g_{i - 1}(n) - g_{i - 1}(\lfloor\frac{n}{p_i}\rfloor) \] 考虑到状态全部是\(\lfloor\frac{n}{x}\rfloor\)的形式，所以我们要是对每个\(i\)都这么做一遍的话，每个\(i\)的总状态数（也是时间复杂度）就是\(O(\omega(i)\sqrt{i})\)。因此总的复杂度大约就是\(O(n\sqrt{n}\log n)\)，并且还很不满，看起来很稳是不是啊……

然后我直接写了一个东西交上去，然后T到60……卡了卡常之后T到了80……

然后注意到如果两个\(i\)的质因子构成是完全一致的话，那么他们对答案的贡献也就一样……所以我们再额外对这个东西记忆化一下，然后就能卡过去了。这之后有没有一个可以推出来的更紧的上界，我就不知道了……有没有先辈会算这个啊……有的话麻烦在评论区书一下qwq

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <functional>
#include <utility>
#include <unordered_map>
#include <map>
#include <stack>
const int N = 50005;
int mu[N + 1], minp[N + 1];
int prm[N + 1]; bool vis[N + 1];
void sieve() {
  int cnt = 0;
  mu[1] = 1; minp[1] = 1; vis[1] = true;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      mu[i] = -1; minp[i] = i;
      prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt; j ++) {
      int v = i * prm[j];
      if(v > N) break;
      vis[v] = true; minp[v] = prm[j];
      if(i % prm[j] == 0) {
        mu[v] = 0; break;
      } else {
        mu[v] = -mu[i];
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    mu[i] += mu[i - 1];
  }
}

using ll = long long;
using ull = unsigned long long;
const ll ha = 1000000007LL;
const int maxn = 50005;
int p[16], pcnt;
const int INF = 0x7f7f7f7f;
int ma[16][maxn]; int st1[16][maxn], top1[16];
int calc_S(int c, int n) {
  if(c == 0) return n;
  if(n == 0) return 0;
  if(ma[c][n] != INF) return ma[c][n];
  st1[c][top1[c] ++] = n;
  int ret = (calc_S(c - 1, n) - calc_S(c - 1, n / p[c]));
  ma[c][n] = ret;
  return ret;
}
int ma_mu[16][maxn]; int st2[16][maxn], top2[16];
int calc_mu(int c, int n) {
  if(c == 0) return (mu[n]);
  if(n == 0) return 0;
  if(ma_mu[c][n] != INF) return ma_mu[c][n];
  st2[c][top2[c] ++] = n;
  int ret = (calc_mu(c - 1, n) + calc_mu(c, n / p[c]));
  ma_mu[c][n] = ret;
  return ret;
}

ll sqr(ll x) {
  ll ret = 1;
  while((ret + 1LL) * (ret + 1LL) <= x) ret ++;
  return ret;
}
const ull seed = 200261ULL;
int main() {
  sieve();
  int a, b, c; scanf("%d%d%d", &a, &b, &c);
  if(a > b) std::swap(a, b);
  if(a > c) std::swap(a, c);
  if(b > c) std::swap(b, c);
  static int rec[50005];
  memset(rec, -1, sizeof(rec));
  memset(ma, 0x7f, sizeof(ma));
  memset(ma_mu, 0x7f, sizeof(ma_mu));
  ll ans = 0;
  for(int i = 1; i <= a; i ++) {
    pcnt = 0;
    int u = i;
    while(u > 1) {
      int tp = minp[u]; p[++ pcnt] = tp;
      while(u % tp == 0) u /= tp;
    }
    int hs = 1;
    for(int i = 1; i <= pcnt; i ++) {
      hs *= p[i];
    }
    if(rec[hs] != -1) {
      ans = (ans + (ll)rec[hs]) % ha;
      continue;
    }
    ll las = 0, ret = 0LL;
    for(int j = 1; j <= b;) {
      int next = std::min(b / (b / j), c / (c / j));
      ll th = calc_mu(pcnt, next);
      // th = (th + ha) % ha;
      ll delta = (th - las + ha) % ha;
      delta = (delta * (ll)calc_S(pcnt, b / j));
      delta = (delta * (ll)calc_S(pcnt, c / j)) % ha;
      ret = (ret + delta);
      if(ret > ha) ret -= ha;
      las = th; j = next + 1;
    }
    for(int j = 1; j <= pcnt; j ++) {
      while(top1[j] > 0) {
        int p = st1[j][-- top1[j]];
        ma[j][p] = INF;
      }
      while(top2[j] > 0) {
        int p = st2[j][-- top2[j]];
        ma_mu[j][p] = INF;
      }
    }
    rec[hs] = ret;
    ans = (ans + ret) % ha;
  }
  printf("%lld\n", ans);
  return 0;
}