Learning：数论（四）莫比乌斯反演（+题集）

Learning：数论（四）莫比乌斯反演（+题集）

莫比乌斯函数的定义：

μ ( x ) = { 1 , n = 1 ( − 1 ) k , n = p 1 p 2 . . . p k ， 其 中 p 1 , p 2 , . . . , p k 为 互 不 相 同 的 素 数 0 , 其 他 情 况 mu(x)=begin{cases} 1,n=1\ (-1)^k,n=p_p_k，其中p_1,p_2,...,p_k为互不相同的素数\ 0,其他情况 end{cases} μ(x)=⎩⎪⎨⎪⎧​1,n=1(−1)k,n=p1​p2​...pk​，其中p1​,p2​,...,pk​为互不相同的素数0,其他情况​
自己稍微推一推就可以知道这是一个积性函数。
所以很显然我们可以线性筛 μ mu μ
由定义得：
μ ( 1 ) = 1 mu(1)=1 μ(1)=1
μ ( p ) = − 1 mu(p)=-1 μ(p)=−1
μ ( p k ) = 0 ( k > 1 ) mu(p^k)=0(k>1) μ(pk)=0(k>1)
所以就可以直接筛了，代码如下：

void init(){mu[1]=1;for(int i=2;i<N;i++){if(!vis[i]){prm[cnt++]=i;mu[i]=-1;}for(int j=1;j<cnt&&i*prm[j]<N;j++){vis[i*prm[j]]=1;if(!(i%prm[j])){mu[i*prm[j]]=0;break;}mu[i*prm[j]]=-mu[i];}}return;
}

莫比乌斯反演

莫比乌斯反演有一个非常非常非常重要的性质：
∑ d ∣ n μ ( d ) = [ n = 1 ] sum_{d|n}mu(d)=[n=1] ∑d∣n​μ(d)=[n=1]
怎么证？
我们设 n = ∏ i = 1 k p i α i n=prod_{i=1}^kp_i^{alpha_i} n=∏i=1k​piαi​​
考虑 n n n的所有因数，他们的素因子都是 p 0 , p 1 , . . . , p k − 1 p_0,p_1,...,p_{k-1} p0​,p1​,...,pk−1​中的，而我们会发现只有当因数的所有的素因子次数为 1 1 1时对答案的贡献才不为 0 0 0，所以我们可以认为 n n n的每个对答案的贡献不为 0 0 0因数都是在 p 0 , p 1 , . . . , p k − 1 p_0,p_1,...,p_{k-1} p0​,p1​,...,pk−1​中取若干个素数相乘得到的。特殊的，因数1我们可以当做一个素数都不取。
当 n = 1 n=1 n=1时，显然 原 式 = 1 原式=1 原式=1。
当 n > 1 n>1 n>1时，
若 k k k为奇数，
首先易证 C n m = C n n − m C_n^m=C_n^{n-m} Cnm​=Cnn−m​
选奇数个素数相乘得到的因数个数为 C k 1 + C k 3 + . . . + C k k C_k^1+C_k^3+...+C_k^k Ck1​+Ck3​+...+Ckk​，这种因数的函数值为 − 1 -1 −1
选偶数个素数相乘得到的因数个数为 C k 0 + C k 2 + . . . + C k k − 1 C_k^0+C_k^2+...+C_k^{k-1} Ck0​+Ck2​+...+Ckk−1​，这种因数的函数值为 1 1 1
首先显然 C n m = C n n − m C_n^m=C_n^{n-m} Cnm​=Cnn−m​
所以易证 C k 1 + C k 3 + . . . + C k k = C k 0 + C k 2 + . . . + C k k − 1 C_k^1+C_k^3+...+C_k^k=C_k^0+C_k^2+...+C_k^{k-1} Ck1​+Ck3​+...+Ckk​=Ck0​+Ck2​+...+Ckk−1​，所以因数的函数值加起来为 0 0 0。
若 k k k为偶数，
选奇数个素数相乘得到的因数个数为 C k 1 + C k 3 + . . . + C k k − 1 C_k^1+C_k^3+...+C_k^{k-1} Ck1​+Ck3​+...+Ckk−1​，这种因数的函数值为 − 1 -1 −1
选偶数个素数相乘得到的因数个数为 C k 0 + C k 2 + . . . + C k k C_k^0+C_k^2+...+C_k^k Ck0​+Ck2​+...+Ckk​，这种因数的函数值为 1 1 1
首先显然 C n m = C n − 1 m − 1 + C n − 1 m ( m ̸ = 0 ) , C n 0 = C n − 1 0 C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}(mnot=0),C_n^0=C_{n-1}^0 Cnm​=Cn−1m−1​+Cn−1m​(m̸​=0),Cn0​=Cn−10​
所以 C k 0 + C k 2 + . . . + C k k = C k − 1 0 + C k − 1 1 + C k − 1 2 + . . . + C k − 1 k − 2 + C k − 1 k − 1 = 2 k − 1 C_k^0+C_k^2+...+C_k^k=C_{k-1}^0+C_{k-1}^1+C_{k-1}^2+...+C_{k-1}^{k-2}+C_{k-1}^{k-1}=2^{k-1} Ck0​+Ck2​+...+Ckk​=Ck−10​+Ck−11​+Ck−12​+...+Ck−1k−2​+Ck−1k−1​=2k−1
C k 1 + C k 3 + . . . + C k k − 1 = C k 1 + C k 2 + C k 3 + . . . + C k k − ( C k 0 + C k 2 + . . . + C k k ) C_k^1+C_k^3+...+C_k^{k-1}=C_k^1+C_k^2+C_k^3+...+C_k^k-(C_k^0+C_k^2+...+C_k^k) Ck1​+Ck3​+...+Ckk−1​=Ck1​+Ck2​+Ck3​+...+Ckk​−(Ck0​+Ck2​+...+Ckk​)
= 2 k − ( C k 0 + C k 2 + . . . C k k ) = 2 k − 2 k − 1 = 2 k − 1 = C k 0 + C k 2 + . . . C k k =2^k-(C_k^0+C_k^2+...C_k^k)=2^k-2^{k-1}=2^{k-1}=C_k^0+C_k^2+...C_k^k =2k−(Ck0​+Ck2​+...Ckk​)=2k−2k−1=2k−1=Ck0​+Ck2​+...Ckk​
所以因数的函数值加起来为 0 0 0。
综上， ∑ d ∣ n μ ( d ) = [ n = 1 ] sum_{d|n}mu(d)=[n=1] ∑d∣n​μ(d)=[n=1]

