积性函数前缀和-个人总结

积性函数前缀和-个人总结

【写在前面】

​ 用了一个多星期将这部分大致弄懂了，东西太多，有很多技巧，自己重新写了一下，记录自己的理解。内容与原文基本一致，在其基础上加上了一些我感觉比较重要的但他没有详细说明的东西。以下都是我逐字打出来的。如果有什么错误，请指出。——Simon

前置技能里面的东西需要充分理解和记忆，在后面推导过程中会多次用到前置技能里面的东西。

转载出处：

author: skywalkert
original article: http://blog.csdn.net/skywalkert/article/details/50500009

【常用技巧】

[sum_{k=1}^nsum_{d|k}dcdot k=sum_{k=1}^nsum_{d=1}^{frac nk}dcdot kcdot d=sum_{d=1}^nsum_{k|d}dcdot frac dk=sum_{d=1}^nsum_{k=1}^{frac nd}dcdot kcdot d=sum_{d=1}^nsum_{d|k}dcdot k=sum_{k=1}^nsum_{k|d} dcdotfrac dk\ 上式为约数，倍数之间重要的变换，需要充分理解并熟练运用。\ \1、遇到[gcd(i,j)=1],考虑将其转换为sum_{k|gcd(i,j)}mu(k)\ 2、对于sum_{i=1}^nsum_{j=1}^n[gcd(i,j)=1]=2sum_{i=1}^nsum_{j=1}^i[gcd(i,j)=1]-sum_{i=1}^n[gcd(i,i)=1]=ig(2sum_{i=1}^nvarphi(i)ig)-1\ 3、sum_{i=1}^{n}isum_{j=1}^{n}[gcd(i,j)=1]cdot j=2sum_{i=1}^{n}isum_{j=1}^i[gcd(i,j)=1]cdot j-sum_{i=1}^n[gcd(i,i)=1]cdot i\ =igg(2sum_{i=1}^nifrac{icdotvarphi(i)+[i=1]}{2}igg)-1=igg(sum_{i=1}^ni^2cdotvarphi(i)+[i=1]igg)-1\ 4、记w(n)为n的质因子个数，则2^{w(n)}为n的约数中无平方因子的个数，则f(n)=2^{w(n)}=sum_{d|n}mu^2(d)\ 则sigma_0(n^2)=sum_{d|n}f(d)=sum_{d|n}sum_{k|d}mu^2(k)，附个表sum_{i=1}^{10}sigma(i^2)\ 5、n 以内不含平方因子的数的个数g(n)=sum_{i=1}^nmu^2(i)=sum_{i=1}^{sqrt{n}}mu(i)cdotlfloorfrac n{i^2} floor\ 6、sum_{d|n}sum_i^{frac{n}{d}}=sum_{d|n}sum_i^{d}，且d|n可以用埃筛预处理，i为d，j为n。\ 7、sigma_0(icdot j)=sum_{d|icdot j}=sum_{x|i}sum_{y|j}[gcd(i,j)=1]，sigma_1(icdot j)=sum_{d|icdot j}d=sum_{x|i}sum_{y|j}frac{ycdot n}{x}[gcd(i,j)=1] \8、若a>b, gcd(a,b)=1，则有gcd(a^m-b^m,a^n-b^n)=a^{gcd(n,m)}-b^{gcd(n,m)}。 ]

​ 证明7：

[令x=icdot j,则由唯一分解定理得：x=p_1^{e_1}p_2^{e_2}dots p_n^{e_k}，则x的约数个数为(e_1+1)cdot(e_2+1)dots(e_k+1)\ 考虑任意一个质数p对答案的贡献。假设质数p在i的质因数中出现了a次，在j的质因数中出现了b次，那么p对答案\的贡献就为a+b+1。而a+b+1=sum_{x=0}^asum_{y=0}^b[gcd(p^x,p^y)=1]，等效与以下矩阵：a=2,b=3\ left(egin{matrix} 1&1&1&1\ 1&p&p&p\ 1&p&p^2&p^2 end{matrix} ight)\ 相当于对于素数p来说，不同时出现于两个数的质因数中。 \ 由唯一分解定理又得：i=p_1^{e_1}p_2^{e_2}p_3^{e_3}...p_k^{e_k}，j=p_1^{q_1}p_2^{q_2}p_3^{q_3}...p_k^{q_k}，根据乘法原理可得：\ sigma_0(icdot j)=sum_{x_1=0}^{e_1}sum_{y_1=0}^{q_1}[(p_1^{x_1},p_1^{y_1})=1]sum_{x_2=0}^{e_2}sum_{y_2=0}^{q_2}[(p_2^{x_2},p_2^{y_2})=1]...sum_{x_n=0}^{e_n}sum_{y_n=0}^{q_n}[(p_n^{x_n},p_n^{y_n})=1]\将其合并得：sigma_0(icdot j)=sum_{x|i}sum_{y|j}[gcd(x,y)=1]\ 对于任意一个素数p来说，它们不同时出现于x,y中，就相当于gcd(x,y)=1。 ]

