莫比乌斯反演的一些简单应用#4

拖更多年我又回来啦!!!(先让我看啊看上次讲到例几先

例8:

求:(egin{aligned}sum_{i=1}^nsum_{j=1}^nfrac{lcm(i,j)}{gcd(i,j)}end{aligned})

这题可以说是非常简单了(比例7简单多了的说,但是谁又能想到它是为了例9做铺垫呢

直接枚举(gcd)

(egin{aligned}&sum_{i=1}^nsum_{j=1}^nfrac{lcm(i,j)}{gcd(i,j)}\=&sum_{k=1}^nsum_{i=1}^{lfloorfrac n k floor}sum_{j=1}^{lfloorfrac n k floor}frac{frac{ikjk}{k}}k imes[gcd(i,j)=1]\=&sum_{k=1}^nsum_{d=1}^{lfloorfrac n k floor}d^2sum_{i=1}^{lfloorfrac n{kd} floor}isum_{j=1}^{lfloorfrac n{kd} floor}j\=&sum_{T=1}^nsum_{i=1}^{lfloorfrac n T floor}isum_{j=1}^{lfloorfrac n T floor}jsum_{d|T}mu(d) imes d^2\=&sum_{T=1}^ns[lfloorfrac n T floor]^2 imes F(T)end{aligned})

其中(T=kd)(egin{aligned}F(T)=sum_{d|T}mu(d) imes d^2end{aligned})

不难证明(F(T))是一个积性函数,单次(O(sqrt n))结束战斗。

例9:

求:(egin{aligned}prod_{i=1}^nprod_{j=1}^nfrac{lcm(i,j)}{gcd(i,j)}end{aligned})

连乘,这就很难受,因为至此为止我们对连乘仍一无所知,所以这里特别放一道。

(egin{aligned}&prod_{i=1}^nprod_{j=1}^nfrac{lcm(i,j)}{gcd(i,j)}\=&prod_{i=1}^nprod_{j=1}^nfrac {ij}{gcd(i,j)^2}\=&(prod_{i=1}^nprod_{j=1}^nij) imes(prod_{i=1}^nprod_{j=1}^ngcd(i,j))^{-2}\=&(prod_{i=1}^ni^n imes n!) imes(prod_{k=1}^nk^{sum_{i=1}^{lfloorfrac n k floor}sum_{j=1}^{lfloorfrac n k floor}[gcd(i,j)=1]})\=&(prod_{i=1}^ni^n imes n!) imes(prod_{k=1}^nk^{sum_{d=1}^{lfloorfrac n k floor}mu(d) imeslfloorfrac n {kd} floor^2})^{-2}end{aligned})

前面一个括号暴力即可。

后面次方上的一坨,只要令(m=lfloorfrac n k floor),那么便是一个最基础的莫比乌斯反演板子啦。

最后一个例题就放到“5”再讲了,我们来讨论一下(egin{aligned}sum_{i=1}^nsum_{j=1}^mlcm(i,j)^{gcd(i,j)}end{aligned}),大家可以提前思考起来了。

原文地址:https://www.cnblogs.com/WR-Eternity/p/11672909.html