这个性质有多重要，我们接下来看一道题（前置知识：数论分块）：
有 t ( 1 ≤ t ≤ 10000 ) t(1leq tleq10000) t(1≤t≤10000)组数据，每组数据给定 n , m , ( 1 ≤ n ≤ m ≤ 1 0 7 ) n,m,(1leq nleq mleq10^7) n,m,(1≤n≤m≤107)求 ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = 1 ] sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=1] i=1∑n​j=1∑m​[gcd(i,j)=1]
O(nm)秒了
我们会发现暴力的时间复杂度是 O ( n m ) O(nm) O(nm)，显然会TLE，所以我们考虑优化。
[ g c d ( i , j ) = 1 ] [gcd(i,j)=1] [gcd(i,j)=1]这个式子很神奇？所以就从这里入手。
仔细分析就会发现 [ g c d ( i , j ) = 1 ] = ∑ d ∣ g c d ( i , j ) μ ( d ) [gcd(i,j)=1]=sum_{d|gcd(i,j)}mu(d) [gcd(i,j)=1]=d∣gcd(i,j)∑​μ(d)，因为由前面的莫比乌斯函数的性质可得当且仅当 g c d ( i , j ) = 1 gcd(i,j)=1 gcd(i,j)=1时， ∑ d ∣ g c d ( i , j ) μ ( d ) sum_{d|gcd(i,j)}mu(d) ∑d∣gcd(i,j)​μ(d)才会等于 1 1 1，否则等于 0 0 0
所以原式就可以变成： ∑ i = 1 n ∑ j = 1 m ∑ d ∣ g c d ( i , j ) μ ( d ) sum_{i=1}^nsum_{j=1}^msum_{d|gcd(i,j)}mu(d) i=1∑n​j=1∑m​d∣gcd(i,j)∑​μ(d)
然后枚举 d d d，此时 i , j i,j i,j就是 d d d的倍数，所以小于 n n n的 i i i就有 ⌊ n d ⌋ lfloorfrac{n}{d}rfloor ⌊dn​⌋个， j j j同理。所以我们就可以轻松得到： ∑ d = 1 n ⌊ n d ⌋ ⌊ m d ⌋ μ ( d ) sum_{d=1}^nlfloorfrac{n}{d}rfloorlfloorfrac{m}{d}rfloormu(d) d=1∑n​⌊dn​⌋⌊dm​⌋μ(d)
线性筛出 μ mu μ的前缀和，然后数论分块 O ( n + m ) O(sqrt{n}+sqrt{m}) O(n ​+m ​)求解。
这就是莫比乌斯反演（其实有个公式的，但是用这个公式大部分题目都很难推，所以不如直接用莫比乌斯函数的性质来搞）
莫比乌斯反演只有多推才能熟练，所以
我们继续！

