题意
求如下表达式的值
\[\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^Cd(ijk) \bmod (10^9+7) \]其中， \(A,B,C \leqslant 10^5\)
solution
先考虑如何处理后面的\(d(ijk)\)
根据[SDOI]2015约数个数和可知，通过简单的映射关系，有，
\[d(ijk) = \sum_{u|i}\sum_{v|j}\sum_{w|k}[gcd(u, v)=1]\times[gcd(u,w)=1]\times[gcd(v,w)=1] \]则有，
\[\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^Cd(ijk) \]\[= \sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \sum_{u|i}\sum_{v|j}\sum_{w|k}[gcd(u, v)=1]\times[gcd(u,w)=1]\times[gcd(v,w)=1])) \]\[= \sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \sum_{u|i}\sum_{v|j}\sum_{w|k}\epsilon(gcd(u, v))\times\epsilon(gcd(u,w))\times\epsilon(gcd(v,w)) \]根据莫比乌斯反演的经典小把戏，尝试把因子提前枚举，
\[= \sum_{u=1}^A \sum_{v=1}^B \sum_{w=1}^C \sum_{u|i} \sum_{v|j} \sum_{w|k} \epsilon(gcd(u, v))\times\epsilon(gcd(u,w))\times\epsilon(gcd(v,w)) \]\[= \sum_{u=1}^A \sum_{v=1}^B \sum_{w=1}^C \lfloor \frac{A}{u} \rfloor \lfloor \frac{B}{v} \rfloor \lfloor \frac{C}{w} \rfloor \epsilon(gcd(u, v))\epsilon(gcd(u,w))\epsilon(gcd(v,w)) \]由莫比乌斯反演的基本推论：
\[\sum_{i=1}^{A} \sum_{j=1}^{B} \epsilon(gcd(i,j)) = \sum_{i=1}^{A} \sum_{j=1}^{B} \sum_{d|gcd(i,j)} \mu(d) = \sum_{i=1}^{A} \sum_{j=1}^{B} \sum_{d|i , d|j} \mu(d) \]则有，
\[= \sum_{u=1}^A \sum_{v=1}^B \sum_{w=1}^C \lfloor \frac{A}{u} \rfloor \lfloor \frac{B}{v} \rfloor \lfloor \frac{C}{w} \rfloor \sum_{a|u,a|v} \mu(a) \sum_{b|u,b|w} \mu(b) \sum_{c|v,c|w} \mu(c) \]再次交换求和号，
\[=\sum_{a=1}^{min\{A,B\}} \sum_{b=1}^{min\{A,C\}} \sum_{c=1}^{min\{B,C\}} \mu(a) \ \mu(b) \ \mu(c) \ \sum_{lcm(a,b)|u} \lfloor \frac{A}{u} \rfloor \sum_{lcm(a,c)|v} \lfloor \frac{B}{v} \rfloor \sum_{lcm(b,c)|w} \lfloor \frac{C}{w} \rfloor \]\[=\sum_{a=1}^{min\{A,B\}} \sum_{b=1}^{min\{A,C\}} \sum_{c=1}^{min\{B,C\}} \mu(a) \ \mu(b) \ \mu(c) \ \sum_{u} \lfloor \frac{A}{u\times lcm(a,b)} \rfloor \sum_{v} \lfloor \frac{B}{v \times lcm(a,c)} \rfloor \sum_{w} \lfloor \frac{C}{w \times gcd(b,c)} \rfloor \]记\(F(n)=\sum_{i} \lfloor \frac{n}{i} \rfloor = \sum_{i=1}^{n}d(i)\)，则有，
\[=\sum_{a=1}^{min\{A,B\}} \sum_{b=1}^{min\{A,C\}} \sum_{c=1}^{min\{B,C\}} \mu(a) \ \mu(b) \ \mu(c) \ F(\lfloor \frac{A}{lcm(a,b)} \rfloor) F(\lfloor \frac{B}{lcm(a,c)} \rfloor) F(\lfloor \frac{C}{gcd(b,c)} \rfloor) \]然后经过一顿操作，一个\(O(n^3)\)成功变成了另一个\(O(n^3)\)的式子
但是可以通过\(O(n \log n)\)的预处理，提前计算出所有\(F(n)\)的值，至少更加便于处理了
考虑这个式子值非零的条件，则\((a,b,c)\)需要满足：
\[\mu(a) \ne 0 , \mu(b) \ne 0, \mu(c) \ne 0, lcm(a,b) \leqslant A, lcm(a,c) \leqslant B, lcm(b, c) \leqslant C \]后面三个条件不容易考虑，可以从前三个条件下手，不难发现\(a,b,c\)都必须为若干指数为\(1\)的质数的积
不难有暴力dfs，暴力枚举质数的积，然后分别计算其对应的式子的值，时间复杂度为\(O(9592^7)\)，甚至不如\(O(n^3)\)的时间效率好
那么考虑一些优化技巧，或许能够发现我们可以在\(max\{A,B,C\}\)较小时，使用\(O(n^3)\)进行枚举，而对于其值较大时，考虑使用暴力dfs解决问题，分别来考虑：
记\(f(A,B,C) = \sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^Cd(ijk)\)
对于\(O(n^3)\)枚举部分，利用本题答案的定义式，根据容斥定理，则有，
\[f(A,B,C) = \sum_{m_i \in M}(-1)^{\tau(m_i)-1} \times f(A - m_{i,1}, B - m_{i,2}, C - m_{i,3}) + d(ABC) \]其中，\(M\)为除\(\{0,0,0\}\)外其他由三个\(0\)或\(1\)组成的\(7\)个有限数列的集合，\(m_i\)为集合中的一个有限数列，\(\tau(i)\)为\(m_i\)中\(1\)的数量
（写的还不如说的明白，那写个锤子的数学表达式...）
这样便\(O(n^3)\)的时间复杂度下解决了较小\(max\{A,B,C\}\)下的值的求解
接下来解决\(max\{A,B,C\}\)较大时暴力dfs的求解，考虑到原定义式的运算规模较大，我们可以通过推出式来进行爆搜
简化问题规模，对于某个特定质数因子\(p_i\)，分别考虑\(a,b,c\)中是否含有因子\(p\),不妨先假设\(a\)中含有质因子\(p\)，那么对于这个特定\(a\)的值存在等式,
\[g(A,B,C) \]\[=\sum_{b=1}^{min\{A,C\}} \sum_{c=1}^{min\{B,C\}} \mu(a) \ \mu(b) \ \mu(c) \ F(\lfloor \frac{A}{lcm(a,b)} \rfloor) F(\lfloor \frac{B}{lcm(a,c)} \rfloor) F(\lfloor \frac{C}{gcd(b,c)} \rfloor) \]\[=\sum_{b=1}^{min\{A,C\}} \sum_{c=1}^{min\{B,C\}} (-1) \ \mu(\frac{a}{p}) \ \mu(b) \ \mu(c) \ F(\lfloor \frac{A}{lcm(\frac{a}{p},b) \times p} \rfloor) F(\lfloor \frac{B}{lcm(\frac{a}{p},c) \times p} \rfloor) F(\lfloor \frac{C}{gcd(b,c)} \rfloor) \]\[=-g(\frac{A}{p}, \frac{B}{p}, C) \]显然对于任意的\(a\)，对于任意的质数因子\(p\)，该等式同步成立，则有，
\[G(A,B,C) = \sum_{p|a}^A g(A, B, C) = -\sum_{p|a}^A g(\lfloor \frac{A}{p} \rfloor, \lfloor \frac{B}{p} \rfloor, C) = -G(\lfloor \frac{A}{p} \rfloor , \lfloor \frac{B}{p} \rfloor, C) \]显然，对于\(b,c\)，该性质同步存在，记\(i\)为当前筛选到第\(i\)个质数\(p_i\)，\(dfs(i, A, B, C)\)为筛选到\(p_i\)时\(f(A,B,C)\)的值，不难设计dfs方案，
\[dfs(i,A,B,C) = \sum_{m_i \in M}(-1)^{\tau(m_i)} \times dfs(i + 1, \lfloor \frac{A}{m_{i,1} \lor m_{i,2} }\rfloor, \lfloor \frac{B}{m_{i,1} \lor m_{i,3} }\rfloor, \lfloor \frac{C}{m_{i,2} \lor m_{i,3} }\rfloor) \]其中，\(M\)为全体由三个\(0\)或\(1\)组成的\(8\)个有限数列的集合，\(m_i\)为集合中的一个有限数列，\(\tau(i)\)为\(m_i\)中\(1\)的数量
当遍历完全部质数时，无论剩余的范围为多大，显然只能由\((a=1, b=1, c=1)\)做出贡献\(F(A) \times F(B) \times F(C)\)，否则其\(\mu\)值为\(0\)
不难计算，这个暴力dfs的时间复杂度为\(O(8^{9592})\)，但是由于\(A,B,C\)上界的存在，实际运行效率远优于此，但是在本题还是无法通过，考虑剪枝：
-
由于我们已经对\(max\{A,B,C\}\)较小时的方案进行了预处理，显然我们优先考虑较大的质数会使得整个搜索树更小
-
当目前遍历到的素数\(p_i \geqslant max\{A,B,C\}\)时，显然可以直接返回我们先前的预处理值\(f(A,B,C)\)，否则会因为已经除去部分因子而导致我们的预处理值发生改变
-
发现当\(a,b,c\)中有至少两个数字可以被\(p\)整除时，不难发现dfs的返回值不变，只有符号发生变化，可以只递归一次dfs，然后将返回值两倍加入当前的答案
在这些剪枝的基础下，代码可以跑的飞快，完全不需要经历痛苦的卡常过程就可以A掉这题
Code
点击查看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 50;
const int M = 31;
const int mod = 1e9 + 7;
inline int read() {
int res = 0, f = 1;
char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = (res << 3) + (res << 1) + c - '0';
c = getchar();
}
return res * f;
}
inline int add_mod(int a, int b) {
a += b;
if (a < 0) a += mod;
if (a >= mod) a -= mod;
return a;
}
inline int del_mod(int a, int b) {
a -= b;
if (a < 0) a += mod;
if (a >= mod) a -= mod;
return a;
}
inline int mul_mod(int a, int b) {
a = 1ll * a * b % mod;
return a;
}
int num;
int prime[N], d[N];
bool v[N];
int f[N];
int dp[M][M][M];
void init() {
int n = 1e5;
for (int i = 1; i <= n; ++i) d[i] = 1;
for (int i = 2; i <= n; ++i) {
if (!v[i]) {
prime[++num] = i;
for (int j = 1; j <= n / i; ++j) {
v[i * j] = 1;
d[i * j] += d[j];
}
}
}
for (int i = 1; i <= n; ++i) f[i] = add_mod(f[i - 1], d[i]);
reverse(prime + 1, prime + 1 + num);
for (int i = 1; i < M; ++i)
for (int j = 1; j < M; ++j)
for (int k = 1; k < M; ++k)
dp[i][j][k] = (0ll + dp[i - 1][j][k] + dp[i][j - 1][k] + dp[i][j][k - 1] - dp[i - 1][j - 1][k] - dp[i - 1][j][k - 1] - dp[i][j - 1][ k - 1] + dp[i - 1][j - 1][k - 1] + d[i * j * k]) % mod;
}
inline int dfs(int nw, int a, int b, int c) {
int maxx = max(max(a, b), c);
if (!a || !b || !c) return 0;
if (!prime[nw]) return mul_mod(f[a], mul_mod(f[b], f[c]));
if (prime[nw] > maxx && maxx < M) return dp[a][b][c];
int res = dfs(nw + 1, a, b, c);
if (a >= prime[nw] && b >= prime[nw]) res = del_mod(res, dfs(nw + 1, a / prime[nw], b / prime[nw], c));
if (a >= prime[nw] && c >= prime[nw]) res = del_mod(res, dfs(nw + 1, a / prime[nw], b, c / prime[nw]));
if (b >= prime[nw] && c >= prime[nw]) res = del_mod(res, dfs(nw + 1, a, b / prime[nw], c / prime[nw]));
if (a >= prime[nw] && b >= prime[nw] && c >= prime[nw]) res = add_mod(res, mul_mod(dfs(nw + 1, a / prime[nw], b / prime[nw], c / prime[nw]), 2));
return res;
}
int A, B, C;
int main () {
init();
int T = read();
while (T--) {
A = read(), B = read(), C = read();
int cnt = 1;
while (prime[cnt] > A && prime[cnt] > B && prime[cnt] > C) ++cnt;
printf("%d\n", dfs(cnt, A, B, C));
}
return 0;
}
杂记
感谢_rqy的博客提供的idea，清芷姐姐太强力（说实话真没看懂rqy博客的细节内容，细节都是自己一点一点填的）
上次写赛博笔记都已经是三年半之前了，时间过得真快啊
顺便闲的没事搞了一个cnblogs，顺手发上去叭
标签：lfloor,frac,试题,sum,rfloor,mu,SDOI2018,nw From： https://www.cnblogs.com/abigjiong/p/17446718.html