[sigma_1(ncdot m)=sum_{a|ncdot m}a\=sum_{k=1}^rsum_{cig|frac{nm}{P_k^{x_k+y_k}}}sum_{a|P_k^{x_k+y_k}}ac\=sum_{a_1ig|P_1^{x_1+y_1}}sum_{a_2ig|P_2^{x_2+y_2}}...sum_{a_rig|P_r^{x_r+y_r}}Big(prod_{i=1}^ra_iBig) \对于某个素数p_k: sum_{aig | P_k^{x_k+y_k}}a=sum_{a|P_{k}^{x_k}}sum_{b|P_{k}^{y_k}}[ gcd(a,b)=1]frac{P_{k}^{x_k}b}{a}\所以：sigma_1(ncdot m)=sum_{a|n}sum_{b|m}frac{ncdot b}{a}[gcd(a,b)=1] ]

2、
10
1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0 1 0
1 1 0 1 1 0 1 1 0 1
1 0 1 0 1 0 1 0 1 0
1 1 1 1 0 1 1 1 1 0
1 0 0 0 1 0 1 0 0 0
1 1 1 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0 1 0
1 1 0 1 1 0 1 1 0 1
1 0 1 0 0 0 1 0 1 0

4、
1											1
1 2 4										1 1 2
1 3 9 										1 1 3
1 2 4 8 16									1 1 2 1 2
1 5 25										1 1 5
1 2 3 4 6 9 12 18 36						1 1 2 1 3 1 2 3 6
1 7 49										1 1 7
1 2 4 8 16 32 64							1 1 2 1 2 1 2
1 3 9 27 81									1 1 3 1 3
1 2 4 5 10 20 25 50 100						1 1 2 1 5 1 2 5 10	
48											48

【前置技能】

【积性函数的定义】

  1. 若(f(n))的定义域为正整数域，值域为复数，即(f:Z^+→C)，则称(f(n))为数论函数。
  2. 若(f(n))为数论函数，且(f(1)=1)，对于互质的正整数(p,q)有(f(p⋅q)=f(p)⋅f(q))，则称其为积性函数。
  3. 若(f(n))为积性函数，且对于任意正整数(p,q)都有(f(p⋅q)=f(p)⋅f(q))，则称其为完全积性函数。

【积性函数的性质与例子】

  1. 若(f(n))为积性函数，则对于正整数(n=prod_{i=1}^tp_i^{e_i})有(f(n)=prod_{i=1}^tf(p_i^{e_i}));若f(n)为完全积性函数，则对于正整数(n=prod_{i=1}^tp_i^{e_i})有(f(n)=prod_{i=1}^tf(p_i)^{e_i})。
  2. 常见的积性函数有：
    1. 除数函数(sigma_k(n)=sum_{d|n}d^k),表示n的约数的k次幂和，注意(sigma_k(n))与(sigma^k(n))是不同的。
      • 由唯一分解定理得：(n=prod_{i=1}^tp_i^{e_i})。则(sigma_k(n)=prod_{i=1}^tsigma_k(p_i^{e_i})=prod_{i=1}^t sum_{d|p_i^{e_i}}d^k=prod_{i=1}^t(1+p^k+p^{2k}+p^{3k}+dots+p^{e_ik}))
    2. 约数个数函数(τ(n)=σ_0(n)=∑_{d|n}1)，表示(n)的约数个数，一般也写为(d(n))。
      • (sigma_0(n)=prod_{i=1}^tsigma_0(p_i^{e_i})=prod_{i=1}^t(1+p^0+p^0+p^0+dots+p^{0})=prod_{i=1}^te_i+1)。
    3. 约数和函数(σ(n)=σ_1(n)=∑_{d|n}d)，表示(n)的约数之和。
      • (sigma_1(n)=prod_{i=1}^t(1+p^1+p^2+p^3+dots+p^{e_i}))。(ps:)括号内的可以用等比数列求和公式简化。
    4. 欧拉函数(varphi(n)=sum_{i=1}^n[(n,i)=1]cdot1),表示不大于(n)且与(n)互质的正整数的个数，另外(sum_{i=1}^n[(n,i)=1]cdot i=frac{ncdot varphi(n)+[n=1]}2)，且对于正整数(n>2)来说(varphi(n))是偶数。
      • (n e1时，2sum_{i=1}^n[(n,i)=1]cdot i=sum_{i=1}^n[(n,i)=1]cdot i+sum_{i=1}^n[(n,i)=1]cdot(n-i)=\ sum_{i=1}^n[(n,i)=1]cdot n=nsum_{i=1}^n[(n,i)=1]=ncdotvarphi(n),则sum_{i=1}^n[(n,i)=1]cdot i=frac{ncdot varphi(n)}{2})
    5. 莫比乌斯函数(μ(n))，在狄利克雷卷积的乘法中与恒等函数互为逆元，(μ(1)=1)，对于无平方因子数(n=∏^t_{i=1}p_i)有(μ(n)=(−1)^t)，对于有平方因子数(n)有(μ(n)=0)。
    6. 元函数 (e(n)=[n=1])，狄利克雷卷积的乘法单位元，完全积性。
    7. 恒等函数(I(n)=1)，完全积性。
    8. 单位函数(id(n)=n)，完全积性。
    9. 幂函数(id^k(n)=n^k)，完全积性。
  3. 关于莫比乌斯函数和欧拉函数有两个经典的公式
    • ([n=1]=∑_{d|n}μ(d))，将(μ(d))看作是容斥的系数即可证明。
    • (n=∑_{d|n}φ(d))，将(frac in(1≤i≤n))化为最简分数统计个数即可证明。