有 t ( 1 ≤ t ≤ 10000 ) t(1leq tleq10000) t(1≤t≤10000)组数据，每组数据给定 n , m , k ( 1 ≤ n ≤ m ≤ 1 0 7 ) n,m,k(1leq nleq mleq10^7) n,m,k(1≤n≤m≤107).求: ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = k ] sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=k] i=1∑n​j=1∑m​[gcd(i,j)=k]（HDU1695数据范围稍有增加）
咋一看和刚刚的怎么长得那么像？
我们会发现只有当 i , j i,j i,j都是 k k k的倍数时，且 g c d ( i k , j k ) = 1 gcd(frac{i}{k},frac{j}{k})=1 gcd(ki​,kj​)=1时才能成立
所以原式转化为 ∑ i = 1 ⌊ n k ⌋ ∑ i = 1 ⌊ m k ⌋ [ g c d ( i , j ) = 1 ] sum_{i=1}^{lfloorfrac{n}{k}rfloor}sum_{i=1}^{lfloorfrac{m}{k}rfloor}[gcd(i,j)=1] i=1∑⌊kn​⌋​i=1∑⌊km​⌋​[gcd(i,j)=1]
这不就转化为原来的那道题了吗？得到原式等于 ∑ d = 1 ⌊ n k ⌋ ⌊ n d k ⌋ ⌊ m d k ⌋ μ ( d ) sum_{d=1}^{lfloorfrac{n}{k}rfloor}lfloorfrac{n}{dk}rfloorlfloorfrac{m}{dk}rfloormu(d) d=1∑⌊kn​⌋​⌊dkn​⌋⌊dkm​⌋μ(d)
直接数论分块

