Number Challenge

Codeforces235E

我是在2015集训队作业上看到这题的。

d(n)d(n)nn的因子个数,给定A,B,C5000A,B,C\leq 5000,求

i=1Aj=1Bk=1Cd(ijk)\sum_ {i=1}^A\sum_ {j=1}^B\sum_ {k=1}^Cd(ijk)

官方做法

首先要知道的是若n=ipiein=\prod_ {i}p_ i^{e_ i},则d(n)=i(ei+1)d(n)=\prod_ {i}(e_ i+1)。用组合的方法很容易就能证明。

根据换枚举的变量的思路,我们不难想到改成枚举一个质数ppi,j,ki,j,k里面分别出现的次数。那就设f(A,B,C,x)f(A,B,C,x)为使用不小于第xx个质数的质数构成的数求上面那个式子的值。由因子个数和质因子指数的关系可以得到转移方程

f(A,B,C,x)=i,j,kf(Apxi,Bpxj,Cpxk,x+1)(i+j+k+1)f(A,B,C,x)=\sum_ {i,j,k}f(\frac{A}{p_ x^i},\frac{B}{p_ x^j},\frac{C}{p_ x^k},x+1)(i+j+k+1)

这是Codeforces上的官方题解的做法。Codeforces上只要求2000\leq 2000的数据量,对比较小的质数特殊处理之后转移就很少了。

VFK

这个做法的前面的思路和我第一眼看到题目的时候很像,但是后面我就完全不会搞下去了。

x=ijx=ij,则xx出现了d(x)d(x)次,对答案的贡献要乘上这个系数。

=x=1ABd(x)k=1Cd(xk)=\sum_ {x=1}^{AB}d(x)\sum_ {k=1}^Cd(xk)

还是要改变一点枚举的东西,那就枚举因子tt吧。看tt{xkk[1,C]}\left\{xk|k\in[1,C]\right\}中有多少个倍数?由于xx中已经有了gcd(x,t)gcd(x,t),剩下的只要是tgcd(x,t)\frac{t}{gcd(x,t)}倍数就好了,那么就有Cgcd(x,t)t\frac{C\cdot gcd(x,t)}{t}个。

=t=1ABCx=1ABd(x)Cgcd(x,t)t=\sum_ {t=1}^{ABC}\sum_ {x=1}^{AB}d(x)\left\lfloor\frac{C\cdot gcd(x,t)}{t}\right\rfloor

枚举gcd(x,t)gcd(x,t)

=g=1ABt=1Cx=1ABgd(xg)Cgtg[gcd(x,t)=1]=\sum_ {g=1}^{AB}\sum_ {t=1}^{C}\sum_ {x=1}^{\left\lfloor\frac{AB}{g}\right\rfloor}d(xg)\left\lfloor\frac{Cg}{tg}\right\rfloor[gcd(x,t)=1]

=g=1ABt=1Cx=1ABgd(xg)Ct[gcd(x,t)=1]=\sum_ {g=1}^{AB}\sum_ {t=1}^{C}\sum_ {x=1}^{\left\lfloor\frac{AB}{g}\right\rfloor}d(xg)\left\lfloor\frac{C}{t}\right\rfloor[gcd(x,t)=1]

反演一波:

=g=1ABh=1ABgt=1Chx=1ABghd(xgh)Cthμ(h)=\sum_ {g=1}^{AB}\sum_ {h=1}^{\left\lfloor\frac{AB}{g}\right\rfloor}\sum_ {t=1}^{\left\lfloor\frac{C}{h}\right\rfloor}\sum_ {x=1}^{\left\lfloor\frac{AB}{gh}\right\rfloor}d(xgh)\left\lfloor\frac{C}{th}\right\rfloor\mu(h)

下一步比较有技巧性。为了能够分离一些东西出来,注意到求和项不存在单独的gg,我们考虑把ghgh合并成mm

=m=1ABhmt=1Chx=1ABmd(mx)Cthμ(h)=\sum_ {m=1}^{AB}\sum_ {h|m}\sum_ {t=1}^{\left\lfloor\frac{C}{h}\right\rfloor}\sum_ {x=1}^{\left\lfloor\frac{AB}{m}\right\rfloor}d(m\cdot x)\left\lfloor\frac{C}{th}\right\rfloor\mu(h)

接下来就可以分离啦。

=m=1AB(x=1ABmd(mx))(hmμ(h)t=1ChCth)=\sum_ {m=1}^{AB}\left(\sum_ {x=1}^{\left\lfloor\frac{AB}{m}\right\rfloor}d(m\cdot x)\right)\cdot\left(\sum_ {h|m}\mu(h)\sum_ {t=1}^{\left\lfloor\frac{C}{h}\right\rfloor}\left\lfloor\frac{C}{th}\right\rfloor\right)

接下来我们可以枚举mm,线性筛出dd的值,O(ABlog(AB))O(AB\log(AB))搞出左半边;枚举右半部分中hh对每一个mm的贡献,积一下分应该是和左半边一样的复杂度。

这样虽然好像能求出来,而正解的复杂度的确是这个,但是开三个O(AB)O(AB)的数组会MLE……我考试的时候就因为MLE直接没分了。不过这样应该是能通过Codeforces上的测试数据的。

结论题

