【题意】
原题地址
题目大意：见分析。
【解题思路】
显然是反演，然而我的做法和网上题解完全不一样- -，使得我心态爆炸了很久。
题目相当于求 Ans=∑ni=11i∑ij=1lcm(i,j)A n s = ∑ i = 1 n 1 i ∑ j = 1 i l c m ( i , j ) ，开始推柿子。
lcm转化为gcd（跳了一步） ∑ni=1∑ij=1jgcd(i,j)∑ i = 1 n ∑ j = 1 i j g c d ( i , j )
疯狂改变枚举顺序 ∑nd=1∑?nd?i=1∑ij=1[gcd(i,j)==1]?j∑ d = 1 n ∑ i = 1 ? n d ? ∑ j = 1 i [ g c d ( i , j ) == 1 ] ? j
∑nd=1∑?nd?d′=1∑?ndd′?i=1∑ij=1(j?d′?μ(d′))∑ d = 1 n ∑ d ′ = 1 ? n d ? ∑ i = 1 ? n d d ′ ? ∑ j = 1 i ( j ? d ′ ? μ ( d ′ ) )
我们设 s(x)=x?μ(x),f(x)=x(x+1)(2x+1)2?6+x(x+1)2?2s ( x ) = x ? μ ( x ) , f ( x ) = x ( x + 1 ) ( 2 x + 1 ) 2 ? 6 + x ( x + 1 ) 2 ? 2
那么上面的柿子可以化成 ∑nd=1∑?nd?d′=1(s(d′)?f(?ndd′?))∑ d = 1 n ∑ d ′ = 1 ? n d ? ( s ( d ′ ) ? f ( ? n d d ′ ? ) )
我们发现现在还是求不了答案，于是设 T=dd′T = d d ′
使劲化： ∑nT=1f(?nT?)?∑d|Ts(d)∑ T = 1 n f ( ? n T ? ) ? ∑ d | T s ( d )
设 g(x)=∑d|xs(d)g ( x ) = ∑ d | x s ( d ) ，观察柿子我们可以发现：
∑ni=1g(i)=∑ni=1∑d|is(d)=∑nd=1∑?nd?i=1s(d)=∑nd=1s(d)??nd?∑ i = 1 n g ( i ) = ∑ i = 1 n ∑ d | i s ( d ) = ∑ d = 1 n ∑ i = 1 ? n d ? s ( d ) = ∑ d = 1 n s ( d ) ? ? n d ?
设 sum(x)=∑xi=1s(i)s u m ( x ) = ∑ i = 1 x s ( i ) ，我们可以发现： ∑ni=1g(i)=∑ni=1sum(?nd?)∑ i = 1 n g ( i ) = ∑ i = 1 n s u m ( ? n d ? )
接下来的问题是求 s(x)和g(x)s ( x ) 和 g ( x ) ，两个都是积性函数，因为前缀和比较大，考虑用杜教筛。
对于 s(x)s ( x ) 那么卷上一个 idi d ，得到的实际上就是一个 ee
s[i]=∑ni=1∑j|ij?μ(j)?ij=∑nj=1∑?nj?i=1j?μ(j)=[n==1]s [ i ] = ∑ i = 1 n ∑ j | i j ? μ ( j ) ? i j = ∑ j = 1 n ∑ i = 1 ? n j ? j ? μ ( j ) = [ n == 1 ]
将 i==1i == 1 的情况移过去，得到：
[n==1]?∑nj=1j?μ(j)=∑ni=2i?∑?ni?j=1j?μ(j)[ n == 1 ] ? ∑ j = 1 n j ? μ ( j ) = ∑ i = 2 n i ? ∑ j = 1 ? n i ? j ? μ ( j )
即 [n==1]?s(n)=∑ni=2i?s(?ni?)[ n == 1 ] ? s ( n ) = ∑ i = 2 n i ? s ( ? n i ? )
g(x)g ( x ) 类似，然后就没了。
【参考代码】
#include
using namespace std;
typedef long long LL;
const int N=5e6+10;
const int mod=1e9+7;
const LL inv2=500000004,inv6=166666668;
mapmps,mpg;
int pnum,l,r;
int bo[N],pri[N];
LL s[N],g[N];
void init()
{
s[1]=g[1]=1;
for(int i=2;
i 【数论-莫比乌斯反演|【莫比乌斯反演+杜教筛】51Nod-1227 平均最小公倍数】【总结】
嗯，我们要多记住一些函数的性质，就不用像我一样推这么久了，直接用 ?? 的性质就很好做，我这里最后一步还是侥幸化出一个积性函数的东西才搞掉的- -。
而且这个做法杜教筛套杜教筛，十分不优美- -。
