【bzoj2693】【jzptable】【莫比乌斯反演】

本文主要是介绍【bzoj2693】【jzptable】【莫比乌斯反演】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
求 $\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$
Input
一个正整数T表示数据组数
接下来T行 每行两个正整数 表示N、M
Output
T行 每行一个整数 表示第i组数据的结果
Sample Input
1
4 5
Sample Output
122
HINT
T <= 10000
N, M<=10000000
题解：
普通的化法可以变成

$$\sum_{d=1}^{n}d\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\frac{x^2\mu(x)sum(\lfloor\frac{n}{dx}\rfloor,\lfloor\frac{m}{d}\rfloor)}{4}$$
sum(x,y)=x(x+1)y(y+1)
设T=dx;
则可以化成
$$\sum_{T=1}^{n}sum2(\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor)T\sum_{x|T}^{}\mu(x)x$$
sum2(x,y)=x(x+1)y(y+1)/4
设f(T)= $\sum_{x|T}^{}\mu(x)x$
如果我们能与处理出f数组,然后做一个Tf(T)的前缀和即可。
可以证明f(T)是积性函数.然后我们把f(T)线筛出来即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10000010
#define P 100000009
#define LL long long
using namespace std;
int p[N],f[N],n,m,T,pos;
LL g[N],ans,s[N];
void pre(){g[1]=1;for (int i=2;i<=n;i++){if (!f[i]){p[++p[0]]=i;g[i]=(1-i+P)%P;}for (int j=1;j<=p[0]&&i*p[j]<=n;j++){f[i*p[j]]=1;if (i%p[j]==0){g[i*p[j]]=g[i];break;}g[i*p[j]]=(g[i]*g[p[j]])%P;}}for (int i=1;i<=n;i++) g[i]=(g[i]*i)%P;for (int i=1;i<=n;i++) s[i]=(s[i-1]+g[i])%P;
}
LL sum(LL x,LL y){LL t1=x*(x+1)/2;LL t2=y*(y+1)/2;t1%=P;t2%=P;return (t1*t2)%P; 
}
int main(){scanf("%d",&T);n=N-10;pre();while (T--){scanf("%d%d",&n,&m);if (n>m) swap(n,m);ans=0;pos=0;for (int i=1;i<=n;i=pos+1){pos=min((n/(n/i)),(m/(m/i)));ans+=(sum((LL)(n/i),(LL)(m/i))*(s[pos]-s[i-1]+P)%P)%P;ans%=P;}  printf("%lld\n",ans);  }
} 

这篇关于【bzoj2693】【jzptable】【莫比乌斯反演】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---