接着下一题：
有 t ( 1 ≤ t ≤ 10000 ) t(1leq tleq10000) t(1≤t≤10000)组数据，每组数据给定 n , m ( 1 ≤ n ≤ m ≤ 1 0 7 ) n,m(1leq nleq mleq10^7) n,m(1≤n≤m≤107)求 ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) 为 素 数 ] sum_{i=1}^nsum_{j=1}^m[gcd(i,j)为素数] i=1∑n​j=1∑m​[gcd(i,j)为素数]
（bzoj2820）
咋一看怎么和刚刚的还是那么像？
记素数集为 p r i m e prime prime
所以我们直接枚举素数，得到 ∑ p ∈ p r i m e ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = p ] sum_{pin prime}sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=p] p∈prime∑​i=1∑n​j=1∑m​[gcd(i,j)=p]
由上题可得：原式= ∑ p ∈ p r i m e ∑ d = 1 n p ⌊ n p d ⌋ ⌊ m p d ⌋ μ ( d ) sum_{pin prime}sum_{d=1}^{frac{n}{p}}lfloorfrac{n}{pd}rfloorlfloorfrac{m}{pd}rfloormu(d) p∈prime∑​d=1∑pn​​⌊pdn​⌋⌊pdm​⌋μ(d)
然后我们记 k = p d k=pd k=pd，枚举 k k k，得到：
∑ k = 1 n ⌊ n k ⌋ ⌊ m k ⌋ ∑ p ∈ p r i m e , p ∣ k μ ( k p ) sum_{k=1}^nlfloorfrac{n}{k}rfloorlfloorfrac{m}{k}rfloorsum_{pin prime,p|k}mu(frac{k}{p}) k=1∑n​⌊kn​⌋⌊km​⌋p∈prime,p∣k∑​μ(pk​)
设函数 f ( n ) = ∑ p ∈ p r i m e , p ∣ n μ ( n p ) f(n)=sum_{pin prime,p|n}mu(frac{n}{p}) f(n)=∑p∈prime,p∣n​μ(pn​)
所以原式= ∑ k = 1 n ⌊ n k ⌋ ⌊ m k ⌋ f ( k ) sum_{k=1}^nlfloorfrac{n}{k}rfloorlfloorfrac{m}{k}rfloor f(k) k=1∑n​⌊kn​⌋⌊km​⌋f(k)
我们可以在线性筛的时候处理 f ( n ) f(n) f(n)。
当 n n n为素数时，显然 f ( n ) = 1 f(n)=1 f(n)=1
当 n n n为合数时，
记 p r m [ j ] prm[j] prm[j]为 n n n的最小素因子（线性筛中当前枚举的素数）， i = n p i=frac{n}{p} i=pn​
当 p r m [ j ] ∣ i prm[j]|i prm[j]∣i（ n n n的最小素因子 p r m [ j ] prm[j] prm[j]的次数大于 1 1 1）时，
当 i i i无多个次数大于1的素因子时，当且仅当 p = p r m [ j ] p=prm[j] p=prm[j]时 μ ( n p ) ̸ = 0 mu(frac{n}{p})not=0 μ(pn​)̸​=0，此时 f ( n ) = μ ( n p r m [ j ] ) = μ ( i ) f(n)=mu(frac{n}{prm[j]})=mu(i) f(n)=μ(prm[j]n​)=μ(i)
当 i i i有多个次数大于1的素因子时，无论 p r m [ j ] prm[j] prm[j]等于多少， μ ( n p ) = 0 mu(frac{n}{p})=0 μ(pn​)=0，又因为易知 μ ( i ) = 0 mu(i)=0 μ(i)=0，所以 f ( n ) = μ ( n p ) = 0 = μ ( i ) f(n)=mu(frac{n}{p})=0=mu(i) f(n)=μ(pn​)=0=μ(i)，
所以当 p r m [ j ] ∣ i prm[j]|i prm[j]∣i时 f ( n ) = μ ( i ) f(n)=mu(i) f(n)=μ(i)
当 p r m [ j ] ̸ ∣ i prm[j]not|i prm[j]̸​∣i（ n n n的最小素因子 p r m [ j ] prm[j] prm[j]的次数等于 1 1 1）时，
此时， n n n就比 i i i多了一个素因数 p r m [ j ] prm[j] prm[j]，因为
f ( i ) = ∑ p ∣ i , p ∈ p r i m e μ ( i p ) f(i)=sum_{p|i,pin prime}mu(frac{i}{p}) f(i)=p∣i,p∈prime∑​μ(pi​)
f ( n ) = ∑ p ∣ n , p ∈ p r i m e μ ( n p ) = ∑ p ∣ n , p ∈ p r i m e μ ( i ∗ p r m [ j ] p ) f(n)=sum_{p|n,pin prime}mu(frac{n}{p})=sum_{p|n,pin prime}mu(frac{i*prm[j]}{p}) f(n)=p∣n,p∈prime∑​μ(pn​)=p∣n,p∈prime∑​μ(pi∗prm[j]​)
因为 i i i不含素因子 p r m [ i ] prm[i] prm[i]，所以
μ ( i ∗ p r m [ j ] p ) = − μ ( i p ) mu(frac{i*prm[j]}{p})=-mu(frac i p) μ(pi∗prm[j]​)=−μ(pi​)
又因为 n n n比 i i i多一个素因子 p r m [ j ] prm[j] prm[j]，所以
f ( n ) = − ∑ p ∣ n , p ∈ p r i m e , p ̸ = p r m [ j ] μ ( i p ) + μ ( n p r m [ j ] ) f(n)=-sum_{p|n,pin prime,pnot= prm[j]}mu(frac{i}{p})+mu(frac n{prm[j]}) f(n)=−p∣n,p∈prime,p̸​=prm[j]∑​μ(pi​)+μ(prm[j]n​)
= μ ( i ) − ∑ p ∣ i , p ∈ p r i m e μ ( i p ) =mu(i)-sum_{p|i,pin prime}mu(frac{i}{p}) =μ(i)−p∣i,p∈prime∑​μ(pi​)
= μ ( i ) − f ( i ) =mu(i)-f(i) =μ(i)−f(i)
这样我们就可以在线性筛的时候预处理 f f f，然后直接数论分块解决。