【狄利克雷卷积与莫比乌斯反演】

  1. 数论函数(f)和(g)狄利克雷卷积定义为((f∗g)(n)=∑_{d|n}f(d)⋅g(frac nd))，狄利克雷卷积满足交换律(((f*g)(n)=(g*f)(n)=sum_{d|n}g(d)f(frac nd)))、结合律((f*g*h=f*(g*h)))，对加法满足分配律，存在单位元函数(e(n)=[n=1])使得(f∗e=f=e∗f)，若(f)和(g)为积性函数则(f∗g)也为积性函数。
  2. 狄利克雷卷积的一个常用技巧是对于积性函数(f)与恒等函数(I)的卷积的处理，例如(n=prod_{i=1}^tp_i^{e_i},(f*I)(n)=sum_{d|n}f(d)I(frac nd)=sum_{d|n}f(d)=prod_{i=1}^tsum_{j=0}^{e_i}f(p_i^j))。
  3. 莫比乌斯反演也是对于(g(n)=∑_{d|n}f(d)(g=f*I)) 的讨论，但是不要求(f) 是积性函数，适用于已知(g(n))求(f(n)) 的情况，由于((I*mu)(n)=sum_{d|n}mu(d)=e(n))，则(g*mu=(f*I)*mu=f*(I*mu)=f*e=f)，即若(g=f*I)，则(f(n)=(g*mu)(n)=sum_{d|n}g(d)cdotmu(frac nd))，类似的有(g(n)=sum_{n|d}f(d)Rightarrow f(n)=sum_{n|d}g(d)cdotmu(frac dn))，二项式反演也是类似的技巧。有一个例子可以看出欧拉函数和莫比乌斯函数之间的关系，由于(sum_{d|n}varphi(d)=id(n))，所以(varphi(n)=sum_{d|n}mu(d)cdotfrac nd)，即(frac{varphi(n)}n=sum_{d|n}frac{mu(d)}d)。

【正文：黑科技】

这种黑科技在低于线性时间的复杂度下解决一类积性函数的前缀和问题。

首先看一个简单的例子，求前(n)个正整数的约数之和，即(∑^n_{i=1}σ(i))，其中(n≤10^{12})。显然不能直接做了，但是我们可以推导一番：

[方法1：sum_{i=1}^nsigma(i)=sum_{i=1}^nsum_{d|i}d=sum_{d=1}^ndsum_{i=1}^frac nd=sum_{i=1}^nicdotlfloorfrac ni floor\ 方法2：sum_{i=1}^nsigma(i)=sum_{i=1}^nsum_{d|i}d=sum_{i=1}^nsum_{d=1}^{frac ni}d=sum_{i=1}^nfrac{lfloorfrac ni floorcdot (lfloorfrac ni floor+1)}{2} ]

​ 当(ile sqrt{n})时，(lfloorfrac ni floor)显然只有(O(sqrt{n}))个取值；当(igesqrt{n})同样；对于固定的(lfloorfrac ni floor)，(i)的取值是一段连续的区间，这段区间是([igglfloorfrac{n}{lfloorfrac ni floor+1}igg floor+1,igglfloorfrac{n}{lfloorfrac ni floor}igg floor ])，因此可以(O(sqrt{n}))求得。例(n=10)时:(sum_{i=1}^nsigma(i)=1 imes10+2 imes5+3 imes3+4 imes2+5 imes2+6 imes1+7 imes1+8 imes1+9 imes1+10 imes1),则(sum_{i=1}^nsigma(i)=10 imes1+5 imes2+3 imes3+2 imes(4+5)+1 imes(6+7+8+9+10))。

