over 2 years ago

前言

刷去年作业题做到了这道题,感觉还是挺好的一道数论题,感谢vfk启发我给出了证明。

分析

我们要求的是,其中表示的约数个数,
这题有做法,但是我显然是来讲反演做法的。
首先我们要证明一个结论:
考虑我们如何把每一个约数对应到一个序列上去。
我们考虑一个素数中的幂数分别是,对于一个约数,假设我们定义,由于互质,所以一个素数只会出现在一个中,那么我们定义约数对应的序列满足:初始化每个,对于每个素因子,那么,这样我们可以看出每个约数对应的序列都不相同,而且每一个互质的序列都对应了一个,因此左右两边相等。
我们证明了这个式子之后,可以推出一个结论:
$$\sum_{x_1=1}^{a_1}\sum_{x_2=1}^{a_2}...\sum_{x_n=1}^{a_n}d(x_1x_2...x_n)=\sum_{x_1=1}^{a_1}\sum_{x_2=1}^{a_2}...\sum_{x_n=1}^{a_n}\sum_{b_1|x_1}\sum_{b_2|x_2}...\sum_{b_n|x_n}\prod_{i<j}[\gcd(b_i, b_j)=1]$$
也就是:
$$\sum_{x_1=1}^{a_1}\sum_{b_1|x_1}\sum_{x_2=1}^{a_2}\sum_{b_2|x_2}...\sum_{x_n=1}^{a_n}\sum_{b_n|x_n}\prod_{i<j} [\gcd(b_i, b_j)=1] $$
即:
$$\sum_{x_1=1}^{a_1}\sum_{x_2=1}^{a_2}...\sum_{x_n=1}^{a_n}\prod_{k=1}^{n}{\left \lfloor \frac{a_i}{x_i}\right \rfloor} \prod_{i<j} [\gcd(b_i, b_j)=1] $$
化成原题就是:
$$\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} $$
这个直接反演就好了,可以得出:
$$\sum_{i=1}^{a}\left \lfloor \frac{a}{i} \right\rfloor\sum_{d=1}^{max(b,c)}\mu(d)\sum_{j=1}^{\left \lfloor b/d \right\rfloor}[\gcd(i,jd)=1]\left \lfloor \frac{b}{jd} \right\rfloor\sum_{j=1}^{\left \lfloor c/d \right\rfloor}[\gcd(i,kd)=1]\left \lfloor \frac{c}{jd} \right\rfloor$$
由于调和数是的,因此时间复杂度就是的。
CF235E.cpp

← bzoj2125:最短路 CF260E →
 
comments powered by Disqus