继续
有 t ( 1 ≤ t ≤ 1000000 ) t(1leq tleq1000000) t(1≤t≤1000000)组数据，每组数据给定 n , m , k ( 1 ≤ n ≤ 1 0 7 ) n,m,k(1leq nleq10^7) n,m,k(1≤n≤107)求 ∑ i = 1 n g c d ( i , n ) sum_{i=1}^ngcd(i,n) i=1∑n​gcd(i,n)
前置知识：狄利克雷卷积
首先枚举 g c d ( i , n ) gcd(i,n) gcd(i,n)：
∑ d ∣ n d ∑ i = 1 n [ g c d ( i , n ) = d ] sum_{d|n}dsum_{i=1}^n[gcd(i,n)=d] d∣n∑​di=1∑n​[gcd(i,n)=d]
除掉 d d d得到：
∑ d ∣ n d ∑ i = 1 n d [ g c d ( i , n d ) = 1 ] sum_{d|n}dsum_{i=1}^{frac nd}[gcd(i,frac nd)=1] d∣n∑​di=1∑dn​​[gcd(i,dn​)=1]
反演：
∑ d ∣ n d ∑ i = 1 n d ∑ k ∣ i , k ∣ n d μ ( k ) sum_{d|n}dsum_{i=1}^{frac nd}sum_{k|i,k|frac nd}mu(k) d∣n∑​di=1∑dn​​k∣i,k∣dn​∑​μ(k)
枚举 k k k：
∑ d ∣ n ∑ k ∣ n d d μ ( k ) n d k sum_{d|n}sum_{k|frac nd}dmu(k)frac n{dk} d∣n∑​k∣dn​∑​dμ(k)dkn​
我们记 T = d k T=dk T=dk，然后枚举T：
∑ T ∣ n n T ∑ d ∣ T d μ ( T d ) sum_{T|n}frac nTsum_{d|T}dmu(frac Td) T∣n∑​Tn​d∣T∑​dμ(dT​)
记 g ( n ) = n , f ( n ) = ∑ d ∣ n d μ ( n d ) g(n)=n,f(n)=sum_{d|n}dmu(frac nd) g(n)=n,f(n)=∑d∣n​dμ(dn​)
显然 g g g是积性函数
然后我们发现 f f f是 g g g和 μ mu μ的狄利克雷卷积，所以也是积性函数
然后我们发现原式其实也就是 f f f和 g g g的狄利克雷卷积，所以也是一个积性函数
直接线性筛，然后 O ( 1 ) O(1) O(1)询问。

其实还有一种更简单的做法，需要用到欧拉函数的性质 ∑ d ∣ n ϕ ( d ) = n sum_{d|n}phi(d)=n ∑d∣n​ϕ(d)=n
利用这个性质我们就可以吧原式转化为：
∑ i = 1 n ∑ d ∣ i , d ∣ n ϕ ( d ) sum_{i=1}^{n}sum_{d|i,d|n}phi(d) i=1∑n​d∣i,d∣n∑​ϕ(d)
直接枚举 d d d，就可以直接得到
∑ d ∣ n ϕ ( d ) n d sum_{d|n}phi(d)frac nd d∣n∑​ϕ(d)dn​
这显然是狄利克雷卷积的形式，是一个积性函数，直接线性筛就OK了。

