洛谷1829 【国家集训队】Crash的数字表格（莫比乌斯反演）

本文链接：https://blog.csdn.net/g21glf/article/details/87715632

传送门

【题目分析】

又一次败给了取模。。。。。qwq

还是先翻译一下题目：

$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$

lcm不好求，转一下变成gcd：

$\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{gcd(i,j)}$

枚举gcd(i,j)=p：

$\sum_{p=1}^{min(n,m)}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{p}[gcd(i,j)=p]$

后面这一堆直接除一个p，因为i,j各含一个p，所以直接抵消：

$\sum_{p=1}^{min(n,m)}p*\sum_{i=1}^{[\frac{n}{p}]}\sum_{j=1}^{[\frac{m}{p}]}i*j[gcd(i,j)=1]$

$\sum_{i=1}^{[\frac{n}{p}]}\sum_{j=1}^{[\frac{m}{p}]}i*j[gcd(i,j)=1]$ 这一块就是两个等差数列相乘，令：

$f(n)=\sum_{i=1}^ni$ ，

所以有:

$\sum_{p=1}^{min(n,m)}p*f([\frac{n}{p}])f([\frac{m}{p}])[gcd(i,j)=1]$

容斥+反演一下：

$\sum_{p=1}^{min(n,m)}p*f([\frac{n}{p}])f([\frac{m}{p}])*\sum_{t\mid gcd(i,j)}^{i\leq [\frac{n}{p}],j\leq[{\frac{m}{p}}]}\mu(t)$

化一下得到：

换个元，令T=pt：

$\sum_{T=1}^{min(n,m)}f(\frac{n}{T})*f{[\frac{m}{T}]}*T\sum_{d\mid T}d*\mu(d)$

所以这就是我们要求的式子，显然前半 $\sum_{p=1}^{min(n,m)}p*\sum_{t=1}^{[\frac{min(n,m)}{p}]}t^2*\mu(t)*f([\frac{n}{pt}])*f([\frac{m}{pt}])$ 截可以直接O(1)得到，所以考虑如何在线筛处理 $T\sum_{d\mid T}d*\mu(d)$ 这一块。

其实可以发现 $\sum_{d\mid T}d*\mu(d)$ 这是个积性函数，式子是这样推的：

$\left\{\begin{matrix} 1-p & p\in Prime & \\ f(a)*f(p) & p\in Prime,p\nmid a& \\ f(a) &p\in Prime,p\mid a & \end{matrix}\right.$

所以就可以在线性筛的时候把前缀和求出来了。

【代码~】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN=1e7+10;
const LL MOD=20101009;
const LL INV=MOD-MOD/2;

int n,m,up;
LL ans;
int prime[MAXN],vis[MAXN],tot;
LL sum[MAXN];

void pre(){
	sum[1]=1;
	for(int i=2;i<=1e7;++i){
		if(!vis[i])
		  prime[++tot]=i,sum[i]=1-i;
		for(int j=1;prime[j]*i<=1e7;++j){
			vis[prime[j]*i]=1;
			if(i%prime[j]==0){
				sum[prime[j]*i]=sum[i];
				break;
			}
			sum[prime[j]*i]=sum[i]*(1-prime[j]);
		}
		sum[i]=((LL)i*sum[i]%MOD+sum[i-1]+MOD)%MOD;
	}
}

LL calc(LL x){
	return x*(x+1)%MOD*INV%MOD;
}

int main(){
	cin>>n>>m;
	pre();
	for(int i=1;i<=min(n,m);i=up+1){
		up=min(n/(n/i),m/(m/i));
		ans=(ans+calc(n/i)*calc(m/i)%MOD*(sum[up]-sum[i-1]+MOD)%MOD)%MOD;
	}
	cout<<ans;
	return 0;
}