题解 P4619 【[SDOI2018]旧试题】

GKxx

2019-05-01 15:43:05

Solution

简单反演+神仙优化题。 首先我们知道 $\sigma_0(xy)=\sum\limits_{i|x}\sum\limits_{j|y}[(i,j)=1]$ $\sigma_0(xyz)=\sum\limits_{i|x}\sum\limits_{j|y}\sum\limits_{k|z}[(i,j)=1][(i,k)=1][(j,k)=1]$ ($\sigma_0$是除数函数,相当于题目描述中的$d$) 只要将$x,y,z$素因子分解后观察即可得到上面的结论。它的好处是出现了我们喜欢的$[a=1]$ 就可以莫比乌斯反演了 $\sum\limits_{i=1}^a\sum\limits_{j=1}^b\sum\limits_{k=1}^c\sigma_0(ijk)$ $=\sum\limits_{i=1}^a\sum\limits_{j=1}^b\sum\limits_{k=1}^c\sum\limits_{u|i}\sum\limits_{v|j}\sum\limits_{w|k}[(u,v)=1][(u,w)=1][(v,w)=1]$ $=\sum\limits_{u=1}^a\sum\limits_{v=1}^b\sum\limits_{w=1}^c\lfloor\frac{a}{u}\rfloor\lfloor\frac{b}{v}\rfloor\lfloor\frac{c}{w}\rfloor[(u,v)=1][(u,w)=1][(v,w)=1]$ $=\sum\limits_{i=1}^a\sum\limits_{j=1}^b\sum\limits_{k=1}^c\lfloor\frac{a}{i}\rfloor\lfloor\frac{b}{j}\rfloor\lfloor\frac{c}{k}\rfloor\sum\limits_{u|(i,j)}\mu(u)\sum\limits_{v|(i,k)}\mu(v)\sum\limits_{w|(j,k)}\mu(w)$ $=\sum\limits_{u=1}^{\min(a,b)}\mu(u)\sum\limits_{v=1}^{\min(a,c)}\mu(v)\sum\limits_{w=1}^{\min(b,c)}\mu(w)\sum\limits_{[u,v]|i}^a\lfloor\frac{a}{i}\rfloor\sum\limits_{[u,w]|j}^b\lfloor\frac{b}{j}\rfloor\sum\limits_{[v,w]|k}^c\lfloor\frac{c}{k}\rfloor$ 设$f_y(x)=\sum\limits_{x|i}^y\lfloor\frac{y}{i}\rfloor$,可以$O(n\log n)$预处理出$f_a,f_b,f_c$所有值 $ans=\sum\limits_{u=1}^{\min(a,b)}\mu(u)\sum\limits_{v=1}^{\min(a,c)}\mu(v)\sum\limits_{w=1}^{\min(b,c)}\mu(w)f_a([u,v])f_b([u,w])f_c([v,w])$ 然而痛苦的地方就在于这样推并不能降复杂度,目前为止我们的复杂度依然是$O(n^3)$。事实上可以把它推到$O(n^2\log n)$的,那样做可以过cf原题但是并不利于我们这题的后续优化。 但是也许我们可以不$O(n^3)$地枚举$(u,v,w)$三元组,因为事实上这样枚举的过程中有很多情况的贡献是$0$: - 如果$\mu(u),\mu(v),\mu(w)$中有一个是$0$,那么贡献是$0$。这样的情况还挺多的。 - 如果$x>y$,那么$f_y(x)=0$。也就是说$[u,v]>a$或者$[u,w]>b$或者$[v,w]>c$都会导致贡献是$0$。 所以我们有一种做法就是枚举最大公约数$g$,枚举$u=ig,v=jg$并注意满足条件$(i,j)=1,\mu(u)\neq0,\mu(v)\neq0,[u,v]=ijg\leq\max(a,b,c)$,连边$(u,v)$,建出一张图。这张图的三元环刚好对应到$(u,v,w)$三元组,三元环计数的同时统计答案即可。 至于这样做的复杂度为什么是对的,我们已经发现有相当多的点对$(u,v)$并不满足上述条件(意味着它们产生的贡献是$0$),除去这些之后剩下的点对连出的边不会太多。正如shadowice大佬已经说了他实测下来这个边数只有七十多万。那么只要你的三元环计数速度合格就好。 关于三元环计数,可以参考[iki9的这篇博客](https://www.luogu.org/blog/KingSann/fou-chang-yong-di-hei-ke-ji-san-yuan-huan-post),我们可以在$O(m\sqrt m)$的时间内完成三元环计数。 但是注意到上述连边没有考虑到自环。也就是说如果三元组$(u,v,w)$中存在两个数相等或者三个数都相等,我们并没有将答案计算在内。因此我们需要单独算。这个很方便:三个数都相等的情况直接枚举这个数是几,把答案加起来就好;恰好有两个数相等的情况就在我们枚举$(u,v)$连边的过程中解决,只要顺手把$(u,u,v)$和$(u,v,v)$的答案都加起来即可。 在做的过程中时刻注意剪枝,只要出现$\mu$值为$0$就跳过。另外可以顺手加一些循环展开、register之类的卡卡常。还有大家应该都注意到的cache miss问题,我们选择使用vector而不是邻接表存图以访问连续的内存来加速。 还有一个小trick:我们统计的是$ijk$的约数个数之和,一个数的约数个数不会很多,$i,j,k$又都小于等于$10^5$,估计最终的答案不会太大。事实上答案是不会超过$\text{long long}$的,因此我们在统计的过程中完全不需要取模,只要在最后输出的时候模一下即可。 给一份稍微可读一点的代码 ```cpp #include <cctype> #include <cstdio> #include <climits> #include <algorithm> #include <vector> template <typename T> inline void read(T& x) { int f = 0, c = getchar(); x = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = x * 10 + c - 48, c = getchar(); if (f) x = -x; } template <typename T> void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + 48); } template <typename T> inline void writeln(T x) { write(x); puts(""); } template <typename T> inline bool chkmin(T &x, const T &y) { return y < x ? (x = y, 1) : 0; } template <typename T> inline bool chkmax(T &x, const T &y) { return x > y ? (x = y, 1) : 0; } #if __cplusplus >= 201103L #define reg #else #define reg register #endif typedef long long LL; const int maxn = 1e5 + 207; const LL mod = 1e9 + 7; int mu[maxn], pri[maxn]; bool ff[maxn]; LL fa[maxn], fb[maxn], fc[maxn]; int a, b, c, mx, mn; struct Edge { int u, v, w; Edge(int x, int y, int z = 0) : u(x), v(y), w(z) {} Edge() : u(0), v(0), w(0) {} }; struct Node { int to, w; Node(int x, int y = 0) : to(x), w(y) {} Node() : to(0), w(0) {} }; std::vector<Node> G[maxn]; int deg[maxn]; Edge es[maxn << 4]; int vis[maxn]; int etot; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline void sieve(int n) { mu[1] = 1; for (reg int i = 2; i <= n; ++i) { if (!ff[i]) { pri[++pri[0]] = i; mu[i] = -1; } for (reg int j = 1; j <= pri[0]; ++j) { int x = i * pri[j]; if (x > n) break; ff[x] = 1; if (i % pri[j]) mu[x] = -mu[i]; else { mu[x] = 0; break; } } } } int main() { int T; read(T); sieve(1e5); while (T--) { read(a); read(b); read(c); mx = std::max(std::max(a, b), c); mn = std::min(std::min(a, b), c); // 预处理 f 函数值 for (reg int i = 1; i <= mx; i += 4) { fa[i] = 0; fa[i + 1] = 0; fa[i + 2] = 0; fa[i + 3] = 0; fb[i] = 0; fb[i + 1] = 0; fb[i + 2] = 0; fb[i + 3] = 0; fc[i] = 0; fc[i + 1] = 0; fc[i + 2] = 0; fc[i + 3] = 0; } for (reg int i = 1; i <= a; ++i) for (reg int j = i; j <= a; j += i) fa[i] += a / j; for (reg int i = 1; i <= b; ++i) for (reg int j = i; j <= b; j += i) fb[i] += b / j; for (reg int i = 1; i <= c; ++i) for (reg int j = i; j <= c; j += i) fc[i] += c / j; // u = v = w LL ans = 0; for (reg int i = 1; i <= mn; ++i) if (mu[i]) ans += mu[i] * mu[i] * mu[i] * fa[i] * fb[i] * fc[i]; // u, v, w 有两个相等 etot = 0; for (reg int i = 1; i <= mx; i += 4) { deg[i] = 0; deg[i + 1] = 0; deg[i + 2] = 0; deg[i + 3] = 0; } for (reg int g = 1; g <= mx; ++g) for (reg int i = 1; i * g <= mx; ++i) if (mu[i * g]) for (reg int j = i + 1; 1ll * i * j * g <= mx; ++j) if (mu[j * g] && gcd(i, j) == 1) { int u = i * g, v = j * g, lcm = i * j * g; int uuv = mu[u] * mu[u] * mu[v], uvv = mu[u] * mu[v] * mu[v]; ans += uuv * (fa[u] * fb[lcm] * fc[lcm] + fa[lcm] * fb[u] * fc[lcm] + fa[lcm] * fb[lcm] * fc[u]); ans += uvv * (fa[v] * fb[lcm] * fc[lcm] + fa[lcm] * fb[v] * fc[lcm] + fa[lcm] * fb[lcm] * fc[v]); ++deg[u]; ++deg[v]; es[++etot] = Edge(u, v, lcm); } // u, v, w 两两不同 for (reg int i = 1; i <= mx; ++i) G[i].clear(); for (reg int i = 1; i <= etot; ++i) { int u = es[i].u, v = es[i].v, w = es[i].w; if (deg[u] > deg[v] || (deg[u] == deg[v] && u < v)) G[u].push_back(Node(v, w)); else G[v].push_back(Node(u, w)); } for (reg int x = 1; x <= mx; ++x) if (mu[x]) { unsigned sz = G[x].size(); for (reg unsigned i = 0; i < sz; ++i) vis[G[x][i].to] = G[x][i].w; for (reg unsigned i = 0; i < sz; ++i) { int y = G[x][i].to, wxy = G[x][i].w; if (!mu[y]) continue; for (reg unsigned j = 0, sszz = G[y].size(); j < sszz; ++j) { int z = G[y][j].to; if (vis[z]) { int wyz = G[y][j].w, wxz = vis[z], mmuu = mu[x] * mu[y] * mu[z]; if (!mmuu) continue; ans += mmuu * (fa[wxy] * fb[wyz] * fc[wxz] + fa[wxy] * fb[wxz] * fc[wyz] + fa[wyz] * fb[wxy] * fc[wxz] + fa[wyz] * fb[wxz] * fc[wxy] + fa[wxz] * fb[wxy] * fc[wyz] + fa[wxz] * fb[wyz] * fc[wxy]); } } } for (reg unsigned i = 0; i < sz; ++i) vis[G[x][i].to] = 0; } writeln(ans % mod); } return 0; } ``` 另附$O(n^2\log n)$的做法: $ans=\sum\limits_{u=1}^a\sum\limits_{v=1}^b\sum\limits_{w=1}^c\lfloor\frac{a}{u}\rfloor\lfloor\frac{b}{v}\rfloor\lfloor\frac{c}{w}\rfloor[(u,v)=1][(u,w)=1][(v,w)=1]$ $=\sum\limits_{i=1}^a\sum\limits_{j=1}^b\sum\limits_{k=1}^c\lfloor\frac{a}{i}\rfloor\lfloor\frac{b}{j}\rfloor\lfloor\frac{c}{k}\rfloor\sum\limits_{d|(i,j)}\mu(d)[(i,k)=1][(j,k)=1]$ $=\sum\limits_{d=1}^{\min(a,b)}\mu(d)\sum\limits_{d|i}^a\sum\limits_{d|j}^b\lfloor\frac{a}{i}\rfloor\lfloor\frac{b}{j}\rfloor\sum\limits_{k=1}^c\lfloor\frac{c}{k}\rfloor[(i,k)=1][(j,k)=1]$ $=\sum\limits_{d=1}^{\min(a,b)}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{a}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{b}{d}\rfloor}\lfloor\frac{a}{id}\rfloor\lfloor\frac{b}{jd}\rfloor\sum\limits_{k=1}^c\lfloor\frac{c}{k}\rfloor[(id,k)=1][(jd,k)=1]$ $=\sum\limits_{k=1}^c\lfloor\frac{c}{k}\rfloor\sum\limits_{d=1}^{\min(a,b)}\mu(d)[(d,k)=1]\sum\limits_{i=1}^{\lfloor\frac{a}{d}\rfloor}\lfloor\frac{a}{id}\rfloor[(i,k)=1]\sum\limits_{j=1}^{\lfloor\frac{b}{d}\rfloor}\lfloor\frac{b}{jd}\rfloor[(j,k)=1]$ 设函数$f(x,y)=\sum\limits_{i=1}^x\lfloor\frac{x}{i}\rfloor[(i,y)=1]$那么 $ans=\sum\limits_{k=1}^c\lfloor\frac{c}{k}\rfloor\sum\limits_{d=1}^{\min(a,b)}\mu(d)[(d,k)=1]f(\lfloor\frac{a}{d}\rfloor,k)f(\lfloor\frac{b}{d}\rfloor,k)$ 枚举$k$,枚举$d$,这个$f$直接$O(x)$暴力就行了,因为$x=a/d$所以枚举$d$和计算$f$的总复杂度是$O(n\log n)$(调和级数乘以$n$),总复杂度$O(n^2\log n)$