BZOJ5332 [SDOI2018] 旧试题
Description
令 d(i) 表示 $i$ 的约数个数。
求 $\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)$ 。
$A,B,C\leqslant10^5$ 。
Solution
注：以下用 $i\perp j$ 表示 $i$ 与 $j$ 互质；$(x/y)$ 表示 $\left\lfloor\frac xy\right\rfloor$ 。
考虑 $d(ijk)$ 。 如果
$$ \begin{aligned} i&=\prod_lp_l^{i_l}\\ j&=\prod_lp_l^{j_l}\\ k&=\prod_lp_l^{k_l} \end{aligned} $$
那么
$$ \begin{aligned} ijk&=\prod_lp_l^{i_l+j_l+k_l}\\ d(ijk)&=\prod_l(1+i_l+j_l+k_l)\\ &=\prod_l\sum_{a\big|p_l^{i_l},b\big|p_l^{j_l},c\big|p_l^{k_l}}[a\perp b][b\perp c][a\perp c]\\ &=\sum_{a|i,b|j,c|k}[a\perp b][a\perp c][b\perp c] \end{aligned} $$
所以答案即为
$$ \sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{a|i,b|j,c|k}[a\perp b][a\perp c][b\perp c] $$
由于 $[x\perp y]=[\gcd(x,y)=1]=\sum_{d|x,d|y}\mu(d)$
所以
$$ \begin{aligned} &\quad\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{a|i,b|j,c|k}[a\perp b][a\perp c][b\perp c]\\ &=\sum_{a=1}^A\sum_{b=1}^B\sum_{c=1}^C[a\perp b][a\perp c]b\perp c(B/b)(C/c)\\ &=\sum_{a=1}^A\sum_{b=1}^B\sum_{c=1}^C(A/a)(B/b)(C/c)\sum_{u|a,u|b}\mu(u)\sum_{v|a,v|c}\mu(v)\sum_{w|b,w|c}\mu(w)\\ &=\sum_{u=1}^A\sum_{v=1}^B\sum_{w=1}^C\mu(u)\mu(v)\mu(w)\left(\sum_{\mathrm{lcm}(u,v)|a}(A/a)\right)\left(\sum_{\mathrm{lcm}(u,w)|b}(B/b)\right)\left(\sum_{\mathrm{lcm}(v,w)|c}(C/c)\right) \end{aligned} $$
又 $\sum_{x|i}(N/i)=\sum_i(N/xi)=F(N/x)$，其中
$$ F(n)=\sum_{i}(n/i)=\sum_{ij\leqslant n}1=\sum_{i=1}^nd(i) $$
是 $d$ 的前缀和。
所以答案即为
$$ \sum_{u=1}^A\sum_{v=1}^B\sum_{w=1}^C\mu(u)\mu(v)\mu(w)F\left(\left\lfloor\frac{A}{\mathrm{lcm}(u,v)}\right\rfloor\right)F\left(\left\lfloor\frac{B}{\mathrm{lcm}(u,w)}\right\rfloor\right)F\left(\left\lfloor\frac{C}{\mathrm{lcm}(v,w)}\right\rfloor\right) $$
容易发现使得后面的式子不为 0 的 $(u,v,w)$ 必满足
$$ \mu(u)\neq0,\mu(v)\neq0,\mu(w)\neq0,\mathrm{lcm}(u,v)\leqslant A,\mathrm{lcm}(u,w)\leqslant B,\mathrm{lcm}(v,w)\leqslant C $$
于是我们爆搜每个质数 $p$ ，枚举它是否被 $u/v/w$ 整除的八种情况即可。
一个优化：我们会发现 $u/v/w$ 中至少有两个数被这个质数整除的四种情况的答案是相同的，除了有两个被整除时 $\mu$ 的两个负号抵消了而三个都被整除的时候由于有三个负号所以还是负的。于是我们只需要把下一层爆搜出的 ans(A/p,B/p,C/p) 加两遍即可（3加1减）。
另一个优化：分析之后我们可以发现把素数从大到小搜时上一个优化会优化得更多。
第三个优化：由于我们素数是从大往小搜的所以当这层的 p 比 A,B,C 都大时这个 p 实际上不影响答案。这时候如果 ABC 都比较小我们可以直接返回预处理的答案。
Code
#include <algorithm>
#include <cstdio>
#include <cstring>
const int N = 100050;
const int M = 40;
const int mod = 1000000007;
typedef long long LL;
int A, B, C;
int F[N], tau[N];
bool mark[N];
int pr[N], cnt;
int FF[M + 1][M + 1][M + 1];
void Init() {
int n = N - 1;
for (int i = 1; i <= n; ++i) tau[i] = 1;
for (int i = 2; i <= n; ++i) if (!mark[i]) {
pr[cnt++] = i;
for (int j = 1; j <= n / i; ++j) {
mark[i * j] = 1;
tau[i * j] += tau[j];
}
}
for (int i = 1; i <= n; ++i) F[i] = F[i - 1] + tau[i];
for (int i = 0; i < cnt - i; ++i)
std::swap(pr[i], pr[cnt - i - 1]);
for (int i = 1; i <= M; ++i)
for (int j = 1; j <= M; ++j)
for (int k = 1; k <= M; ++k)
FF[i][j][k] =
(0ll + FF[i - 1][j][k] + FF[i][j - 1][k] + FF[i][j][k - 1]
- FF[i - 1][j - 1][k] - FF[i - 1][j][k - 1] - FF[i][j - 1][k - 1]
+ FF[i - 1][j - 1][k - 1] + tau[i * j * k]) % mod;
}
inline void Mod(int &a) {
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int dfs(int x, int A, int B, int C) {
// it calculates
// sum{u=1..A,v=1..B,w=1..C}
// mu[u]*mu[v]*mu[w]*F[A/lcm(u,v)]*F[B/lcm(v,w)]*F[C/lcm(u,w)]
// where u,v,w have only prime factors that <= pr[x].
if (!pr[x]) return (LL)F[A] % mod * F[B] % mod * F[C] % mod;
int p = pr[x];
int n = std::max(std::max(A, B), C);
if (p > n && n <= M) {
return FF[A][B][C];
}
if (!(A && B && C)) return 0;
int ans = dfs(x + 1, A, B, C);
if (A >= p && B >= p) Mod(ans -= dfs(x + 1, A / p, B / p, C));
if (B >= p && C >= p) Mod(ans -= dfs(x + 1, A, B / p, C / p));
if (A >= p && C >= p) Mod(ans -= dfs(x + 1, A / p, B, C / p));
if (A >= p && B >= p && C >= p) {
int t = dfs(x + 1, A / p, B / p, C / p);
Mod(t <<= 1);
Mod(ans += t);
}
return ans;
}
int main() {
//freopen("divsum.in", "r", stdin);
//freopen("divsum.out", "w", stdout);
Init();
int T;
scanf("%d", &T);
while (T--) {
int A, B, C;
scanf("%d%d%d", &A, &B, &C);
int c = 0;
while (pr[c] > A && pr[c] > B && pr[c] > C) ++c;
printf("%d\n", dfs(c, A, B, C));
}
//printf("%d\n", clock());
return 0;
}