求前n个正整数的约数个数之和也类似：

[sum_{i=1}^nsigma_0(i)=sum_{i=1}^nsum_{d|n}1=sum_{d=1}^nsum_{i=1}^frac nd1=sum_{d=1}^nlfloorfrac nd floor ]

现在我们来加大一点难度，(51Nod 1239)求前(n)个正整数的欧拉函数之和，即(Phi(n)=∑^n_{i=1}φ(i))，其中(n≤10^{11})。

对于(varphi(i)),我们知道(sum_{d|n}varphi(d)=n),即((varphi*I)(n)=sum_{d|n}varphi(d)I(frac nd)=sum_{d|n}varphi(d)=n)，则

[frac{ncdot(n+1)}{2}=sum_{i=1}^ni=sum_{i=1}^n(varphi*I)(i)=sum_{i=1}^nsum_{d|n}varphi(d)=sum_{i=1}^nsum_{d=1}^{frac ni}varphi(d)=sum_{i=1}^nPhi(lfloorfrac ni floor) ]

对于(sum_{i=1}^nPhi(lfloorfrac ni floor))，如果(i=1)则即是我们要求的(Phi(n))。

[则Phi(n)=sum_{i=1}^nPhi(lfloorfrac ni floor)-sum_{i=2}^nPhi(lfloorfrac ni floor)=frac{ncdot (n+1)}2-sum_{i=2}^nPhi(lfloor frac ni floor) ]

由于(Phi(n))是一个积性函数的前缀和，所以筛法也可以预处理一部分。所以总复杂度为(O(n^{frac 23}))。

​ 如果能通过狄利克雷卷积构造一个更好计算前缀和的函数，且用于卷积的另一个函数也易计算，则可以简化计算过程。例如上题就是利用了(φ∗I=id)的性质，但一定注意，不是所有的这一类题都只用配个恒等函数(I)
就可以轻松完事的，有时需要更细致的观察。

(51Nod 1244)定义梅滕斯函数(M(n)=∑^n_{i=1}μ(i))，给定正整数(n)，计算(M(n))，其中(n≤10^{11})。可以利用(mu*I=e)的性质简化

对于(mu(i))，有(sum_{d|n}mu(d)=[n=1])，则((mu*I)(n)=sum_{d|n}mu(d)I(frac nd)=[n=1])，则

[1=sum_{i=1}^n[i=1]=sum_{i=1}^n(mu*I)(i)=sum_{i=1}^nsum_{d|n}mu(d)=sum_{i=1}^nsum_{d=1}^{frac ni}mu(d)=sum_{i=1}^nM(lfloorfrac ni floor)\ 同理得： M(n)=sum_{i=1}^nM(lfloorfrac ni floor)-sum_{i=2}^nM(lfloor frac ni floor)=1-sum_{i=2}^nM(lfloorfrac ni floor) ]

同理复杂度为(O(n^{frac 23}))。

(51Nod 1237)定义最大公约数之和的函数(G(n)=sum_{i=1}^nsum_{j=1}^ngcd(i,j))，给定正整数n，计算(G(n))，其中(nle10^{10})。

[方法1：G(n)=sum_{i=1}^nsum_{j=1}^ngcd(i,j)=sum_{i=1}^nsum_{j=1}^nsum_{d=1}^n[gcd(i,j)=d]cdot d=sum_{d=1}^nsum_{i=1}^{frac nd}sum_{j=1}^{frac nd}[gcd(i,j)=1]cdot d\ 因为[gcd(i,j)=1]=sum_{k|gcd(i,j)}mu(k) \ 则G(n)=sum_{d=1}^nsum_{i=1}^{frac nd}sum_{j=1}^{frac nd}sum_{k|gcd(i,j)}mu(k)cdot d=sum_{k=1}^nmu(k)sum_{d=1}^{n}dsum_{i=1}^{frac n{kd}}sum_{j=1}^{frac n{kd}}1=sum_{k=1}^nmu(k)sum_{d=1}^{ n}dcdotlfloorfrac n{kd} floor^2\ 令T=dk, 则得sum_{T=1}^nlfloorfrac n{T} floor ^2sum_{d|T}dcdotmu(frac Td)\ 再由n=id(n)=sum_{d|n}varphi(d), 则由莫比乌斯反演得varphi(n)=sum_{d|n}id(d)cdotmu(frac nd)=sum_{d|n}dcdotmu(frac nd)\ 则得sum_{T=1}^nlfloorfrac{n}{T} floor^2varphi(T)，剩下就是求欧拉函数前缀和了。 ]

