Codeforces 235E
原题
题目描述:设\(d(n)\)表示\(n\)的因子个数, 给定\(a, b, c\), 求:
\[\sum_{i=1}^{a} \sum_{j=1}^{b} \sum_{k=1}^{c} d(i \cdot j \cdot k) (mod 2^{30})\]
solution
rng_58 Orz,这方法太神了,rng_58证明了下面这条式子:
\[\sum_{i=1}^{a} \sum_{j=1}^{b} \sum_{k=1}^{c} d(i \cdot j \cdot k) =\sum_{(i, j)=(i, k)=(j, k)=1} \left \lfloor \frac{a}{i} \right \rfloor \left \lfloor \frac{b}{j} \right \rfloor \left \lfloor \frac{c}{k} \right \rfloor\]
证明:
设
\[f(a, b, c)=\sum_{i=1}^{a} \sum_{j=1}^{b} \sum_{k=1}^{c} d(i \cdot j \cdot k) \]
\[g(a, b, c)=\sum_{(i, j)=(i, k)=(j, k)=1} \left \lfloor \frac{a}{i} \right \rfloor \left \lfloor \frac{b}{j} \right \rfloor \left \lfloor \frac{c}{k} \right \rfloor\]
由容斥原理可得(一式)
\[d(i \cdot j \cdot k)=f(a, b, c)-f(a-1, b, c)-f(a, b-1, c)-f(a, b, c-1)+f(a-1, b-1, c)+f(a-1, b, c-1)+f(a, b-1, c-1)-f(a-1, b-1, c-1)\]
则若(二式)
\[d(i \cdot j \cdot k)=g(a, b, c)-g(a-1, b, c)-g(a, b-1, c)-g(a, b, c-1)+g(a-1, b-1, c)+g(a-1, b, c-1)+g(a, b-1, c-1)-g(a-1, b-1, c-1)\]
则原命题得证。
二式\(=\)
\[\sum_{(i, j)=(i, k)=(j, k)=1} \left \lfloor \frac{a}{i} \right \rfloor \left \lfloor \frac{b}{j} \right \rfloor \left \lfloor \frac{c}{k} \right \rfloor -\left \lfloor \frac{a-1}{i} \right \rfloor \left \lfloor \frac{b}{j} \right \rfloor \left \lfloor \frac{c}{k} \right \rfloor – \left \lfloor \frac{a}{i} \right \rfloor \left \lfloor \frac{b-1}{j} \right \rfloor \left \lfloor \frac{c}{k} \right \rfloor – \left \lfloor \frac{a}{i} \right \rfloor \left \lfloor \frac{b}{j} \right \rfloor \left \lfloor \frac{c-1}{k} \right \rfloor + \left \lfloor \frac{a-1}{i} \right \rfloor \left \lfloor \frac{b-1}{j} \right \rfloor \left \lfloor \frac{c}{k} \right \rfloor +
\left \lfloor \frac{a-1}{i} \right \rfloor \left \lfloor \frac{b}{j} \right \rfloor \left \lfloor \frac{c-1}{k} \right \rfloor + \left \lfloor \frac{a}{i} \right \rfloor \left \lfloor \frac{b-1}{j} \right \rfloor \left \lfloor \frac{c-1}{k} \right \rfloor – \left \lfloor \frac{a-1}{i} \right \rfloor \left \lfloor \frac{b-1}{j} \right \rfloor \left \lfloor \frac{c-1}{k} \right \rfloor\]
\(=\)
\[\sum_{(i, j)=(i, k)=(j, k)=1} (\left \lfloor \frac{a}{i} \right \rfloor -\left \lfloor \frac{a-1}{i} \right \rfloor) (\left \lfloor \frac{b}{j} \right \rfloor – \left \lfloor \frac{b-1}{j} \right \rfloor) (\left \lfloor \frac{c}{k} \right \rfloor – \left \lfloor \frac{c-1}{k} \right \rfloor)\]
即只有当\((i, j)=(i, k)=(j, k)=1 , i|a, j|b, k|c\)时,和中的式子才等于\(1\),否则为\(0\).
设\(p_i\)为质因子,\(q_i\)为\(p_{i}^{q_i} \leq n\)的最大值,则\(n\)的因数个数为
\[\prod_{i} (q_i +1)\]
根据上述定义设类似\(q_i\)的定义对于\(a\)为\(x_i\), \(b\)为\(y_i\), \(c\)为\(z_i\)
对于\(p_i\),该质数的个数为\(x_i+y_i+z_i\),
因为\((i, j)=(i, k)=(j, k)=1 , i|a, j|b, k|c\), 对于\(p_i\), 答案为\((0, 0, 0)+(1 \text ~ x_i, 0, 0)+(0, 1 \text ~ y_i, 0)+(0, 0, 1 \text ~ z_i)=x_i+y_i+z_i+1\)
所以二式=一式,即\(f(a, b, c)=g(a, b, c)\)
然后就可以用莫比乌斯的性质函数来解了。
\[\sum_{(i, j)=(i, k)=(j, k)=1} \left \lfloor \frac{a}{i} \right \rfloor \left \lfloor \frac{b}{j} \right \rfloor \left \lfloor \frac{c}{k} \right \rfloor\]
\[=\sum_{i} \left \lfloor \frac{a}{i} \right \rfloor \sum_{d=(j, k)} \epsilon(d) \left \lfloor \frac{b}{j} \right \rfloor \left \lfloor \frac{c}{k} \right \rfloor\]
\[=\sum_{i} \left \lfloor \frac{a}{i} \right \rfloor \sum_{d} \mu(d) \left \lfloor \frac{b}{j'd} \right \rfloor \left \lfloor \frac{c}{k'd} \right \rfloor\]
因为\(i\)与\(d, j', k'\)都有关联,所以只好枚举
枚举\(i\),枚举\(d\),然后分别枚举\(j'\), \(k'\),然后相乘,时间复杂度为:\(O(n^2ln\) \(n)\)