51nod 1238 - 最小公倍数之和 V3

51nod 1238 - Click Here

　　

Description

　　出一个数N，输出小于等于N的所有数，两两之间的最小公倍数之和。

　　由于结果很大，输出Mod 1000000007的结果。

　　

Input

　　输入一个数N。(2 <= N <= 10^10)

　　

Output

　　输出Mod 1000000007的结果。

　　

Solution

　　这个技巧$(f \cdot g) \times g = (f \times I) \cdot g$还蛮好玩的233

　　

　　首先根据题目要求推下式子

$$\begin{eqnarray*} ans &=& \sum_{i=1}^n \sum_{j=1}^n [i,j] \\ &=& \sum_{i=1}^n \sum_{j=1}^n \frac{ij}{(i,j)} \\ &=& \sum_{d=1}^n \frac{1}{d} \sum_{i=1}^n \sum_{j=1}^n [(i,j)=d] \\ &=& \sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} [(i,j)=1] \\ &=& \sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{k \mid i , k \mid j} \mu(k) \\ &=& \sum_{d=1}^n d \sum_k k^2\mu(k) \cdot (\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor} i)^2 \\ &=& \sum_{D=1}^n \sum_{k \mid D} k^2\mu(k) \cdot \frac{D}{k} \cdot (\sum_{i=1}^{\lfloor \frac{n}{D} \rfloor} i)^2 \\ \end{eqnarray*}$$

　　

　　令$f(n) = \sum_{k \mid n} k^2\mu(k) \cdot \frac{n}{k}​$，$S(n) = \sum_{i=1}^n i​$

　　那么上式等价于$ans = \sum_{D=1}^n f(D) \cdot S(\lfloor \frac{n}{D} \rfloor)^2$

　　$\lfloor \frac{n}{D} \rfloor​$只有$2 \sqrt n​$个取值，因此求出$f​$的前缀和即可解决问题。

　　

　　约定$f \times g$为$f$与$g$的狄利克雷卷积，$f \cdot g$为$f$与$g$的乘积。

　　那么有

$$\begin{eqnarray*} f &=& (\mu \cdot ID^2) \times ID \\ f \times ID^2 &=& (\mu \cdot ID^2) \times ID \times ID^2 \\ f \times ID^2 &=& (\mu \cdot ID^2) \times ID^2 \times ID \\ f \times ID^2 &=& ((\mu \times I) \cdot ID^2) \times ID \\ f \times ID^2 &=& (e \cdot ID^2) \times ID \\ f \times ID^2 &=& ID \end{eqnarray*}$$

　　因为$ID^2, ID​$的前缀和能够$O(1)​$求得，因此$f​$可以用杜教筛在$O(n^{\frac{2}{3}})​$求出前缀和。

　　

　　然后，因为杜教筛需要提前预处理出前$n^{\frac{2}{3}}​$的部分。

　　这个可以将$f(n)​$化为$f(n) = n \sum_{k \mid n} k \mu(k)​$，利用$k​$只能是square-free number这个性质，可以很简单用线性筛预处理出。

　　时间复杂度$O(n^{\frac{2}{3}} + \sqrt n)$

　　

CODE

CODE - Click Here