[方法2：G(n)=sum_{i=1}^nsum_{j=1}^ngcd(i,j)=sum_{i=1}^nsum_{j=1}^nsum_{d=1}^n[gcd(i,j)=d]cdot d=sum_{d=1}^nsum_{i=1}^{frac nd}sum_{j=1}^{frac nd}[gcd(i,j)=1]cdot d\ sum_{d=1}^ndsum_{i=1}^{frac nd}sum_{j=1}^{frac nd}[gcd(i,j)=1]=sum_{d=1}^ndigg(ig(2sum_{i=1}^{frac nd}varphi(i)ig)-1igg)，则剩下就是求欧拉函数前缀和了。\ 对于sum_{i=1}^nsum_{j=1}^n[gcd(i,j)=1]=2sum_{i=1}^nsum_{j=1}^i[gcd(i,j)=1]-sum_{i=1}^n[gcd(i,i)=1]=ig(2sum_{i=1}^nvarphi(i)ig)-1 ]

(51Nod 1238)定义最小公倍数之和的函数(L(n)=sum_{i=1}^nsum_{j=1}^nlcm(i,j))，给定正整数n，计算(L(n))，其中(nle10^{10})

[方法1：L(n)=sum_{i=1}^nsum_{j=1}^nlcm(i,j)=sum_{i=1}^nsum_{j=1}^nfrac{icdot j}{gcd(i,j)}=sum_{i=1}^nsum_{j=1}^nsum_{d=1}^n[gcd(i,j)=d]frac{icdot j}{d}\ =sum_{d=1}^nsum_{i=1}^{frac nd}sum_{j=1}^{frac nd}[gcd(i,j)=1]icdot jcdot d=sum_{d=1}^nsum_{i=1}^{frac nd}sum_{j=1}^{frac nd}sum_{k|gcd(i,j)}mu(k)cdot icdot jcdot d=sum_{d=1}^nsum_{k=1}^{frac nd}sum_{i=1}^{frac {n}{dk}}sum_{j=1}^{frac{n}{dk}}icdot jcdot dcdotmu(k)cdot k^2\ =sum_{d=1}^ndsum_{k=1}^{frac nd}mu(k)cdot k^2sum_{i=1}^{frac {n}{dk}}isum_{j=1}^{frac{n}{dk}}j=sum_{d=1}^ndsum_{k=1}^{frac nd}mu(k)cdot k^2cdotfrac{(lfloorfrac n{dk} floor+1)^2cdot lfloorfrac n{dk} floor^2}{4}\ 然后就是求mu(k)cdot k^2的前缀和，但是这个方法时间复杂度过高好像为O(n)。\此题不可行。后面有一道题要用此方法。 ]

[方法2：L(n)=sum_{i=1}^nsum_{j=1}^nlcm(i,j)=sum_{i=1}^nsum_{j=1}^nfrac{icdot j}{gcd(i,j)}=sum_{i=1}^nsum_{j=1}^nsum_{d=1}^n[gcd(i,j)=d]frac{icdot j}{d}\ =sum_{d=1}^ndsum_{i=1}^{frac nd}sum_{j=1}^{frac nd}[gcd(i,j)=1]icdot j=sum_{d=1}^ndsum_{i=1}^{frac nd}isum_{j=1}^{frac nd}[gcd(i,j)=1]j\ 因为sum_{i=1}^{n}isum_{j=1}^{n}[gcd(i,j)=1]cdot j=2sum_{i=1}^{n}isum_{j=1}^i[gcd(i,j)=1]cdot j-sum_{i=1}^n[gcd(i,i)=1]cdot i\ =igg(2sum_{i=1}^nifrac{icdotvarphi(i)+[i=1]}{2}igg)-1=igg(sum_{i=1}^ni^2cdotvarphi(i)+[i=1]igg)-1\ 则得sum_{d=1}^ndigg(ig(sum_{i=1}^{frac nd}i^2cdotvarphi(i)+[i=1]ig)-1igg)=sum_{d=1}^ndsum_{i=1}^{frac nd}i^2cdotvarphi(i)，然后就是求phi(n)=sum_{i=1}^ni^2cdot varphi(i)。\ 令f(n)=n^2cdot varphi(n)，则sum_{d|n}f*(id)^2(n)=sum_{d|n}d^2cdotvarphi(d)cdot(frac nd)^2=n^2sum_{d|n}varphi(d)=n^3\ 则frac {n^2cdot(n+1)^2}4=sum_{i=1}^ni^3=sum_{i=1}^n(f*id^2)(i)=sum_{i=1}^nsum_{d|i}d^2cdotvarphi(d)cdot(frac id)^2=sum_{i=1}^ni^2sum_{d=1}^{frac ni}d^2cdotvarphi(d)\=sum_{i=1}^ni^2cdotphi(frac ni)，则phi(n)=sum_{i=1}^ni^2cdot phi(frac ni)-sum_{i=2}^ni^2cdot phi(frac ni)=frac{n^2cdot(n+1)^2}{4}-sum_{i=1}^ni^2cdotphi(frac ni)\ 最终得L(n)=sum_{d=1}^ndcdotphi(frac nd) ]