i=1Aj=1Bk=1Cd(ijk)=gcd(i,j)=gcd(j,k)=gcd(k,i)=1AiBjCk\sum_ {i=1}^A\sum_ {j=1}^B\sum_ {k=1}^Cd(ijk)=\sum_ {gcd(i,j)=gcd(j,k)=gcd(k,i)=1}\left\lfloor\frac{A}{i}\right\rfloor\left\lfloor\frac{B}{j}\right\rfloor\left\lfloor\frac{C}{k}\right\rfloor

这个黑科技似乎来源于rng_58的观察,他用这个结论做了这道题,但不知道是为什么,发了贴来求助。后来得到了证明,并成功推广到了高维。

在介绍证明之前,先回顾一个知识并对它进行拓展。

差分

差分通常(也就是被我)认为是微分在离散函数上的类似概念。差分的形式包括但不限于Δfi=fifi1\Delta f_ i=f_ i-f_ {i-1}这个样子。还有其他各种各样的差分方式,就和大家平时写的代码里面的数组差分一个概念啦。

前缀和与差分互为逆运算,但不一定能得到一样的东西,因为前缀和还要看初始值。

如果我们有一个二维数组,我们知道某个位置的前缀和非常容易O(n2)O(n^2)求出来。那前缀和的逆运算——差分——是否也能够算出来呢?

这个问题也很基础,容斥一下就搞定了。但提出这个问题的目的在于,我们可以继续推广到高位,做高维差分。如果暴力算而且已经得到了所有需要的前缀和,nn维差分的时间复杂度为O(2n)O(2^n)

回归

结论的左边显然是一个函数三维前缀和。为了证明这个等式,我们对两边做三维差分。还是要求i,j,ki,j,k互质,那右边整理完是这个样子的:

i,j,k(AiA1i)(BjB1j)(CkC1k)\sum_ {i,j,k}\left(\left\lfloor\frac{A}{i}\right\rfloor-\left\lfloor\frac{A-1}{i}\right\rfloor\right)\left(\left\lfloor\frac{B}{j}\right\rfloor-\left\lfloor\frac{B-1}{j}\right\rfloor\right)\left(\left\lfloor\frac{C}{k}\right\rfloor-\left\lfloor\frac{C-1}{k}\right\rfloor\right)

=i,j,k[iA][jB][kC]=\sum_ {i,j,k}[i|A][j|B][k|C]

对于一个质数pp,可以不选,也可以选多次。由此发现质数之间的贡献是可以互相叠加的,我们可以用乘法原理把他们合并。

设质数ppxx中出现了f(x,p)f(x,p)次。因为i,j,ki,j,k两两互质,所以一个质数pp只能存在于一个变量中,或者根本就不在i,j,ki,j,k中。如果它存在于ii中,那就有f(A,p)f(A,p)种可能。因为pp存在于三个变量中的情况互相独立,我们用加法原理把它们加起来,再加上不存在于三个变量中的那一种情况,共有

f(A,p)+f(B,p)+f(C,p)+1f(A,p)+f(B,p)+f(C,p)+1

=f(ABC,p)+1=f(ABC,p)+1

种情况。把所有的pp的贡献乘起来

pPf(ABC,p)+1\prod_ {p\in P}f(ABC,p)+1

=d(ABC)=d(ABC)

而这正是等式左边三维差分的答案。

怎么求

枚举ii,再枚举和ii互质的j,kj,k。怎么保证j,kj,k互质?用莫比乌斯反演容斥即可。

F(n,i)F(n,i)为与ii互质的部分的答案贡献,则F(n,i)=gcd(i,j)=1njF(n,i)=\sum_ {gcd(i,j)=1}\left\lfloor\frac{n}{j}\right\rfloor

答案可以表示为

i=1AAigcd(i,d)=1F(Bi,i)F(Ci,i)μ(d)\sum_ {i=1}^A\left\lfloor\frac{A}{i}\right\rfloor\sum_ {gcd(i,d)=1}F(\left\lfloor\frac{B}{i}\right\rfloor,i)\cdot F(\left\lfloor\frac{C}{i}\right\rfloor,i)\cdot\mu(d)

这里要求dd也和ii互质是因为如果ddii不互质,FF代表的那些情况在之前就没有被统计入答案,现在也不用考虑删去。

因为nn的大小允许开两个二维数组,那就先预处理gcdgcd+暴力得到一个O(n2logn)O(n^2\log n)的做法,再记忆化ff来卡常,就过了。

我的优化

我的优化十分暴力,写起来代码十分肮脏。

我们在FF中用O(n)O(n)的时间枚举互质的,其实可以用莫比乌斯反演。预处理R(n)=i=1nniR(n)=\sum_ {i=1}^n\left\lfloor\frac{n}{i}\right\rfloor,则反演可得F(n,i)=diμ(d)R(nd)F(n,i)=\sum_ {d|i}\mu(d)R(\frac{n}{d})。用线性筛预处理出一堆东西,只枚举那些μ\mu不为00的,就可以保证这里枚举的数量不超过32个。

本来均摊的O(logn)O(\log n)的复杂度我会用微积分算出来,现在我就不会算了,因为μ\mu不为00的因子数量是离散的。反正要快一些。

再优化第二层循环。用反演优化需要求前缀和,那就预处理μ\mu在固定一段间隔dd时的前缀和,O(2B+2C)O(2\sqrt{B}+2\sqrt{C})分块搞。因子的展开同样枚举那些μ\mu不为00的。现在时间复杂度真的比较玄学了。

效果还是有的,极限数据点标程861ms861ms,我的234ms234ms