http://www.lydsy.com/JudgeOnline/problem.php?id=2154 (题目链接)

题意

　　给出${n,m}$，求$${\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)}$$

Solution

　　莫比乌斯反演，推啊推式子。

\begin{aligned}  \sum_{i=1}^n\sum_{j=1}^mlcm(i,j)=&\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}  \\  =&\sum_{g=1}^{min(n,m)}\sum_{i=1}^{\lfloor{n/g}\rfloor}\sum_{j=1}^{\lfloor{m/g}\rfloor}\frac{ijg^2}{g}[gcd(i,j)=1]  \\  =&\sum_{g=1}^{min(n,m)}g\sum_{i=1}^{\lfloor{n/g}\rfloor}\sum_{j=1}^{\lfloor{m/g}\rfloor}ij\sum_{t|i,t|j}μ(t)  \\  =&\sum_{g=1}^{min(n,m)}g\sum_{t=1}^{min(\lfloor{n/g}\rfloor,\lfloor{m/g}\rfloor)}μ(t)\sum_{i=1}^{\lfloor{n/(gt)}\rfloor}\sum_{j=1}^{\lfloor{m/(gt)}\rfloor}ijt^2   \end{aligned}

　　此时，我们用${S(n)}$表示${\sum_{i=1}^n1}$。

\begin{aligned}  \sum_{g=1}^{min(n,m)}g\sum_{t=1}^{min(\lfloor{n/g}\rfloor,\lfloor{m/g}\rfloor)}μ(t)t^2S(\lfloor\frac{n}{gt}\rfloor)S(\lfloor\frac{m}{gt}\rfloor)   \end{aligned}

　　令${Q=gt}$。

\begin{aligned}  \sum_{Q=1}^{min(n,m)}S(\lfloor\frac{n}{Q}\rfloor)S(\lfloor\frac{m}{Q}\rfloor)Q\sum_{t|Q}tμ(t)   \end{aligned}

　　我们发现，${g(Q)=\sum_{t|Q}tμ(t)}$是个积性函数，为什么呢。首先有公式${f(t)=tμ(t)}$是积性的，那么我们构造另外一个积性函数${p(t)=1}$，将${f}$和${p}$狄利克雷卷积，就得到了${g}$，所以${g}$是个积性函数，可以用线性筛在${O(n)}$的时间内算出来，所以最后复杂度就是${O(n)}$的。

细节

　　最后输出答案的时候加模再取模

代码

// bzoj2154#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#define LL long long#define inf 2147483647#define MOD 20101009#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=10000010;LL f[maxn],S[maxn];int p[maxn],vis[maxn],n,m;int main() {	scanf("%d%d",&n,&m);	if (n>m) swap(n,m);	S[1]=f[1]=1;	for (int i=2;i<=m;i++) {		if (!vis[i]) p[++p[0]]=i,f[i]=1-i;		for (int j=1;j<=p[0] && p[j]*i<=m;j++) {			vis[i*p[j]]=1;			if (i%p[j]==0) {f[i*p[j]]=f[i];break;}			else f[i*p[j]]=f[i]*f[p[j]]%MOD;		}		S[i]=(S[i-1]+i)%MOD;	}	LL ans=0;	for (LL i=1;i<=n;i++)		ans=(ans+S[n/i]*S[m/i]%MOD*i%MOD*f[i]%MOD)%MOD;	printf("%lld\n",(ans+MOD)%MOD);	return 0;}

【bzoj2154】 Crash的数字表格