(Tsinsen A1231)定义最小公倍数之和的函数(L(n,m)=sum_{i=1}^nsum_{j=1}^m lcm(i,j))，给定正整数n，m,计算(L(n,m))，其中(n,mle10^{7})

[L(n)=sum_{i=1}^nsum_{j=1}^mlcm(i,j)=sum_{i=1}^nsum_{j=1}^mfrac{icdot j}{gcd(i,j)}=sum_{i=1}^nsum_{j=1}^msum_{d=1}^n[gcd(i,j)=d]frac{icdot j}{d}\ =sum_{d=1}^nsum_{i=1}^{frac nd}sum_{j=1}^{frac md}[gcd(i,j)=1]icdot jcdot d=sum_{d=1}^nsum_{i=1}^{frac nd}sum_{j=1}^{frac md}sum_{k|gcd(i,j)}mu(k)cdot icdot jcdot d=sum_{d=1}^nsum_{k=1}^{frac nd}sum_{i=1}^{frac {n}{dk}}sum_{j=1}^{frac{m}{dk}}icdot jcdot dcdotmu(k)cdot k^2\ =sum_{d=1}^ndsum_{k=1}^{frac nd}mu(k)cdot k^2sum_{i=1}^{frac {n}{dk}}isum_{j=1}^{frac{m}{dk}}j=sum_{d=1}^ndsum_{k=1}^{frac nd}mu(k)cdot k^2cdotfrac{lfloorfrac n{dk} floorcdot(lfloorfrac n{dk} floor+1)cdot lfloorfrac m{dk} floorcdot(lfloorfrac m{dk} floor+1)}{4}\ 到此时此题已经可以过了。复杂度为O(n).但其实还可以优化。\将最后面的一部分记为sum(frac n{dk},frac m{dk})，\ 则上式=sum_{d=1}^nsum(frac nd,frac md)sum_{k|d}frac dkcdotmu(k)cdot k^2，再令f(d)=sum_{k|d}frac dkcdotmu(k)cdot k^2，\因为积性函数的约数和也是积性函数，所以f数组可以预处理出来。 \对于一个素数p，它的新 f 值显然是 p - p^2 的\ 如果 p 是多个素数的一次项的积\ 显然 f 是积性的 f( p ) = f( p1 ) * f( p2 ) * f( p3 )……\ 如果 p 的唯一分解存在质因子的\指数大于1，它新增的每一个因子的 μ 值都是0，没有意义，\只有统计时D变成了原来的 j 倍,所以 此时f( p ) = f( i ) * j\ 前缀和在之后加一下就可以了\ ]

不知道为什么显然的看下面（类似）

积性函数的线性筛原理：