再看一道题
有 t ( 1 ≤ t ≤ 10000 ) t(1leq tleq10000) t(1≤t≤10000)组数据，每组数据给定 n , m , k ( 1 ≤ n ≤ m ≤ 1 0 7 ) n,m,k(1leq nleq mleq10^7) n,m,k(1≤n≤m≤107).求: ∑ i = 1 n ∑ j = 1 m g c d ( i , j ) sum_{i=1}^nsum_{j=1}^mgcd(i,j) i=1∑n​j=1∑m​gcd(i,j)
这道题和刚刚有点像？
还是先枚举 g c d ( i , j ) gcd(i,j) gcd(i,j)：
∑ d = 1 n d ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = d ] sum_{d=1}^ndsum_{i=1}^nsum_{j=1}^m[gcd(i,j)=d] d=1∑n​di=1∑n​j=1∑m​[gcd(i,j)=d]
通过之前第二题的结论可以得到：
∑ d = 1 n d ∑ k = 1 n ⌊ n d k ⌋ ⌊ m d k ⌋ μ ( k ) sum_{d=1}^ndsum_{k=1}^nlfloorfrac n{dk}rfloorlfloorfrac m{dk}rfloormu(k) d=1∑n​dk=1∑n​⌊dkn​⌋⌊dkm​⌋μ(k)
我们令 T = d k T=dk T=dk，然后直接枚举 T T T：
∑ T = 1 n ⌊ n T ⌋ ⌊ m T ⌋ ∑ d ∣ T d μ ( T d ) sum_{T=1}^nlfloorfrac nTrfloorlfloorfrac mTrfloorsum_{d|T}dmu(frac Td) T=1∑n​⌊Tn​⌋⌊Tm​⌋d∣T∑​dμ(dT​)
记 f ( n ) = ∑ d ∣ T d μ ( T d ) f(n)=sum_{d|T}dmu(frac Td) f(n)=∑d∣T​dμ(dT​)，显然是狄利克雷卷积的形式，是一个积性函数，可以直接线性筛。
所以原式可以转化为：
∑ T = 1 n ⌊ n T ⌋ ⌊ m T ⌋ f ( T ) sum_{T=1}^nlfloorfrac nTrfloorlfloorfrac mTrfloor f(T) T=1∑n​⌊Tn​⌋⌊Tm​⌋f(T)
直接数论分块 O ( n + m ) O(sqrt n+sqrt m) O(n ​+m ​)
这道题同样也可以用欧拉函数，而且同样简单很多
原式可以直接转化为
∑ i = 1 n ∑ j = 1 m ∑ d ∣ i , d ∣ j ϕ ( d ) sum_{i=1}^nsum_{j=1}^msum_{d|i,d|j}{phi(d)} i=1∑n​j=1∑m​d∣i,d∣j∑​ϕ(d)
直接枚举 d d d：
∑ d = 1 n ϕ ( d ) ⌊ n d ⌋ ⌊ m d ⌋ sum_{d=1}^nphi(d)lfloorfrac ndrfloorlfloorfrac mdrfloor d=1∑n​ϕ(d)⌊dn​⌋⌊dm​⌋
然后数论分块就OK了。
就是这么简单。
那干嘛要讲莫比乌斯反演的做法？
练手感…因为很多题都是只能用莫比乌斯反演做的，比如说下一题：
有 t ( 1 ≤ t ≤ 1000000 ) t(1leq tleq1000000) t(1≤t≤1000000)组数据，每组数据给定 n , m , k ( 1 ≤ n ≤ 1 0 7 ) n,m,k(1leq nleq10^7) n,m,k(1≤n≤107)求 ∑ i = 1 n l c m ( i , n ) sum_{i=1}^nlcm(i,n) i=1∑n​lcm(i,n)
先讲一种用欧拉函数的 O ( n l o g n ) O(nlogn) O(nlogn)做法（当然在这道题会TLE，但是可以了解一下，这种做法非常神奇）
∑ i = 1 n l c m ( i , n ) sum_{i=1}^nlcm(i,n) i=1∑n​lcm(i,n)
= n ∑ i = 1 n i g c d ( i , n ) =nsum_{i=1}^nfrac i{gcd(i,n)} =ni=1∑n​gcd(i,n)i​
= n ∑ d ∣ n 1 d ∑ i = 1 n i [ g c d ( i , n ) = d ] =nsum_{d|n}frac1dsum_{i=1}^{n}i[gcd(i,n)=d] =nd∣n∑​d1​i=1∑n​i[gcd(i,n)=d]
= n ∑ d ∣ n 1 d ∑ i = 1 n d i d [ g c d ( i , n d ) = 1 ] =nsum_{d|n}frac1dsum_{i=1}^{frac nd}id[gcd(i,frac nd)=1] =nd∣n∑​d1​i=1∑dn​​id[gcd(i,dn​)=1]
= n ∑ d ∣ n ∑ i = 1 n d i [ g c d ( i , n d ) = 1 ] =nsum_{d|n}sum_{i=1}^{frac nd}i[gcd(i,frac nd)=1] =nd∣n∑​i=1∑dn​​i[gcd(i,dn​)=1]
= n ∑ d ∣ n d ϕ ( d ) + [ d = 1 ] 2 =nsum_{d|n}frac {dphi(d)+[d=1]}2 =nd∣n∑​2dϕ(d)+[d=1]​
前面几行应该都懂了吧，都做了那么多题了
问题是最后一行…
我们只考虑后面的式子： ∑ i = 1 n d i [ g c d ( i , n d ) = 1 ] sum_{i=1}^{frac nd}i[gcd(i,frac nd)=1] ∑i=1dn​​i[gcd(i,dn​)=1]
因为 d d d是 n n n的因数，所以我们可以用 d d d代替 n d frac nd dn​：
∑ i = 1 d i [ g c d ( i , d ) = 1 ] sum_{i=1}^di[gcd(i,d)=1] i=1∑d​i[gcd(i,d)=1]
其实就是求小于等于 d d d与 d d d互质的数的和
然后我们会发现如果 x ⊥ d ( x &lt; d ) xperp d(x&lt;d) x⊥d(x<d)，那么 ( d − x ) ⊥ d (d-x)perp d (d−x)⊥d
所以我们可以把与 d d d互质的数首尾两两分组，他们的和就是 d d d，然后他们所有的和就是 d ϕ ( d ) 2 frac{dphi(d)}2 2dϕ(d)​，如果 x = d − x x=d-x x=d−x也不影响，特判一下d=1的情况就OK了。
然后线性筛出 ϕ phi ϕ，调和级数时间预处理答案。
但是这道题要 O ( n ) O(n) O(n)才行啊，有更优秀的做法吗？
莫比乌斯反演
∑ i = 1 n l c m ( i , n ) sum_{i=1}^nlcm(i,n) i=1∑n​lcm(i,n)
= n ∑ i = 1 n i g c d ( i , n ) =nsum_{i=1}^nfrac i{gcd(i,n)} =ni=1∑n​gcd(i,n)i​
= n ∑ d ∣ n 1 d ∑ i = 1 n i [ g c d ( i , n ) = d ] =nsum_{d|n}frac1dsum_{i=1}^{n}i[gcd(i,n)=d] =nd∣n∑​d1​i=1∑n​i[gcd(i,n)=d]
= n ∑ d ∣ n 1 d ∑ i = 1 n d i d [ g c d ( i , n d ) = 1 ] =nsum_{d|n}frac1dsum_{i=1}^{frac nd}id[gcd(i,frac nd)=1] =nd∣n∑​d1​i=1∑dn​​id[gcd(i,dn​)=1]
= n ∑ d ∣ n ∑ i = 1 n d i [ g c d ( i , n d ) = 1 ] =nsum_{d|n}sum_{i=1}^{frac nd}i[gcd(i,frac nd)=1] =nd∣n∑​i=1∑dn​​i[gcd(i,dn​)=1]
= n ∑ d ∣ n ∑ i = 1 n d i ∑ k ∣ i , k ∣ n d μ ( k ) =nsum_{d|n}sum_{i=1}^{frac nd}isum_{k|i,k|frac nd}mu(k) =nd∣n∑​i=1∑dn​​ik∣i,k∣dn​∑​μ(k)
= n ∑ d ∣ n ∑ k ∣ n d μ ( k ) k ∑ i = 1 n d k i =nsum_{d|n}sum_{k|frac nd}mu(k)ksum_{i=1}^{frac n{dk}}i =nd∣n∑​k∣dn​∑​μ(k)ki=1∑dkn​​i
= n ∑ k ∣ n μ ( k ) k ∑ d ∣ n k ∑ i = 1 d i =nsum_{k|n}mu(k)ksum_{d|frac nk}sum_{i=1}^di =nk∣n∑​μ(k)kd∣kn​∑​i=1∑d​i
后面那个式子用等差数列求和：
= n ∑ k ∣ n μ ( k ) k ∑ d ∣ n k d ( d + 1 ) 2 =nsum_{k|n}mu(k)ksum_{d|frac nk}frac{d(d+1)}{2} =nk∣n∑​μ(k)kd∣kn​∑​2d(d+1)​
= n 2 ∑ k ∣ n μ ( k ) k ∑ d ∣ n k ( d 2 + d ) =frac n2sum_{k|n}mu(k)ksum_{d|frac nk}(d^2+d) =2n​k∣n∑​μ(k)kd∣kn​∑​(d2+d)
我们记 f ( n ) = ∑ k ∣ n μ ( k ) k ∑ d ∣ n k d 2 , g ( n ) = ∑ k ∣ n μ ( k ) k ∑ d ∣ n k d f(n)=sum_{k|n}mu(k)ksum_{d|frac nk}d^2,g(n)=sum_{k|n}mu(k)ksum_{d|frac nk}d f(n)=∑k∣n​μ(k)k∑d∣kn​​d2,g(n)=∑k∣n​μ(k)k∑d∣kn​​d
可以轻松证明这两个都是积性函数，可以线性筛。
然后就OK了。
留一道题给读者思考：
【BZOJ2693】jzptab