[ecause sum_{d|n}varphi(d)=n,则由莫比乌斯反演得varphi(n)=sum_{d|n}mu(d)cdotfrac{n}{d}=sum_{d|n}mu(frac{n}{d})cdot d\ 由莫比乌斯函数的意义： mu(n)=left{egin{array}{ll} 1&若n=1\ (-1)^k&若n无平方数因数，且n=p_1p_2dots p_k\ 0&若n有大于1的平方因数 end{array} ight.\可知，当n为素数时，varphi(n)=mu(n)cdot 1+mu(1)cdot n=n-1 \当n=p_1p_2dots p_k，即无平方数因数，varphi(n)=varphi(p_1)cdotvarphi(p_2)cdot dotscdotvarphi(p_k)\ 当n中有平方数因数时，平方数因数对varphi(n)没有贡献即：\ 假设n=icdot y，y是x的一个最小质因数则：varphi(i)=sum_{d|i}mu(d)frac {i}{d}\ varphi(n)=varphi(icdot y)=sum_{d|(icdot y)}mu(d)frac {icdot y}{d}=ycdot sum_{d|(icdot y)}mu(d)frac {i}{d}=ycdot varphi(i)\ \综上varphi(n)= left{egin{matrix} n-1&nin primes\ f(i)cdot y&y^2|n\ f(i)cdot f(y)&y^2 ot mid n end{matrix} ight.其中，y为n的最小质因数，并且n=icdot y ]

2019-ICPC-南京赛区-网络赛E：令(f_n(k)=sum_{l_1=1}^nsum_{l_2=1}^ndotssum_{l_k=1}^n gcd(l_1,l_2,dots,l_k))。求(sum_{i=2}^kf_n(i) mod (10^9+7))。(nle 10^9,kle 10^{10^5})。

对于(f_n(k))有：

[sum_{l_1=1}^nsum_{l_2=1}^ndotssum_{l_k=1}^ngcd(l_1,l_2,dots,l_k)=sum_{d=1}^nsum_{l_1=1}^{frac{n}{d}}sum_{l_2=1}^{frac{n}{d}}dotssum_{l_k=1}^{frac{n}{d}}[gcd(l_1,l_2,dots,l_k)=1]cdot d^2 \=sum_{d=1}^nd^2sum_{t=1}^{n}mu(t)sum_{l_1=1}^{frac{n}{dt}}sum_{l_2=1}^{frac{n}{dt}}dotssum_{l_k=1}^{frac{n}{dt}}=sum_{d=1}^nd^2sum_{t=1}^nmu(t)lfloorfrac{n}{dt} floor^k ]

令(T=dt)得：

[f_n(k)=sum_{T=1}^{n}sum_{t|T}mu(t)cdotfrac{T^2}{t^2}cdot lfloorfrac{n}{T} floor^k ]

则(sum_{i=2}^kf_n(i))为：

[sum_{i=2}^kf_n(i)=sum_{i=2}^ksum_{T=1}^nsum_{t|T}mu(t)cdot frac{T^2}{t^2}cdot lfloorfrac{n}{T} floor^k=sum_{T=1}^nsum_{t|T}mu(t)frac{T^2}{t^2}sum_{i=2}^klfloorfrac{n}{T} floor^k \=sum_{T=1}^nsum_{t|T}mu(t)frac{T^2}{t^2}Big(frac{lfloorfrac{n}{T} floor^{k+1}-1}{lfloorfrac{n}{T} floor-1}-lfloorfrac{n}{T} floor-1Big) ]

​ 因为(kle 10^{10^5})，所以用欧拉定理降幂取模即可。注意特判(lfloor frac{n}{T} floor=1)的情况。

​ 其中令(g(T)=sum_{t|T}mu(t)cdot frac{T^2}{t^2}，Phi(n)=sum_{T=1}^ng(T))。对于(T)小的部分可以通过线性筛求得：

​ 1. 当(T)为素数时，(g(T)=T^2-1)。
​ 2. 若(T)中无平方质因子时(T=p_1cdot p_2dots p_k)，因为(g(T))为积形函数，则有(g(T)=g(p_1)cdot g(p_2)dots g(p_k))。

​ 3. 若(T)中有平方质因子时，有(g(Tcdot p)=g(T)cdot p^2)。

​ 对于(T)大的部分，我们发现(g(T)=mu*id^2(T))，则(g*I(T)=mu*I*id^2(T)=e*id^2(T)=id^2(T)=T^2)。则有：

[sum_{T=1}^nT^2=sum_{T=1}^nsum_{d|T}g(d)=sum_{T=1}^nsum_{d|T}sum_{t|d}mu(t)cdot frac{d^2}{t^2}=sum_{T=1}^nsum_{d=1}^{frac{n}{T}}sum_{t|d}mu(t)cdotfrac{d^2}{t^2} \=sum_{T=1}^nPhi(frac{n}{T}),则Phi(n)=frac{ncdot (n+1)cdot (2cdot n+1)}{6}-sum_{T=2}^nPhi(frac{n}{T}) ]

放个51Nod1238代码当模板用：

/*
 * @Author: Simon 
 * @Date: 2019-05-03 12:35:17 
 * @Last Modified by: Simon
 * @Last Modified time: 2019-05-03 17:29:21
 */
#include<bits/stdc++.h>
using namespace std;
typedef int Int;
#define int long long
#define INF 0x3f3f3f3f
#define maxn 5000005
#define Mod 3000005
const int mod=1e9+7;
int inv2,inv4,inv6;
struct HashMap{
    int head[Mod],key[Mod],value[Mod],nxt[Mod],tol=0;
    void clear(){
        tol=0;memset(head,-1,sizeof(head));
    }
    HashMap(){
        clear();
    }
    void insert(int k,int v){
        int idx=k%Mod;
        for(int i=head[idx];~i;i=nxt[i]){
            if(key[i]==k){
                value[i]=min(value[i],v);
                return ;
            }
        }
        key[tol]=k;value[tol]=v;nxt[tol]=head[idx];head[idx]=tol++;
    }
    int operator [](int k){
        int idx=k%Mod;
        for(int i=head[idx];~i;i=nxt[i]){
            if(key[i]==k) return value[i];
        }
        return -1;
    }
}mp;
Int prime[maxn],Phi[maxn],cnt=0,sum[maxn];
bool vis[maxn]={1,1};
void Euler(){
    Phi[1]=1;
    for(int i=2;i<maxn;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            Phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<maxn;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                Phi[i*prime[j]]=Phi[i]*prime[j];
                break;
            }
            Phi[i*prime[j]]=Phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<maxn;i++) sum[i]=(sum[i-1]+i%mod*i%mod*Phi[i])%mod;
}
int sum_1(int n){
    n%=mod;
    return n%mod*(n+1)%mod*inv2%mod;
}
int sum_2(int n){
    n%=mod;
    return n%mod*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}
int sum_3(int n){
    n%=mod;
    return n%mod*n%mod*(n+1)%mod*(n+1)%mod*inv4%mod;
}
int dfs(int n){
    if(n<maxn) return sum[n];
    if(mp[n]!=-1) return mp[n];
    int sum=0;
    for(int i=2,j;i<=n;i=j+1){
        j=n/(n/i);
        (sum+=(sum_2(j)-sum_2(i-1)+mod)%mod*dfs(n/i)%mod)%=mod; 
    }
    sum=(sum_3(n)-sum+mod)%mod;
    mp.insert(n,sum);
    return sum;
}
int solve(int n){
    int sum=0;
    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        (sum+=(sum_1(j)-sum_1(i-1)+mod)%mod*dfs(n/i)%mod)%=mod;
    }
    return sum;
}
int fpow(int a,int b){
    a%=mod;int ans=1;
    while(b){
        if(b&1) (ans*=a)%=mod;
        (a*=a)%=mod;
        b>>=1;
    }
    return ans;
}
Int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);Euler();
    inv2=fpow(2,mod-2);inv4=fpow(4,mod-2);inv6=fpow(6,mod-2);
    int n;scanf("%lld",&n);
    printf("%lld
",solve(n));
    cin.get(),cin.get();
    return 0;
}

莫比乌斯反演扩展

结尾补一个不常用的莫比乌斯反演非卷积形式的公式，对于数论函数(f,g)和完全积性函数(t)且(t(1)=1):

[f(n)=sum_{i=1}^nt(i)cdot gBig(Big lfloor frac{n}{i}Big floor Big)\ Leftrightarrow g(n)=sum_{i=1}^nmu(i)cdot t(i)cdot fBig(Big lfloor frac{n}{i}Big floor Big)\ ]

补充：特殊形式下的积性函数的线性筛原理

[如何利用线性筛来O(n)求出函数f(x)=sum_{pin primes,p|x}mu(frac {x}{p})的前缀和\令x的最小质因子为y，即x=icdot y\ 1、xin primes ,p只能等于x,则f(x)=mu(frac {x}{x})=mu(1)=1\ 2、i\%y=0,即x有多个最小质因子,f(x)=f(icdot y)=sum_{pin primes,p|(icdot y)}mu(frac {icdot y}{p}) \当i没有多个相同的质因子，当且仅当p=y时，mu(frac {icdot y}{p})不为0，故f(x)=u(i)。 \当i也有多个相同的质因子，那么对于任意的p，都有mu(frac {icdot y}{p})=0,故f(x)=0 \所以f(x)=mu(i)+0=mu(i) \3、i\%y eq 0，即x只有一个最小质因子：有f(i)=sum_{pin primes,p|i}mu(frac {i}{p}) \f(x)=f(icdot y)=sum_{pin primes,p|(icdot y)}mu(frac {icdot y}{p})\= left{egin{matrix} sum_{pin primes,p|(icdot y)}mu(frac {i}{p})cdot mu(y)=sum_{pin primes,p|(icdot y)}-mu(frac {i}{p})=-f(i)&p eq y\ sum_{pin primes,p|(icdot y)}mu(frac {icdot y}{y})=sum_{pin primes,p|(icdot y)}mu({i})=mu(i)&p=y end{matrix} ight.\ 所以f(x)=-f(i)+mu(i)\ 综上f(x)=left{egin{matrix} 1&x in primes\ mu(i)&y^2|x,即x有平方数因子\ -f(i)+mu(i)&y^2 ot mid x,即x无平方数因子 end{matrix} ight.\其中，y为n的最小质因数，并且n=icdot y ]

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/--Simon/p/11391429.html